📚 지식 노트

분할 정복: 나눠서 풀고 합친다

분할 정복(divide and conquer)은 문제를 같은 모양의 작은 문제 몇 개로 나누고(분할), 각각을 같은 방법으로 풀고(정복), 답을 합친다(결합). 작은 문제가 충분히 작아지면 바로 푼다. 정렬 노트의 병합 정렬과 퀵 정렬, 이진 탐색이 모두 이 틀이다.

걸리는 시간은 재귀 트리(recursion tree)를 그려 보면 보인다. 병합 정렬은 크기 n인 문제를 n/2 두 개로 나누고 합치는 데 n만큼 일한다. 식으로 쓰면 T(n) = 2T(n/2) + n이다. 깊이가 하나 내려갈 때마다 문제 수는 두 배, 크기는 절반이라 줄마다 일의 합이 n으로 같고, 줄이 log₂ n + 1개 있으니 전체는 O(n log n)이다.

마스터 정리(master theorem)는 T(n) = a·T(n/b) + f(n) 꼴을 한 번에 푸는 공식이다. 외우기보다 “줄마다 일이 어떻게 변하나”로 이해하면 쉽다. 한 줄 내려갈 때 호출은 a배, 크기는 1/b배가 된다. 그 결과 줄의 일이 깊이마다 줄어들면 맨 위 한 번이 전체를 정하고, 같으면 줄 수(log n)만큼 곱해지고, 늘어나면 맨 아래 잎(n^(log_b a)개)이 전체를 정한다.

• 나누는 수를 줄이면 빨라진다: 큰 수 두 개를 반으로 나눠 곱하면 작은 곱셈이 넷 필요하지만, 카라츠바 곱셈은 덧셈을 조금 더 해서 셋으로 줄인다. a가 4에서 3이 되자 O(n²)이 O(n^1.585)로 내려간다.
• 대가: 재귀 호출과 임시 공간의 비용이 있어 문제가 작을 때는 단순한 방법이 낫다. 그래서 실무 구현은 일정 크기 아래에서 단순한 방법으로 바꾼다(정렬의 삽입 정렬 전환).
• 쓰임: 나뉜 문제끼리 서로 기다리지 않으니 병렬로 돌리기 좋다. 고속 푸리에 변환(FFT), 가장 가까운 두 점 찾기, 큰 데이터를 나눠 처리하고 합치는 맵리듀스가 같은 생각이다.

세 경우의 정확한 조건은 Wikipedia의 Master theorem 문서에 있다.

문제 풀기 →Python 코드 →

동적 계획법: 한 번 푼 것은 기억한다

분할 정복으로 나눈 작은 문제들이 서로 겹치면 같은 계산을 몇 번이고 다시 한다. 피보나치 수 f(n) = f(n-1) + f(n-2)를 그대로 재귀로 짜면 f(5) 하나에 호출이 15번 일어나고, n이 하나 늘 때마다 호출이 약 1.6배씩 늘어난다. 서로 다른 인자는 f(0)~f(5) 여섯 개뿐인데도 그렇다.

동적 계획법(dynamic programming, DP)은 작은 문제의 답을 표에 적어 두고 다시 쓰는 방법이다. 두 조건이 맞아야 쓸 수 있다. 큰 문제의 최적해가 작은 문제의 최적해로 만들어지고(최적 부분 구조), 같은 작은 문제가 여러 번 나와야(겹치는 부분 문제) 한다. 표를 채우는 방향에 따라 둘로 나뉜다.

• 메모이제이션(memoization, 위에서 아래로): 재귀 코드는 그대로 두고, 계산한 답을 표에 적었다가 같은 인자가 오면 표에서 꺼낸다. 필요한 칸만 계산하고 코드가 점화식과 닮아 쓰기 쉽다. 대신 재귀가 깊으면 호출 스택이 넘칠 수 있다. Python의 functools.cache가 이 방식이다.
• 타뷸레이션(tabulation, 아래에서 위로): 가장 작은 문제부터 반복문으로 표를 채운다. 재귀가 없어 빠르고, 이전 줄만 필요하면 표를 한두 줄로 줄여 메모리를 아낄 수 있다. 대신 채울 순서를 직접 정해야 한다.

대표 예가 0/1 배낭 문제(knapsack)다. 무게와 가치가 있는 물건들 중 무게 한도 안에서 가치 합이 가장 크게 고른다. 물건마다 넣을지 말지 두 가지라 다 시험하면 2ⁿ가지지만, “물건 1~i만 써서 한도 w로 낼 수 있는 최대 가치”를 칸으로 삼으면 칸마다 두 칸만 보고 채울 수 있다.

best[i][w] = best[i-1][w]                                   # 물건 i를 뺀다
if weight[i] <= w:
  best[i][w] = max(best[i][w], best[i-1][w - weight[i]] + value[i])   # 넣는다

• 복잡도: 칸이 (물건 수 n + 1) × (한도 W + 1)개이고 칸마다 O(1)이라 O(nW)다. W가 숫자의 크기라서 W를 적는 자릿수에 대해서는 지수 시간이다(의사 다항 시간). 배낭 문제는 일반적으로 어려운 문제(더 나아가기 노트의 NP-난해)이고, 한도가 작을 때만 이 표가 빠르다.
• 답 되짚기: 표에는 최댓값만 있다. 어떤 물건을 골랐는지는 오른쪽 아래에서 거꾸로 올라가며, 값이 위 칸과 다르면 그 물건을 넣은 것으로 보고 그 무게만큼 왼쪽으로 옮겨 찾는다.
• 쓰임: 두 글의 최장 공통 부분 수열(LCS)과 문자열 노트의 편집 거리, 그래프 노트의 벨만-포드·플로이드-워셜 최단 경로, 문장을 단어로 나누기, 자원 배분 같은 최적화 문제가 모두 같은 틀이다.

비트마스크 DP는 "지금까지 무엇을 골랐나"가 상태일 때 그 집합을 정수 하나의 비트로 적는다. 외판원 문제라면 g(S, e)를 "출발 도시에서 시작해 집합 S의 도시를 모두 거쳐 e에서 끝나는 가장 짧은 길"로 두고, e 바로 앞에 들른 도시를 S에서 하나씩 빼 보며 채운다. 도시가 n개면 집합 2ⁿ개 × 끝 도시 n개이고 칸마다 n개를 보니 O(n²·2ⁿ)이다(벨먼–헬드–카프 알고리즘, 1962). n = 20이면 모든 순서 20! ≈ 2.4 × 10¹⁸가지 대신 약 4.2억 번으로 줄지만, 여전히 지수 시간이라 n이 20 안팎일 때만 쓴다. 집합 연산은 비트 연산 한 번이다. i번이 들었는지는 S & (1 << i), 넣기는 S | (1 << i)다.

배낭 문제의 변형(개수 제한 없는 배낭, 한 줄짜리 표로 줄이기)은 cp-algorithms의 Knapsack Problem에 정리돼 있다.

문제 풀기 →Python 코드 →

탐욕법: 지금 가장 좋아 보이는 것을 고른다

탐욕법(greedy algorithm)은 단계마다 지금 가장 좋아 보이는 선택을 하고 되돌아보지 않는다. 표도 재귀도 없어 빠르고 짧다. 거스름돈을 줄 때 큰 동전부터 내는 것이 대표적이다.

문제는 늘 맞지는 않는다는 것이다. 탐욕이 최적해를 내려면 “지금의 탐욕 선택을 포함하는 최적해가 반드시 있다”(탐욕 선택 속성)는 것과 최적 부분 구조가 함께 성립해야 하고, 이건 문제마다 증명해야 한다. 흔한 증명 방법은 바꿔치기 논법(exchange argument)이다. 최적해가 탐욕과 다른 선택을 했다면 그것을 탐욕의 선택으로 바꿔도 손해가 없음을 보인다.

• 탐욕이 맞는 문제: 회의실 하나에 회의를 가장 많이 넣기(끝나는 시간이 가장 이른 회의부터 고르기), 허프만 부호화, 그래프 노트의 다익스트라 최단 경로와 크루스칼·프림 최소 신장 트리.
• 틀리는 문제: 0/1 배낭(가치 대비 무게가 좋은 것부터 담으면 틀릴 수 있다), 임의의 동전 체계의 거스름돈. 물건을 쪼갤 수 있는 배낭이라면 탐욕이 맞는다.
• 근사로 쓰기: 최적을 보장하지 못해도 충분히 가까운 답을 빨리 낸다면 쓸 만하다. 어려운 문제의 근사 알고리즘이 대개 탐욕이다(더 나아가기 노트).

어떤 동전 체계에서 탐욕이 최적인지는 그 자체로 연구 주제다. Wikipedia의 Change-making problem 문서가 이 질문과 동적 계획법 풀이를 함께 다룬다.

문제 풀기 →Python 코드 →

백트래킹: 해 보고, 막히면 되돌아간다

답이 선택의 나열이고 그 조합이 너무 많을 때, 하나씩 골라 나가다가 규칙에 어긋나는 순간 그 갈래를 버리고 직전 선택으로 되돌아가는 방법이 백트래킹(backtracking)이다. 모든 조합을 깊이 우선으로 훑되, 가망 없는 갈래는 끝까지 가 보지 않고 일찍 잘라낸다(가지치기, pruning).

N-Queens는 N×N 판에 퀸 N개를 서로 공격하지 않게 놓는 문제다. 한 행에 하나씩 놓는다고 정하면 행마다 열만 고르면 된다. 4×4에서 모든 배치는 4⁴ = 256가지지만, 놓는 순간 부딪치는지 보면 훨씬 적게 시도하고 첫 해에 닿는다.

place(row):
  if row == N: 해를 찾았다
  for col in 0..N-1:
    if 안전(row, col):           # 같은 열·대각선에 퀸이 없다
      퀸을 놓는다; place(row + 1); 퀸을 거둔다

• 복잡도: 최악에는 여전히 지수 시간이다. 가지치기는 최악의 차수를 바꾸지 못하지만, 실제로 훑는 갈래를 크게 줄인다. 8-Queens의 해는 92개다.
• 더 잘 자르기: 열과 두 방향 대각선이 쓰였는지를 배열(또는 비트)로 들고 다니면 “안전한가?”를 O(1)에 답한다. 선택지가 가장 적은 칸부터 채우면 막다른 길을 더 빨리 만난다.
• 쓰임: 스도쿠, 낱말 퍼즐, 일정 짜기 같은 제약 만족 문제, SAT 풀이기의 기본 틀이다. 최적화 문제에서 “지금까지 찾은 최선보다 나아질 수 없는 갈래”를 자르면 분기 한정(branch and bound)이 된다.

해의 개수와 대칭을 뺀 기본 해, 다른 풀이법은 Wikipedia의 Eight queens puzzle 문서에 있다.

문제 풀기 →Python 코드 →

두 포인터와 슬라이딩 윈도

배열에서 “조건을 만족하는 쌍”이나 “조건을 만족하는 구간”을 찾을 때, 모든 쌍을 보면 O(n²)이다. 정렬돼 있거나 값이 모두 양수처럼 단조로운 성질이 있으면, 인덱스 두 개를 한 방향으로만 움직여 O(n)에 끝낼 수 있다.

두 포인터(two pointers): 정렬된 배열의 양 끝에 L과 R을 두고, 합이 목표보다 작으면 L을 오른쪽으로, 크면 R을 왼쪽으로 옮긴다. 합이 작으면 L은 남은 어떤 칸과 짝지어도 목표에 못 미친다(남은 칸 중 R이 가장 크다). 그래서 L을 버려도 답을 놓치지 않는다. 합이 클 때의 R도 마찬가지다.

슬라이딩 윈도(sliding window): 두 인덱스를 같은 방향으로 움직여 연속 구간(창)을 유지한다. 오른쪽 끝을 늘리며 값을 더하고, 조건이 깨지면 왼쪽 끝을 줄이며 값을 뺀다. 창의 합을 매번 새로 더하지 않고 들어온 값과 나간 값만 반영하는 것이 핵심이다.

• 조건: 창을 줄이면 조건이 반드시 좋아져야 한다(값이 모두 양수인 합처럼). 음수가 섞이면 줄여도 합이 커질 수 있어 이 방법이 틀린다. 그때는 누적합과 해시나 정렬을 쓴다.
• 누적 합(prefix sum): P[0] = 0, P[i + 1] = P[i] + a[i]를 한 번 만들어 두면 구간 a[l..r]의 합은 P[r + 1] − P[l]로 O(1)이다. 음수가 섞여 창을 못 쓸 때 "합이 k인 연속 구간의 개수"는 왼쪽부터 P를 만들며 지금까지 나온 P 값의 개수를 해시 표에 세어 두고, 매번 P − k가 몇 번 나왔는지 더하면 O(n)에 센다.
• 변형: 고정 길이 창(최근 k개의 평균), 서로 다른 글자만 담은 가장 긴 부분 문자열, 두 정렬된 목록 합치기, 빠른·느린 포인터로 연결 리스트의 고리 찾기가 모두 같은 틀이다.
• 쓰임: 최근 1분 동안의 요청 수로 속도를 제한하는 서버, 이동 평균으로 값을 부드럽게 만드는 센서·주식 차트, 프레임 시간의 최근 평균을 보여 주는 게임 성능 그래프가 창을 민다.

문제 풀기 →Python 코드 →