TL;DR — 3줄 핵심 요약• 문제: 퀵 정렬은 평균 O(n log n)으로 빠르지만, 피벗을 잘못 고르면 이미 정렬된 배열에서 O(n²)까지 느려진다.• 기술/원인: 피벗을 기준으로 작은 값과 큰 값을 나누고, 나뉜 두 구간에 같은 일을 반복한다. 분할이 한쪽으로만 되면 비교 횟수가 (n-1)+(n-2)+…+1이 되어 제곱이 된다.• 해결/인사이트: 랜덤 피벗, 미디언-오브-쓰리, 작은 구간의 삽입 정렬 전환, 꼬리 재귀, Introsort로 최악을 피한다. C++ std::sort도 Introsort를 쓴다.들어가며한 기업의 필기 테스트에서 나온 문제를 계기로 퀵 정렬을 다시 정리했다. 퀵 정렬은 평균 속도가 빠르고 추가 메모리를 거의 쓰지 않아 널리 쓰인다. 이 글은 기본 개념, 동작 원리, 최악..

TL;DR — 3줄 핵심 요약• 문제: 직무 테스트에서 데이터베이스 인덱스를 설명하는 문항을 다 쓰지 못했다. 백엔드와 모바일 게임 서버에서 인덱스 설계는 읽기 성능을 좌우한다.• 기술/원인: 인덱스는 컬럼 값과 레코드 위치를 정렬해 둔 별도 자료구조다. 조회는 그 구조에서 위치를 먼저 찾아 전체 스캔을 피하지만, 삽입·수정·삭제 때는 인덱스도 함께 갱신해야 한다.• 해결/인사이트: WHERE, JOIN, GROUP BY, ORDER BY에 자주 쓰이는 컬럼에 선택도가 높은 것부터 건다. 만든 뒤에는 EXPLAIN으로 실제 사용 여부를 확인해야 한다.들어가며: 직무 테스트에서 놓친 주제며칠 전 한 기업의 직무 테스트를 봤다. CS 기초 필기였는데, 데이터베이스 인덱스 문항을 끝까지 쓰지 못했다. 인덱스는..

TL;DR — 3줄 핵심 요약• 문제: Malloc Lab은 malloc, free, realloc을 직접 구현하는 과제인데, 사전 지식 없이는 무엇부터 손대야 할지 알 수 없었다.• 기술/원인: 힙은 sbrk로 늘어나며, 블록마다 크기와 사용 여부를 적은 헤더를 두고, 가용 블록은 리스트로 관리한다. 할당 방식(First Fit, Best Fit)과 병합(Coalescing)이 단편화와 처리 속도를 좌우한다.• 해결/인사이트: 사용률(얼마나 낭비 없이 썼는가)과 처리량(초당 몇 번 처리했는가)은 서로 맞바꾸는 관계다. 점수는 두 값을 함께 계산하므로 한쪽만 올리는 구현은 점수가 오르지 않는다.들어가며크래프톤 정글 4기에서 Malloc Lab을 구현해야 했다. 이 글은 그때 이해를 위해 정리한 사전 지식..

TL;DR — 3줄 핵심 요약• 문제: PintOS Threads 과제를 하려면 프로세스와 스레드, 스케줄링, 동기화, 경쟁 상태, 교착 상태, 문맥 교환, MLFQS를 한 번에 설명할 수 있어야 했다.• 기술/원인: CPU는 한 번에 하나만 실행하므로, 운영체제는 스케줄러로 실행 순서를 정하고, 공유 데이터에는 락과 세마포어로 순서를 강제하며, 전환할 때는 문맥을 저장하고 복원한다.• 해결/인사이트: 개념을 정의, 원인, 대표 알고리즘 순서로 정리하고 나면 PintOS의 Alarm Clock, Priority Scheduling, MLFQS 구현이 무엇을 요구하는지 보인다.들어가며크래프톤 정글에서 KAIST PintOS를 구현하며 팀 프로젝트를 진행하고 있다. 이 글은 정글에서 제공한 가이드라인의 공부..

TL;DR — 3줄 핵심 요약• 문제: 레드-블랙 트리를 이해하려면 이진 탐색 트리, 균형, 회전, 재귀를 먼저 알아야 했고, 삽입과 삭제의 경우의 수가 많았다.• 기술/원인: 레드-블랙 트리는 노드에 빨강이나 검정 색을 붙이고 다섯 가지 규칙을 지키는 이진 탐색 트리다. 규칙이 깨지면 색을 바꾸고 회전으로 구조를 고친다.• 해결/인사이트: 규칙 덕분에 트리의 높이가 log n 수준으로 유지되어 탐색, 삽입, 삭제가 최악의 경우에도 O(log n)이다. 삽입은 새 노드를 항상 빨강으로 넣고, 삼촌 노드의 색에 따라 두 갈래로 처리한다.들어가며: 정글 4주차 주제크래프톤 정글 4기 Part 2 "탐험 준비"를 진행하면서 4주차에 레드-블랙 트리를 다뤘다. 이 글은 그때 정리한 기본 개념이다.레드-블랙 트리..

TL;DR — 3줄 핵심 요약• 문제: 백준 1197번을 풀려고 했는데, 스패닝 트리가 무엇인지도 모르는 상태에서 개념 다섯 개(MST, 프림, 크루스칼, 우선순위 큐, 유니온-파인드)가 한 문제에 들어 있었다.• 기술/원인: MST는 모든 정점을 연결하면서 사이클이 없고 간선 가중치 합이 최소인 트리다. 프림은 정점에서 시작해 가장 싼 간선으로 넓히고, 크루스칼은 간선을 싼 순서로 보며 사이클이 생기면 건너뛴다.• 해결/인사이트: 사이클 판정은 유니온-파인드로 한다. 개념을 정리한 뒤에는 문제가 바로 풀렸고, 제출해 채점까지 통과해야 끝난다는 것도 확인했다.들어가며: 문제 하나에 개념 다섯 개2024년 1월 19일, 백준 1197번 최소 스패닝 트리 문제를 풀려고 했다. 정점 V개(최대 10,000)와..