알고리즘 개론 (CLRS) 치트시트

Cheatsheet Content

1. 알고리즘 분석 1.1. 점근적 표기법 $O(g(n))$: 상한 (최악의 경우), $f(n) \le c \cdot g(n)$ $\Omega(g(n))$: 하한 (최선의 경우), $f(n) \ge c \cdot g(n)$ $\Theta(g(n))$: 상한 및 하한, $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ $o(g(n))$: 엄격한 상한, $f(n) $\omega(g(n))$: 엄격한 하한, $f(n) > c \cdot g(n)$ (작은 $\Omega$) 1.2. 재귀 관계 치환 방법: 답 예상 후 귀납법으로 증명 재귀 트리 방법: 재귀 트리를 그려서 비용 합산 마스터 정리: $T(n) = aT(n/b) + f(n)$ if $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$ if $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$ if $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$, and $a f(n/b) \le c f(n)$ for some $c 2. 정렬 알고리즘 2.1. 비교 정렬 삽입 정렬: $O(n^2)$, 제자리 정렬, 안정적 선택 정렬: $O(n^2)$, 제자리 정렬, 불안정적 합병 정렬: $O(n \log n)$, $O(n)$ 공간, 안정적, 분할 정복 힙 정렬: $O(n \log n)$, $O(1)$ 공간, 불안정적, 힙 자료구조 사용 퀵 정렬: 평균 $O(n \log n)$, 최악 $O(n^2)$, 제자리 정렬, 불안정적, 분할 정복 (피벗 선택 중요) 비교 정렬의 하한: $\Omega(n \log n)$ 2.2. 선형 시간 정렬 계수 정렬 (Counting Sort): $O(n+k)$, $k$는 원소 범위, 안정적, 정수만 가능 기수 정렬 (Radix Sort): $O(d(n+k))$, $d$는 자릿수, 안정적, 정수만 가능 버킷 정렬 (Bucket Sort): 평균 $O(n)$, 균등 분포 가정 3. 자료 구조 3.1. 기본 자료 구조 스택: LIFO (Last-In, First-Out), PUSH , POP - $O(1)$ 큐: FIFO (First-In, First-Out), ENQUEUE , DEQUEUE - $O(1)$ 링크드 리스트: 단일/이중/원형, 삽입/삭제 $O(1)$ (위치 알 때), 검색 $O(n)$ 3.2. 트리 이진 탐색 트리 (BST): 검색, 삽입, 삭제 평균 $O(h)$, 최악 $O(n)$ ($h$는 높이) 레드-블랙 트리 (RBT): 균형 이진 탐색 트리, 모든 연산 $O(\log n)$ 속성: 1. 노드는 빨강 또는 검정. 2. 루트는 검정. 3. 모든 잎(NIL)은 검정. 4. 빨강 노드의 자식은 모두 검정. 5. 모든 노드에서 잎까지의 단순 경로에 포함된 검정 노드의 수는 동일. B-트리: 디스크 기반 자료 구조에 적합, 각 노드에 여러 키 저장, $O(\log_t n)$ ($t$는 최소 차수) 힙: 완전 이진 트리, 힙 속성 만족 (최대 힙: 부모 $\ge$ 자식, 최소 힙: 부모 $\le$ 자식) BUILD-HEAP : $O(n)$ HEAPIFY : $O(\log n)$ INSERT , EXTRACT-MAX/MIN : $O(\log n)$ 3.3. 해시 테이블 직접 주소 지정 테이블: $O(1)$ 조회, 키 범위 작을 때 체이닝: 충돌 시 링크드 리스트로 연결, 평균 $O(1+\alpha)$ (삽입/삭제/검색), $\alpha$는 적재율 개방 주소 지정: 충돌 시 다른 슬롯 탐색 (선형, 이차, 이중 해싱), $O(1+\alpha)$ 4. 그래프 알고리즘 4.1. 그래프 탐색 BFS (너비 우선 탐색): 최단 경로 (가중치 없는 그래프), $O(V+E)$, 큐 사용 DFS (깊이 우선 탐색): $O(V+E)$, 스택/재귀 사용, 위상 정렬, 강한 연결 요소 4.2. 최소 신장 트리 (MST) 프림 알고리즘: $O(E \log V)$ (이진 힙), $O(E + V \log V)$ (피보나치 힙) 크루스칼 알고리즘: $O(E \log E)$ 또는 $O(E \log V)$, Disjoint-Set 자료구조 사용 4.3. 최단 경로 벨만-포드: 단일 시작점, 음수 가중치 허용, 음수 사이클 감지, $O(VE)$ 다익스트라: 단일 시작점, 음수 가중치 불허, $O(E \log V)$ (이진 힙), $O(E + V \log V)$ (피보나치 힙) 플로이드-워셜: 모든 쌍 최단 경로, 음수 가중치 허용, $O(V^3)$ 존슨 알고리즘: 모든 쌍 최단 경로, 희소 그래프에 효율적, $O(VE + V^2 \log V)$ 4.4. 기타 그래프 알고리즘 위상 정렬: DAG (방향 비순환 그래프)에서만 가능, $O(V+E)$ 강한 연결 요소 (SCC): DFS 2회, 코사라주/타잔 알고리즘, $O(V+E)$ 최대 유량: 포드-풀커슨 알고리즘, 에드몬즈-카프 알고리즘 5. 고급 설계 기법 5.1. 동적 계획법 (Dynamic Programming) 부분 문제의 최적 구조, 중복 부분 문제 상향식 (Bottom-up) 또는 하향식 (Top-down) (메모이제이션) 예시: 최장 공통 부분 수열 (LCS), 0/1 배낭 문제, 행렬 연쇄 곱셈 5.2. 탐욕 알고리즘 (Greedy Algorithms) 탐욕적 선택 속성, 최적 부분 구조 항상 지역적으로 최적의 선택을 함으로써 전역적으로 최적의 해를 찾는 전략 예시: 활동 선택 문제, 허프만 코딩, 프림/크루스칼 알고리즘 5.3. 분할 정복 (Divide and Conquer) 문제를 작은 하위 문제로 분할 하위 문제를 재귀적으로 해결 하위 문제의 해를 결합하여 원래 문제의 해를 구함 예시: 합병 정렬, 퀵 정렬, 행렬 곱셈 (스트라센) 6. NP-완전성 P: 다항 시간 내에 풀 수 있는 결정 문제의 집합 NP: 해가 주어졌을 때 다항 시간 내에 검증할 수 있는 결정 문제의 집합 NP-완전 (NPC): NP에 속하며, NP에 속하는 모든 문제가 다항 시간 내에 이 문제로 환원될 수 있는 문제의 집합 NP-난해 (NPH): NP-완전 문제만큼 어렵거나 더 어려운 문제의 집합 (결정 문제가 아닐 수도 있음) 쿡의 정리: SAT (충족 가능성 문제)는 NP-완전이다. 예시: TSP (외판원 문제), 부분집합 합 문제, 클리크 문제, 정점 덮개 문제 7. 기타 알고리즘 7.1. 문자열 매칭 고지식한 알고리즘: $O((n-m+1)m)$ 라빈-카프: 해싱 이용, 평균 $O(n+m)$, 최악 $O(nm)$ KMP (크누스-모리스-프랫): 전처리 $O(m)$, 매칭 $O(n)$, 총 $O(n+m)$ 7.2. 기하 알고리즘 볼록 껍질 (Convex Hull): 그레이엄 스캔 $O(n \log n)$, 자비스 행진 $O(nh)$ 가장 가까운 두 점 (Closest Pair): $O(n \log n)$