알고리즘 핵심 요약

Cheatsheet Content

동적 계획법 (Dynamic Programming) 복잡한 문제를 여러 개의 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 각 하위 문제의 해를 한 번만 계산하여 저장하고, 필요할 때 재사용함으로써 중복 계산을 피하고 효율성을 높입니다. DP의 주요 단계 최적해 구조 특징화: 문제의 최적해가 하위 문제의 최적해를 포함하는지 (최적 부분 구조) 파악합니다. 최적해 값 재귀적 정의: 하위 문제의 해를 기반으로 전체 문제의 최적해 값을 재귀적으로 정의하는 점화식을 세웁니다. 최적해 값 계산 (상향식 또는 하향식): 상향식 (Bottom-up): 가장 작은 하위 문제부터 시작하여 점화식을 사용하여 점차 큰 문제의 해를 계산해 나갑니다. 보통 테이블에 해를 저장합니다. 하향식 (Top-down, 메모이제이션): 재귀적으로 문제를 풀되, 한 번 계산한 하위 문제의 해는 저장해 두었다가 다시 필요할 때 가져다 씁니다. 최적해 구성: 계산된 정보를 바탕으로 실제 최적해 (예: LCS 문자열, 행렬 곱셈 순서)를 구성합니다. 최장 공통 부분 수열 (LCS) 두 수열 $X = \langle x_1, \dots, x_m \rangle$와 $Y = \langle y_1, \dots, y_n \rangle$가 주어졌을 때, $X$와 $Y$ 모두의 부분 수열인 가장 긴 수열 $Z$를 찾습니다. 이는 유전자 서열 분석, 파일 비교 등에 응용됩니다. $X_i$는 $X$의 첫 $i$개 원소로 구성된 접두어, $Y_j$는 $Y$의 첫 $j$개 원소로 구성된 접두어를 의미합니다. $X_i$와 $Y_j$의 LCS 길이를 $c[i,j]$라고 할 때, 점화식은 다음과 같습니다: $$ c[i,j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0 \\ c[i-1, j-1] + 1 & \text{if } x_i = y_j \\ \max(c[i-1, j], c[i, j-1]) & \text{if } x_i \ne y_j \end{cases} $$ 설명: $i=0$ 또는 $j=0$인 경우, 한 수열이 비어 있으므로 LCS 길이는 0입니다. $x_i = y_j$인 경우, 두 수열의 마지막 원소가 같으므로, 이 원소를 LCS에 포함시키고, $X_{i-1}$과 $Y_{j-1}$의 LCS 길이에 1을 더합니다. $x_i \ne y_j$인 경우, $x_i$ 또는 $y_j$ 중 하나를 LCS에 포함시킬 수 없으므로, $X_i$와 $Y_{j-1}$의 LCS 길이, 또는 $X_{i-1}$과 $Y_j$의 LCS 길이 중 더 큰 값을 선택합니다. 시간 복잡도: $O(mn)$. 공간 복잡도: $O(mn)$ (LCS 테이블 저장용). 행렬 연쇄 곱셈 (Matrix-Chain Multiplication) 행렬 $A_1, A_2, \dots, A_n$이 주어졌을 때, 이들을 곱하는 데 필요한 스칼라 곱셈의 총 횟수를 최소화하는 괄호화를 찾는 문제입니다. 행렬 곱셈은 결합법칙이 성립하지만 교환법칙은 성립하지 않으므로, 곱셈 순서에 따라 비용이 크게 달라질 수 있습니다. $A_i$의 차원이 $p_{i-1} \times p_i$라고 할 때, $A_{i \dots j}$ (즉, $A_i \times A_{i+1} \times \dots \times A_j$)를 계산하는 데 필요한 최소 스칼라 곱셈 수를 $m[i,j]$라고 하면, 점화식은 다음과 같습니다: $$ m[i,j] = \begin{cases} 0 & \text{if } i=j \\ \min_{i \le k 설명: $i=j$인 경우, 하나의 행렬이므로 곱셈 비용은 0입니다. $i 시간 복잡도: $O(n^3)$. 공간 복잡도: $O(n^2)$. 탐욕 알고리즘 (Greedy Algorithms) 탐욕 알고리즘은 각 단계에서 그 순간에 가장 최적이라고 생각되는 선택을 하는 방식으로 해를 찾아나갑니다. 이러한 지역적으로 최적의 선택들이 궁극적으로 전역적으로 최적의 해를 도출할 것이라고 기대합니다. 탐욕 알고리즘이 최적해를 보장하려면 다음 두 가지 속성이 만족되어야 합니다. 최적 부분 구조 (Optimal Substructure): 문제의 최적해가 하위 문제의 최적해를 포함합니다. 탐욕적 선택 속성 (Greedy-Choice Property): 지역적으로 최적의 선택을 하면 나중에 다시 고려할 필요 없이 전역적으로 최적의 해를 얻을 수 있습니다. 즉, 탐욕적 선택이 항상 안전합니다. 활동 선택 문제 (Activity Selection Problem) 서로 시간이 겹치지 않으면서 가능한 한 많은 활동을 선택하는 문제입니다. 각 활동 $i$는 시작 시간 $s_i$와 종료 시간 $f_i$를 가집니다. 예를 들어, 회의실 사용 스케줄링에 적용될 수 있습니다. 탐욕적 전략: 모든 활동을 종료 시간 $f_i$의 오름차순으로 정렬합니다. 종료 시간이 같으면 시작 시간이 빠른 순으로 정렬합니다. 가장 먼저 종료되는 활동을 선택합니다. 이 활동은 가능한 가장 많은 시간을 남겨주어 다른 활동들이 선택될 기회를 높입니다. 선택된 활동과 시간이 겹치지 않는 (즉, 시작 시간이 이전에 선택된 활동의 종료 시간보다 크거나 같은) 활동들 중에서 다음으로 종료 시간이 가장 빠른 활동을 선택합니다. 더 이상 선택할 활동이 없을 때까지 이 과정을 반복합니다. 예시: 활동 A(1,4), B(3,5), C(0,6), D(5,7), E(3,8), F(5,9), G(6,10), H(8,11), I(8,12), J(2,13), K(12,14) 정렬 후: A(1,4), B(3,5), D(5,7), C(0,6) (종료시간 6이지만 시작시간 0), E(3,8), F(5,9), G(6,10), H(8,11), I(8,12), J(2,13), K(12,14) 탐욕적 선택: A(1,4) -> D(5,7) -> H(8,11) -> K(12,14). 총 4개 활동. 시간 복잡도: $O(n \log n)$ (정렬 시간) + $O(n)$ (선택 과정) $= O(n \log n)$. 허프만 코딩 (Huffman Coding) 데이터 압축을 위한 효율적인 방법으로, 각 문자의 빈도수에 따라 가변 길이의 이진 코드를 할당하는 접두어 코드(prefix code)를 생성합니다. 빈도수가 높은 문자에는 짧은 코드를, 빈도수가 낮은 문자에는 긴 코드를 할당하여 전체 비트 수를 최소화합니다. 탐욕적 전략: 각 문자와 해당 빈도수를 나타내는 리프 노드를 생성합니다. 이 노드들을 빈도수를 기준으로 하는 최소 우선순위 큐에 삽입합니다. 우선순위 큐에 노드가 하나만 남을 때까지 다음을 반복합니다: 큐에서 빈도수가 가장 작은 두 노드 (C1, C2)를 추출합니다. 이 두 노드를 자식으로 하고, 빈도수의 합을 자신의 빈도수로 하는 새로운 내부 노드 (C_new)를 생성합니다. (C1은 C_new의 왼쪽 자식, C2는 오른쪽 자식이 될 수 있으며, 이는 코드 할당에 영향을 줍니다.) 새로운 내부 노드 C_new를 우선순위 큐에 삽입합니다. 최종적으로 큐에 남은 하나의 노드가 허프만 트리의 루트가 됩니다. 트리의 루트에서 리프 노드까지의 경로를 따라 '0'과 '1'을 할당하여 각 문자의 코드를 얻습니다. 시간 복잡도: $O(n \log n)$, 여기서 $n$은 고유 문자의 수입니다. 우선순위 큐에 $n$개의 삽입/삭제 연산이 발생하며, 각 연산은 $O(\log n)$이 소요됩니다. 복잡도 클래스 (Complexity Classes) 계산 문제들을 그들이 해결될 수 있는 자원의 양(시간, 공간 등)에 따라 분류하는 것입니다. 알고리즘의 효율성을 이해하는 데 필수적입니다. P (Polynomial time): 결정론적 튜링 머신(일반적인 컴퓨터 모델)으로 입력 크기에 대한 다항 시간 내에 해결 가능한 문제들의 집합입니다. 이들은 일반적으로 "쉽게" 해결할 수 있는 문제로 간주됩니다 (예: 정렬, 검색, 최단 경로). NP (Nondeterministic Polynomial time): 해답이 주어졌을 때, 그 해답이 올바른지 여부를 결정론적 튜링 머신으로 다항 시간 내에 검증 할 수 있는 문제들의 집합입니다. 해를 찾는 것은 어려울 수 있지만, 해를 확인하는 것은 쉽습니다 (예: 부분집합 합, 해밀턴 경로). NP-완전 (NPC): NP에 속하는 문제 중, NP의 모든 다른 문제가 다항 시간 내에 이 문제로 환원(reduction)될 수 있는 문제의 집합입니다. 만약 어떤 NP-완전 문제를 다항 시간 내에 풀 수 있다면, P=NP가 증명됩니다. 이는 컴퓨터 과학의 가장 큰 미해결 문제입니다. NP-난해 (NP-Hard): NP의 모든 문제가 다항 시간 내에 이 문제로 환원될 수 있는 문제의 집합입니다. NP-난해 문제는 반드시 NP에 속할 필요는 없습니다 (예: 정지 문제). NP-완전 문제는 NP-난해 문제이면서 동시에 NP에 속하는 문제입니다. P vs NP 문제: P와 NP가 같은 집합인지 (즉, 해를 쉽게 검증할 수 있는 모든 문제는 해를 쉽게 찾을 수도 있는가?)는 아직 알려지지 않았습니다. 대부분의 컴퓨터 과학자들은 P $\ne$ NP라고 추측합니다. 분할 상환 분석 (Amortized Analysis) 일련의 자료 구조 연산(예: 스택의 push, pop, multi-pop; 동적 배열의 삽입)의 평균 비용을 분석하는 기법입니다. 단일 연산의 최악의 경우는 매우 비쌀 수 있지만, 전체 일련의 연산에 걸쳐 평균을 내면 비용이 훨씬 낮아지는 경우가 있습니다. 주요 방법: 총계 방법 (Aggregate method): $n$개의 연산 시퀀스에 대한 총 비용 $T(n)$을 계산한 다음, 이를 $n$으로 나누어 각 연산의 평균 비용 $T(n)/n$을 얻습니다. 회계 방법 (Accounting method): 각 연산에 "크레딧"을 할당합니다. 일부 연산은 실제 비용보다 더 많은 크레딧을 "벌고", 다른 연산은 "저축된" 크레딧을 사용하여 실제 비용보다 적은 크레딧을 "소비"합니다. 모든 연산에 대한 총 크레딧이 총 실제 비용보다 크거나 같아야 합니다. 잠재력 방법 (Potential method): 자료 구조의 "상태"를 나타내는 잠재력 함수 $\Phi(D_i)$를 정의합니다. $i$번째 연산의 실제 비용을 $c_i$, 자료 구조의 상태 변화에 따른 잠재력 변화를 $\Phi(D_i) - \Phi(D_{i-1})$이라고 할 때, 분할 상환 비용 $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$로 정의합니다. 초기 상태의 잠재력 $\Phi(D_0) = 0$이어야 합니다. 모든 $i$에 대해 잠재력 $\Phi(D_i) \ge 0$이어야 합니다. 예시: 동적 배열(vector, ArrayList)에 원소를 추가하는 경우. 대부분의 삽입은 $O(1)$이지만, 배열이 가득 차면 크기를 두 배로 늘리고 모든 원소를 복사하는 데 $O(N)$이 걸립니다. 분할 상환 분석을 사용하면 $N$번의 삽입에 대한 총 비용이 $O(N)$임을 보일 수 있으므로, 각 삽입의 분할 상환 비용은 $O(1)$이 됩니다. 문자열 매칭 (String Matching) 주어진 텍스트 $T$ 내에서 특정 패턴 $P$의 모든 발생을 찾는 문제입니다. 정보 검색, 생물정보학 등 다양한 분야에서 활용됩니다. 단순 알고리즘 (Naive Algorithm) 패턴 $P$를 텍스트 $T$의 모든 가능한 위치(쉬프트)에 대해 직접 비교합니다. 가장 직관적이지만 비효율적일 수 있습니다. 패턴 $P$의 길이 $m$, 텍스트 $T$의 길이 $n$. $i$는 텍스트 내에서 패턴이 시작할 수 있는 위치 ($0$부터 $n-m$까지). 각 위치 $i$에서 $P$의 모든 문자를 $T[i \dots i+m-1]$과 비교합니다. 시간 복잡도: 최악의 경우 $O((n-m+1)m)$, 즉 $O(nm)$. 예를 들어, $T = \text{`aaaaaaab`}$, $P = \text{`aaab`}$와 같이 거의 모든 문자가 일치하지만 마지막에 불일치하는 경우 발생합니다. 라빈-카프 알고리즘 (Rabin-Karp Algorithm) 해싱을 사용하여 패턴과 텍스트의 각 윈도우를 고유한 숫자로 변환한 후, 이 해시 값을 비교하여 일치를 빠르게 확인합니다. 해시 값이 일치하면 실제 문자열 비교를 수행하여 "스퓨리어스 히트(spurious hit)"를 방지합니다. 특정 소수 $q$를 사용하여 해시 값을 계산합니다. 롤링 해시(rolling hash) 기법을 사용하여 텍스트의 다음 윈도우 해시 값을 효율적으로 업데이트합니다. 시간 복잡도: 평균적으로 $O(n+m)$ (적은 스퓨리어스 히트 가정). 최악의 경우 (모든 해시 값이 일치하여 매번 문자열 비교가 필요한 경우) $O(nm)$. 크누스-모리스-프랫 (KMP) 알고리즘 패턴 내의 중복되는 정보를 활용하여, 텍스트에서 불일치가 발생했을 때 패턴을 효율적으로 "쉬프트"하여 재매칭에 필요한 비교 횟수를 최소화합니다. 이를 위해 패턴 자체에 대한 전처리 과정으로 접두어 함수 ($\pi$ 함수) 를 계산합니다. $\pi[q]$는 패턴 $P$의 접두어 $P_q$ (길이 $q$의 접두어) 중에서, $P_q$의 가장 긴 적절한 접두어 이면서 동시에 $P_q$의 접미어 인 부분 문자열의 길이입니다. 이 $\pi$ 함수는 불일치가 발생했을 때, 패턴을 얼마나 앞으로 (오른쪽으로) 쉬프트해야 할지 알려줍니다. KMP 접두어 함수 ($\pi$ 함수) 계산: function compute_prefix_function(P): m = P.length pi = array of size m // pi[q] stores the length for P[0...q] pi[0] = 0 // The prefix of length 1 (P[0]) has no proper prefix k = 0 // Length of the longest proper prefix of P[0...q-1] that is also a suffix of P[0...q-1] for q from 1 to m-1: // Compute pi[q] for q = 1, ..., m-1 while k > 0 and P[k] != P[q]: k = pi[k-1] // Mismatch, try shorter prefix if P[k] == P[q]: k = k + 1 // Match, extend prefix pi[q] = k return pi KMP 매칭 알고리즘: function kmp_matcher(T, P): n = T.length m = P.length pi = compute_prefix_function(P) // Preprocessing the pattern P q = 0 // Number of characters matched (length of the current prefix of P that matches a suffix of T) for i from 0 to n-1: // Scan the text T from left to right while q > 0 and P[q] != T[i]: q = pi[q-1] // Mismatch. Look for the next shorter prefix that could match if P[q] == T[i]: q = q + 1 // Match. Extend the matched prefix if q == m: // Pattern P occurs with shift i - m + 1 print "Pattern occurs with shift", i - m + 1 // To find subsequent occurrences, we don't start from scratch. // We know that pi[q-1] characters of P already match a suffix of T[0...i]. q = pi[q-1] 시간 복잡도: $\pi$ 함수 전처리에 $O(m)$, 매칭에 $O(n)$이 소요되어 총 $O(n+m)$입니다. 이는 최악의 경우에도 매우 효율적입니다. 계산 기하학 (Computational Geometry) 기하학적 문제를 해결하는 알고리즘을 연구하는 분야입니다. 점, 선, 다각형 등 기하학적 객체를 다룹니다. 볼록 껍질 (Convex Hull) 주어진 점들의 집합을 포함하는 가장 작은 볼록 다각형을 찾는 문제입니다. 결과는 보통 볼록 껍질을 구성하는 정점들을 반시계 방향으로 나열한 것입니다. 그레이엄 스캔 (Graham Scan): 주어진 점들 중 가장 낮은 Y 좌표를 가진 점 (동점일 경우 가장 작은 X 좌표)을 $p_0$로 선택합니다. $p_0$를 제외한 나머지 점들을 $p_0$를 기준으로 하는 극각(polar angle)의 오름차순으로 정렬합니다. 스택을 사용하여 볼록 껍질을 구성합니다. $p_0$와 $p_1$을 스택에 푸시합니다. 정렬된 점들을 순회하면서, 현재 점과 스택의 맨 위 두 점이 "비좌회전(non-left turn)"을 형성하는지 (즉, 볼록 껍질의 바깥쪽으로 꺾이는지) 확인합니다. 좌회전이 아니면 (우회전 또는 일직선), 스택의 맨 위 점을 팝하여 오목한 부분을 제거하고, 좌회전이 될 때까지 반복한 후 현재 점을 푸시합니다. 시간 복잡도: 정렬에 $O(n \log n)$, 스캔에 $O(n)$, 총 $O(n \log n)$. 자비스 행진 (Jarvis March, Gift Wrapping): 가장 낮은 Y 좌표를 가진 점 $p_0$를 시작점으로 선택합니다. 이 점은 반드시 볼록 껍질에 속합니다. 현재 볼록 껍질에 포함된 점 $p_{curr}$가 주어졌을 때, 다음 볼록 껍질 점 $p_{next}$를 찾습니다. $p_{next}$는 $p_{curr}$와 다른 모든 점 $p_i$를 연결하는 선분 중, $p_{curr}$를 시작점으로 하는 이전 볼록 껍질 모서리(또는 초기에는 양의 X축)에 대해 가장 작은 반시계 방향 각도를 형성하는 점입니다. 새로 찾은 $p_{next}$를 볼록 껍질에 추가하고, $p_{curr}$를 $p_{next}$로 업데이트합니다. 시작점 $p_0$에 다시 도달할 때까지 이 과정을 반복합니다. 시간 복잡도: $O(nh)$, 여기서 $n$은 총 점의 수, $h$는 볼록 껍질에 포함된 점의 수입니다. 최악의 경우 ($h=n$) $O(n^2)$이 될 수 있습니다. 가장 가까운 점 쌍 (Closest Pair of Points) $n$개의 점이 평면에 주어졌을 때, 유클리드 거리가 가장 작은 두 점의 쌍을 찾는 문제입니다. 이는 분할 정복(Divide and Conquer) 기법으로 $O(n \log n)$에 해결할 수 있습니다. 분할 정복 접근법: 주어진 점들을 X 좌표 기준으로 정렬한 리스트 $P_x$와 Y 좌표 기준으로 정렬한 리스트 $P_y$를 만듭니다. 점 집합 $P$를 중간 X 좌표를 기준으로 두 개의 절반 $P_L$과 $P_R$로 나눕니다. $P_L$과 $P_R$에서 재귀적으로 가장 가까운 점 쌍을 찾습니다. 이 과정에서 얻은 최소 거리들을 각각 $\delta_L, \delta_R$이라고 하고, $\delta = \min(\delta_L, \delta_R)$로 설정합니다. 이제 분할 선 $L$을 가로지르는 점 쌍 중에서 $\delta$보다 작은 거리를 갖는 쌍이 있는지 확인해야 합니다. 이를 위해, 분할 선 $L$의 양쪽에 $\delta$ 너비의 스트립($2\delta$ 폭) 안에 있는 점들만 고려합니다. 이 스트립 내의 점들을 Y 좌표 기준으로 정렬하여 리스트 $S_y$를 만듭니다. $S_y$의 각 점에 대해, 그 점으로부터 Y 좌표가 최대 $\delta$ 이내에 있는 점들만 확인합니다. 기하학적인 증명에 따라 각 점에 대해 최대 7개의 다음 점만 확인하면 됩니다. 이 세 가지 경우 (왼쪽 절반, 오른쪽 절반, 스트립)에서 찾은 최소 거리 중 가장 작은 값이 전체의 가장 가까운 점 쌍의 거리입니다. 시간 복잡도: $O(n \log n)$. NP-완전성 증명 (NP-Completeness Proofs) 특정 문제가 NP-완전임을 증명하는 것은, 그 문제가 NP 클래스 중에서 가장 "어려운" 문제 중 하나임을 보여주는 것입니다. 이는 문제의 본질적인 계산 복잡성을 이해하는 데 중요합니다. 문제 $X$가 NP-완전임을 증명하는 두 가지 주요 단계: $X \in NP$임을 보이기: 문제 $X$의 해답이 주어졌을 때, 이 해답이 올바른지 다항 시간 내에 검증할 수 있음을 보여줍니다. 즉, $X$는 NP 클래스에 속한다는 것을 증명합니다. $X$가 NP-난해임을 보이기: 이미 NP-완전임이 알려진 어떤 문제 $Y$를 문제 $X$로 다항 시간 환원($Y \le_P X$)할 수 있음을 보여줍니다. 이는 $X$를 해결하는 다항 시간 알고리즘이 있다면, 이를 사용하여 $Y$도 다항 시간 내에 해결할 수 있다는 의미입니다. 따라서 $X$는 $Y$만큼 어렵거나 더 어렵습니다. 일반적인 NP-완전 문제 다음은 컴퓨터 과학에서 가장 유명한 NP-완전 문제들 중 일부입니다. 이 문제들은 다른 많은 문제의 NP-완전성을 증명하는 데 환원(reduction)의 기반이 됩니다. SAT (Satisfiability - 만족 가능성): 주어진 부울 논리식(예: $(A \lor B \lor \neg C) \land (\neg A \lor C)$)이, 변수(A, B, C)에 참/거짓 값을 할당하여 전체 식을 참으로 만들 수 있는지 여부를 결정하는 문제입니다. 3-SAT: SAT의 특수한 경우로, 각 절(clause)이 정확히 3개의 리터럴(변수 또는 변수의 부정)을 포함하는 부울 논리식의 만족 가능성을 묻는 문제입니다. 3-SAT은 여전히 NP-완전입니다. 클리크 (Clique): 주어진 그래프 $G=(V,E)$와 정수 $k$에 대해, $G$가 크기가 $k$ 이상인 완전 부분 그래프(클리크)를 포함하는지 여부를 결정하는 문제입니다. 정점 커버 (Vertex Cover): 주어진 그래프 $G=(V,E)$와 정수 $k$에 대해, 모든 간선이 최소한 하나의 끝점에서 커버되는(포함되는) 정점 집합(정점 커버)이 크기가 $k$ 이하로 존재하는지 여부를 결정하는 문제입니다. 해밀턴 사이클 (Hamiltonian Cycle): 주어진 그래프 $G=(V,E)$가 모든 정점을 정확히 한 번씩 방문하고 시작점으로 돌아오는 사이클(해밀턴 사이클)을 포함하는지 여부를 결정하는 문제입니다. 외판원 문제 (Traveling Salesperson Problem, TSP): 도시 목록과 도시들 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하고 출발 도시로 돌아오는 가장 짧은 경로를 찾는 문제입니다. (최적화 버전은 NP-난해, 결정 버전은 NP-완전). 부분집합 합 (Subset Sum): 정수 집합 $S$와 목표 합 $T$가 주어졌을 때, $S$의 부분집합 중 원소들의 합이 $T$가 되는 것이 존재하는지 여부를 결정하는 문제입니다. 배낭 문제 (Knapsack Problem): 각 항목에 무게와 가치가 주어진 항목 집합과 최대 용량(무게)을 가진 배낭이 주어졌을 때, 배낭에 넣을 수 있는 항목들의 총 가치를 최대화하는 방법을 찾는 문제입니다. (결정 버전은 NP-완전).