[코드트리 후기] 6주차, Dynamic Programming 개념 정리
이번 블로그에서는 최근에 코드트리에서 공부했던 Dynamic Programming 기법을 쭉 정리해보려고 한다.
Memoization의 힘
피보나치 수열을 출력하는 프로그램을 재귀 함수만으로 한번 만들어보자.
프로그래밍을 열심히 공부했다면, 이 정도는 어렵지 않게 구현할 수 있다.
그런데 한가지 문제가 있다. 위 프로그램에 50을 집어넣으면 너무 오래 걸려서 결과가 출력되질 않는다.
각 fibonacci 함수는 내부에서 fibonacci 함수를 2회 호출한다. 그럼 내부에서 실행된 fibonacci 함수는 또다시 fibonacci 함수를 2회 호출하고, 그 과정이 계속해서 반복된다. n이 2 이하가 될 때까지 n을 1씩 빼면서 재귀적으로 호출할 테니, 함수의 전체 깊이는 n - 1이 된다.
그림으로 그려보면 훨씬 직관적으로 와닿는다.
따라서 이 코드는 O(2^n)의 시간 복잡도를 갖는다고 볼 수 있다. 코드트리의 시간복잡도 챕터를 공부했다면, 이는 말도 안되는 시간복잡도임을 바로 알 수 있다. n이 30 정도만 되어도 2^30 = 1,073,741,824으로 fibonacci 함수의 호출 횟수가 10억회를 돌파한다!
그런데 그림을 그려보면 직관적으로 보이는 것이 하나 있다. 이 그림에는 반복되는 노드가 너무 많다. 예를 들어서, F(3)은 이 그림에서 3번 등장했다.
그리고 곰곰히 생각해 보면, 이 함수가 이렇게 끔찍한 시간복잡도를 갖는 원인은 이렇게 중복되는 노드를 계속해서 계산하기 때문이다. N이 커질수록 F(3)은 2^n에 비례하는 횟수만큼 실행될 것이다.
그렇다면 F(3)을 이미 한번 계산했으니, F(3)의 결과를 저장해놓고 F(3)이 필요할 때마다 그냥 저장된 결과를 반환시킬 수 있지 않을까?
이것이 바로 Memoization이다. 프로그램의 실행 과정에서 프로그램이 동일한 문제를 다시 마주쳤을 때, 문제를 다시 계산하지 않고 이미 저장된 결과를 그대로 반환하여 중복되는 문제를 O(1)의 시간에 내놓는다. 백엔드 공부를 좀 해봤다면 마주쳤을 캐싱 기법과 동일한 원리다.
이제 이 아이디어를 fibonacci 함수에 적용해보자. 코드를 아래와 같이 개선할 수 있다.
이제 코드를 실행해보면 큰 수를 입력해도 엄청 빠르게 계산된다! 아까의 그림을 위 코드 구조를 반영하여 다시 한번 살펴보자.
반복되는 노드구조가 사라지고 전체적으로 아주 깔끔하게 변한 걸 볼 수 있다. 아까는 총 15회의 함수 호출이 발생했지만 이젠 9회의 함수 호출로 줄어들었다. n이 더 크다면 그 수치는 훨씬 드라마틱하게 변한다.
Memoization 덕분에 이제 위 코드는 O(n)이라는 적은 시간 복잡도를 자랑한다.
문제를 중복되는 문제로 작게 쪼개기
Memoization은 강력하지만, Memoization을 쓰기 위해 필요한 조건은 "문제를 중복되는 문제로 쪼개는 것"이다.예시를 통해서 문제를 어떻게 쪼개는지 살펴보자.
위 문제에서 만약 1, 2, 5 이렇게 3종류의 동전이 주어졌고, 11을 동전 갯수를 최소로 하여 만들어야 한다고 할 때, 문제를 어떻게 쪼갤 수 있을까?
F(n)을 n을 만들 수 있는 최소 동전의 갯수를 반환하는 함수라고 해보자. 그러면
- 1원을 넣는 케이스: F(10) + 1
- 2원을 넣는 케이스: F(9) + 1
- 5원을 넣는 케이스: F(6) + 1
라고 할 때, 이 세가지 값 중 최소가 되는 값을 선택할 수 있을 것이다. 그리고 그 값이 F(11)이 될 수 있을 것이라고 유추해 볼 수 있다.
이를 점화식으로 나타내면 아래와 같다.
이것도 아까 피보나치 함수처럼 아래와 같은 재귀 트리를 만들 수 있다. 중간 중간에 반복되는 노드가 있으니 Memoization을 적용할 수 있다는 사실을 쉽게 확인할 수 있다.
참고로 여기서 F(10), F(9), F(6)과 같이 F(11)을 푸는데 사용된 쪼개진 문제들을 Subproblem이라고 한다.
위 방식을 응용하여 문제를 풀이하는 코드는 아래와 같다.
Top-down과 Bottom-up 방식
지금까지는 재귀 함수에서의 Memoization을 살펴봤다. 그런데 위 점화식을 다시 곰곰이 생각해 보면, 재귀를 사용해서 n에서 초기값까지 내려가는 방법 말고도, 초기값에서 n으로 올라가는 방법을 생각해 볼 수 있다.
다시 1, 2, 5의 동전으로 11을 만드는 케이스를 생각해보자.
F(0)은 초기 값 0로 고정되어 있으니 F(1)부터 시작한다.
F(1)은 F(1 - 1) + 1, F(1 - 2) + 1, F(1 - 5) + 1 셋 중 가장 작은 값을 고를 수 있는데, F(0) + 1을 제외하면 나머지는 범위를 벗어나므로 F(1)을 1로 채워줄 수 있다.
F(2)는 F(2 - 1) + 1, F(2 - 2) + 1, F(2 - 5) + 1 셋 중 가장 작은 값을 고를 수 있고, F(1) + 1, F(0) + 1만 가능하다. 둘 중 작은 값은 F(0) + 1이므로 다시 1로 채워준다.
이런 식으로 이 과정을 F(11)까지 반복하면, F(11)에 아까와 동일하게 최소 동전 개수가 담기게 된다. 이제 F(11)을 반환하면 된다.
코드로 나타내면 아래와 같다.
재귀 함수처럼 n에서 내려가는 방식을 Top-down 방식이라고 하고, 지금의 배열 방식처럼 n까지 채워나가는 것을 Bottom-up 방식이라고 한다. (Bottom-up 방식은 표를 채워나간다고 해서 Tabulation이라고 부르기도 한다.)
보통은 DP 문제를 풀 때는 Bottom-up 방식이 선호되는 편인데, 가끔 Top-down 방식이 필요한 경우가 있으므로 상황에 따라 둘 다 구현할 수 있도록 연습해 두는 게 좋다.
Dynamic Programming
이렇게 해서 Memoization과 Subproblem으로 쪼개는 방법에 대해서 알아보았다. 문제를 더 작은 Subproblem으로 쪼개고, 중복되는 Subproblem들을 Memoization을 활용하여 쳐내어 문제를 푸는 기법을 Dynamic Programming (동적 계획법)이라고 한다.
DP는 적절한 점화식만 세울 수 있다면 정말 많은 문제에서 활용할 수 있다. 최근에 봤던 독특했던 DP 풀이는 n개의 올바른 괄호를 가진 문자열을 모두 출력하는 문제를 DP로 풀어낸 풀이였다. (문자열의 개수를 출력하는 게 아니라 모든 가능한 문자열을 출력하는 것이다!)
하지만 DP는 중요한 조건이 몇 개 있다.
- 중복되는 Subproblem이 존재해야 한다.
- Subproblem의 최적 해들로 Problem의 최적 해를 도출할 수 있어야 한다.
왜 중요한 조건인지 하나씩 살펴보자.
중복되는 Subproblem이 존재해야 한다
좋은 예시로 merge sort를 살펴보자. merge sort는 하나의 큰 배열을 계속해서 반으로 쪼개서 풀어내니까, merge sort도 하나의 큰 Problem을 작은 Subproblem을 이용해 풀어내는 과정이 담겨있다. 하지만 merge sort의 풀이법을 DP라고 부르지 않는다. 그 이유는 Subproblem이 중복되지 않기 때문이다.
merge sort는 이미 있는 배열을 반으로 쪼개고, 또 반으로 쪼개진 배열을 다시 반으로 쪼갠다. 이 과정을 계속 거쳐서 배열의 원소가 1개가 될 때까지 쪼개고, 그때부터 배열을 정렬해서 합쳐나간다. 문제는 배열을 쪼개는 과정에서 "이미 subarray를 정렬했었던 케이스"가 전혀 존재하지 않는다. merge sort 함수를 재귀적으로 호출할 때 아직 한 번도 정렬하지 않은 배열만 계속해서 던져준다.
DP의 핵심은 중복되는 subproblem을 memoization을 사용하여 이미 계산된 부분을 쳐내는 것에 있다. merge sort는 problem을 subproblem으로 쪼갤 수는 있지만 subproblem이 중복되지 않으므로 memoization을 사용할 수 없고, 따라서 DP라고 할 수 없다.
참고로 이렇게 problem을 subproblem으로 쪼개었지만 subproblem이 중복되지 않는 경우는 분할 정복(Divide and conquer)이라고 부른다.
Subproblem이 Problem을 해결해야 한다
아래 문제를 살펴보자.
위 문제의 풀이 방법을 한번 생각해 보자. 내가 처음에 생각해 본 아이디어는 아래와 같다.
간단하게 설명하자면, DP[x][y]를 (x, y) 칸에서 max-min 값을 최소로 하는 경로의 (min, max) 쌍으로 정의했다.
그리고 (x - 1, y)에서 (x, y)로 이어지는 경로 a와 (x, y - 1)에서 (x, y)로 이어지는 경로 b가 있을 때, a의 max-min 값과 b의 max-min 값을 비교하고 값이 최소가 되는 경로를 선택하여 (min, max) 쌍을 DP[x][y]에 집어넣는다.
뭔가 괜찮은 것 같고 예제 케이스도 통과하지만, 아래와 같은 반례가 있다.
두 케이스 모두 문제는 (3, 3) 지점에 도달하면서 시작된다.
(3, 3)에서 (3, 2) 혹은 (2, 3) 중에서 하나를 골라야 하는데, 둘 다 max - min의 값이 2로 동일하다. 이때 코드가 왼쪽 경로 min 5, max 7을 골랐다면 왼쪽 케이스에서 잘못된 답을, 위쪽 경로 min 3, max 5를 골랐다면 오른쪽 케이스에서 잘못된 답을 반환한다.
그러므로 이 풀이 방법은 Subproblem의 최적해가 상위 Problem의 최적해를 구할 수 없으므로 올바른 DP 풀이로 볼 수 없다.
그래서 다시 한번 머리를 굴려보면, 이 문제에서 필요한 상태값은 현재 좌표, 경로의 min값, 경로의 max값 이렇게 3가지다. 만약 처음부터 min 값을 5로 제한했다면 어떨까? 즉, 경로를 탐색할 때 무조건 5보다 큰 칸만 밟을 수 있다고 조건을 걸고 탐색하는 것이다.
그럼 탐색할때 지금까지 지나온 경로의 (min, max) 값을 복잡하게 고려할 것 없이, 탐색할 때 무조건 5보다 큰 칸 중에 가장 작은 칸만 계속 밟으며 최댓값을 최소로 유지하면 된다. 이러면 오른쪽 케이스에서 최적의 해를 찾을 수 있다. 반대로, min 값을 1로 제한했다면 마찬가지로 무조건 작은 수만 밟으며 경로를 탐색하는데, 이 때는 왼쪽 케이스에서 최적의 해를 찾을 수 있다.
이렇게 min 값을 고정한다는 아이디어를 전체 범위로 확장할 수 있다. 칸에 들어갈 수 있는 모든 숫자들을 한 번씩 min 값으로 고정하고 모든 타일을 순회하는 것이다. 마침 문제의 조건에도 모든 칸에는 1~100 사이의 정수만 들어갈 수 있다고 했으니 TLE가 발생할 우려도 없다.
이는 DP 배열에 하나의 상태를 추가하고 3차원으로 확장하여 정의할 수 있다. DP[x][y][min] 를 "min보다 큰 숫자만을 사용하여 x, y 타일에 도달하는 경로 중 타일의 최댓값이 가장 최소가 되는 값"으로 정의한다. 그리고 이제 DP[n][n][min]의 값을 갱신할 때마다 answer 변수에 max - min의 최소 값을 기록하면 된다. 이러면 Subproblem으로 Problem의 최적해를 구할 수 있다.
이처럼 과거에 골랐던 선택이 미래에 최적의 선택을 하는데 영향을 끼친다면, DP 배열에 상태가 빠졌다는 신호일 수 있다. 점화식을 세우기 전에 문제에서 어떤 상태들이 있는지 미리 정리해 보는 습관을 들여두면 좋다.
마치며
나는 DP가 아직도 조금 까다롭다고 생각한다. 간단한 DP 문제는 여러 번 풀어봐서 괜찮을지 몰라도 DP 문제에는 정말 다양한 유형이 있고, 처음 보는 유형은 점화식을 어떻게 세워야 할지 감이 안 잡힐 때도 많다.
하지만 코딩테스트에서 만나는 DP는 결국 이미 봤었던 문제를 조금만 비틀어서 내는 경우가 대부분이다. 코드트리에서 다양한 유형의 문제를 꾸준히 풀어나가며 점점 DP를 정복해 나가면 당당하게 풀어낼 수 있는 자신감을 얻을 수 있을 것이다.
▼ 코드트리 청약 통장 챌린지 참여하기
https://www.codetree.ai/ko/no-free-lunch-2026/?ref=NKJVVB
#코드트리 #코딩테스트 #코테공부 #DP #다이나믹프로그래밍