🟣 부분문제가 겹치면 재계산이 폭발한다
분할정복은 문제를 쪼개 각각 풀고 합쳤다. 병합 정렬에서는 쪼갠 부분들이 서로 겹치지 않아 깔끔했다. 그런데 어떤 문제는 쪼개 보면 같은 부분문제가 여기저기서 되풀이해 나타난다. 이때 분할정복을 그대로 쓰면 같은 계산을 몇 번이고 다시 한다.
피보나치 수를 재귀로 구하는 코드가 극단적인 예다. fib(n)은 fib(n-1)과 fib(n-2)를 부르고, fib(n-1)은 다시 fib(n-2)와 fib(n-3)을 부른다. fib(n-2)가 벌써 두 번 계산된다. 아래로 내려갈수록 같은 값이 지수적으로 중복 호출되어 전체가 O(2ⁿ)이 된다. 앞 장에서 본 지수의 벽에 정면으로 부딪히는 것이다.
해법은 단순하다. 한 번 푼 부분문제의 답을 어딘가 적어 두고, 다시 필요하면 계산 대신 꺼내 쓴다. 이 발상이 동적 프로그래밍(DP)이다.
🟣 DP가 성립하는 두 조건
아무 문제에나 DP를 쓸 수 있는 건 아니다. 두 조건이 맞아야 한다.
첫째는 중첩 부분문제다. 같은 부분문제가 여러 번 나와야 저장해서 얻는 이득이 있다. 부분문제가 매번 새것이면 저장할 이유가 없고, 그건 그냥 분할정복이다.
둘째는 최적 부분구조다. 큰 문제의 최적해가 작은 부분문제의 최적해로 조립돼야 한다. 부분문제를 최적으로 풀어도 그게 전체 최적으로 이어지지 않으면 DP의 전제가 무너진다.
이 두 조건이 맞으면 부분문제의 답을 채우는 방식은 두 갈래다.
하향식은 재귀 구조를 그대로 두되 이미 계산한 값을 저장(메모이제이션)해 중복 호출을 막는다. 상향식은 가장 작은 부분문제부터 표를 채워 올라간다. 둘 다 각 부분문제를 한 번씩만 풀어 지수 시간을 다항 시간으로 끌어내린다. 피보나치라면 O(2ⁿ)이 O(n)으로 내려간다.
🟣 LCS: 두 수열의 공통 뼈대
DP의 감을 잡기 좋은 예가 최장 공통 부분 수열(LCS)이다. 두 문자열에서 순서를 지키되 연속일 필요는 없이 뽑을 수 있는 가장 긴 공통 수열을 찾는 문제다. "ABCBDAB"와 "BDCAB"의 LCS는 "BCAB"으로 길이 4다. 이 문제는 파일 비교(diff)나 DNA 서열 정렬의 뼈대이기도 하다.
핵심은 점화식이다. 두 문자열의 앞에서부터 i, j번째까지 봤을 때의 LCS 길이를 L[i][j]라 두면, 두 문자의 마지막 글자를 비교해 이렇게 정한다.
- 두 글자가 같으면
L[i][j] = L[i-1][j-1] + 1. 공통 글자 하나를 더 잇는다. - 다르면
L[i][j] = max(L[i-1][j], L[i][j-1]). 한쪽 글자를 포기한 두 경우 중 더 긴 쪽을 택한다.
이 점화식대로 표를 채우면 답이 나온다. 표 크기가 두 문자열 길이의 곱이라 복잡도는 O(mn)이다. 재귀로 그냥 풀면 지수인 문제가, 부분문제의 답을 2차원 표에 적어 두는 것만으로 다항으로 내려온다. DP가 왜 강력한지 한 번에 보이는 예다.
🟣 연쇄 행렬 곱: 순서만 바꿔도 비용이 달라진다
DP가 더 극적으로 통하는 문제가 연쇄 행렬 곱이다. 행렬 여러 개를 곱할 때, 곱셈의 결과는 괄호를 어떻게 치든 같지만 연산 횟수는 괄호 위치에 따라 크게 달라진다. 10×100, 100×5, 5×50 세 행렬을 곱할 때 앞에서 묶으면 7,500번, 뒤에서 묶으면 75,000번의 스칼라 곱셈이 든다. 열 배 차이다.
행렬이 많아지면 가능한 괄호 조합이 지수적으로 늘어 전부 시도할 수 없다. 여기서 최적 부분구조가 보인다. 전체 곱의 최적 괄호는 어딘가 한 지점에서 둘로 갈리고, 그 양쪽도 각각 최적으로 괄호가 쳐져 있어야 한다. 그래서 "구간 [i, j]를 곱하는 최소 비용"을 부분문제로 두고, 가르는 지점 k를 모두 시도해 최솟값을 택한다. 짧은 구간부터 표를 채워 올리면 O(n³)에 최적 괄호가 나온다. 지수를 다항으로 누르는 이 승리가 DP의 전형이다.
🟣 그리디: 되돌아보지 않고 지금 최선을 택한다
DP는 모든 부분문제를 따져 최적을 조립한다. 그런데 어떤 문제는 그렇게까지 안 해도 된다. 매 순간 눈앞의 최선만 골라도 전체 최적에 도달하는 경우가 있다. 이렇게 국소 최적을 계속 택하는 방식이 그리디다.
거스름돈 문제가 익숙한 예다. 한국 동전 체계(500, 100, 50, 10)에서는 큰 동전부터 최대한 많이 내는 그리디가 항상 최소 개수를 낸다. 그리디가 통하려면 그리디 선택 속성이 있어야 한다. 지금의 국소 최적 선택이 전체 최적해의 일부가 됨이 보장돼야 한다는 뜻이다. 이게 없으면 그리디는 틀린 답을 낸다. 동전이 (1, 3, 4)처럼 생기면, 6원을 만들 때 그리디는 4+1+1로 세 개를 쓰지만 최적은 3+3으로 두 개다.
🟣 DP를 쓸까 그리디를 쓸까
둘의 경계는 배낭 문제에서 선명하다. 물건마다 무게와 가치가 있고 가방 용량이 정해졌을 때 가치 합을 최대로 담는 문제다. 물건을 쪼개 담을 수 있는 분할 배낭은 그리디로 풀린다. 단위 무게당 가치가 높은 것부터 담으면 최적이다. 반면 쪼갤 수 없는 0-1 배낭은 그리디가 틀린다. 단위 가치가 높아도 그걸 담으면 더 좋은 조합을 놓칠 수 있기 때문이다. 0-1 배낭은 DP로 풀어야 한다.
정리하면 그리디가 통하는지 먼저 따지고, 그리디 선택 속성이 증명되면 그리디를 쓴다. 대개 더 빠르고 단순하기 때문이다. 증명이 안 되면 DP로 물러나 모든 부분문제를 따진다. 그리디는 통할 때 우아하지만 통하는지 증명하지 못하면 위험하다는 점이 이 둘을 가르는 실전 감각이었다.
🟣 정리
- 부분문제가 겹치면 분할정복은 같은 계산을 지수적으로 반복한다. 답을 저장해 재사용하는 것이 동적 프로그래밍이다.
- DP는 중첩 부분문제와 최적 부분구조가 있어야 성립한다. 하향식 메모이제이션과 상향식 표 채우기 두 방식이 있다.
- LCS는 2차원 표로, 연쇄 행렬 곱은 구간 DP로 지수 시간을 다항으로 끌어내린다. 부분문제의 답을 적어 두는 것만으로 승부가 갈린다.
- 그리디는 매 순간 국소 최적을 택한다. 빠르고 단순하지만 그리디 선택 속성이 증명될 때만 옳다.
- 같은 배낭 문제도 분할 가능하면 그리디, 0-1이면 DP다. 그리디가 통하는지부터 따지고 안 되면 DP로 물러나는 것이 실전 순서다.
DP와 그리디는 코딩 테스트와 면접에서 가장 자주 나오는 주제다. "이 문제를 그리디로 풀면 반례가 있나요"라는 질문에 반례를 만들거나 정당성을 논증하는 능력이 곧 실력으로 읽힌다. 지금까지는 배열과 수열을 다뤘다. 다음 장은 노드와 간선으로 얽힌 관계, 그래프 알고리즘이다.