1. Dynamic Programming 이란?
DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은동적 프로그래밍은 "큰 문제"를 "부분 문제"로 나누고 "부분 문제"의 정답으로 "큰 문제"의 해답을 찾아가는 알고리즘 설계 기법이다.
Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경 쓰지 않아도 된다.
큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 이 방식을 그래서 DP 보다는 '기억하며 풀기'라고 부르면 더 직관적일 것 같다.
2. DP를 쓰는 이유?
왜 DP를 사용할까? 일반적인 재귀(Naive Recursion) 방식을 사용하는 것도 DP와 매우 유사하게 느껴진다. 하지만 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다.
피보나치 수열을 예로 들어 동적 프로그래밍을 설명하려 한다.
다음은 피보나치 수열의 점화식이다.
점화식으로부터 알 수 있는 것은 피보나치 수열은 재귀적인 관계를 가지고 있다는 것이다.
즉 F(N)은 F(N-1)과 F(N-2)에 의해서 결정된다.
코드에 가깝게 표현하면 다음과 같다.
F[1] = 1;
F[2] = 1;
F[i] = F[i - 1] + F[i - 2];점화식으로부터 알 수 있는 것은 피보나치 수열은 재귀적인 관계를 가지고 있다는 것이다.
즉 F(N)은 F(N-1)과 F(N-2)에 의해서 결정된다.
피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 어떻게 될까? 단순하다. return f(n) = f(n-1) + f(n-2)
그런데 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수 적으로 증가한다.(약 7해, #,###경 #,###조 ... 번 이상 함수 호출, 컴퓨터도 죽는다.)
왜냐하면, f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 되기 때문이다.
그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 한다면 어떨까? 앞에서 계산된 값을 다시 반복할 필요가 없이 약 200회 내에 계산이 가능해진다.
즉, 매우 효율적으로 문제를 해결할 수 있게 된다.
시간복잡도를 기준으로 아래와 같이 개선이 가능하다.
O(n^2) → O(f(n)) 로 개선 (다항식 수준으로, 문제에 따라 다름.)
3. DP의 사용 조건
DP가 적용되기 위해서는 2가지 조건을 만족해야 한다.
1) 중복되는 부분 문제 (Overlapping Subproblem)
큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우를 의미
2) 최적 부분 구조 (Optimal Substructure)
동일한 작은 문제를 반복적으로 해결해야 하는 경우
① Overlapping Subproblems
DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.
예를 들어, 피보나치 수열이 해를 찾는 과정을 유심히 살펴보면 "큰 문제"를 찾기 위해 여러 "부분 문제"를 반드시 풀어야 하고 "부분 문제"는 반드시 중복해서 나타난다는 점이다.
예를 들어 F(4)를 구하기 위해선 "부분 문제" F(3)과 F(2)의 해를 찾아야 하고 F(3)은 다시 쪼개져 F(2)와 F(1)의 해를 찾아야 한다.
• F(4) = F(3) + F(2)
┗ F(4) = ( F(2) + F(1) ) + F(2)
이처럼 중복되는 부분 문제(Overlapping Subproblem)는 분할 정복과 동적 프로그래밍의 가장 큰 차이다.
분할 정복은 "큰 문제"가 "유니크한 부분 문제"로 나뉘지만 동적 프로그래밍은 "부분 문제"가 반복적으로 등장한다.
② Optimal Substructure(최적 부분 구조)
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다!
만약, A - B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다.
<최단 경로 찾기>
위의 그림에서 A - X 사이의 최단 거리는 AX2이고 X - B는 BX2이다. 전체 최단 경로는 AX2 - BX2이다. 다른 경로를 택한다고 해서 전체 최단 경로가 변할 수는 없다.
이와 같이, 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있게 된다.
피보나치 수열에서도 마찬가지로 "부분 문제"의 해가 "큰 문제"에 영향을 받지 않고 언제나 동일하다.
F(4)를 구하기 위한 F(2)의 해를 구하는 방식과 그 결괏값이
F(3)을 구하기 위한 F(2)의 그것과 동일하다는 의미이다.
이처럼 "큰 문제"의 해를 찾기 위한 연산과 "부문 문제"의 해를 찾기 위한 연산이 동일해야 하며 "부분 문제"의 해를 조합해 "큰 문제"의 해를 찾을 수 있는 구조를 최적 부문 구조(Optimal Substructure)라고 한다.
쉽게 정리하면 "큰 문제"의 해는 "부분 문제"의 조합으로 찾을 수 있으며 문제의 해는 동일한 연산으로 수행되어야 한다.
4. DP 사용하기
DP는 특정한 경우에 사용하는 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰일 수 있다. 그래서 DP를 적용할 수 있는 문제인지를 알아내는 것부터 코드를 짜는 과정이 난이도가 쉬운 것부터 어려운 것까지 다양하다.
일반적으로 DP를 사용하기 전에는 아래의 과정을 거쳐 진행할 수 있다.
1) DP로 풀 수 있는 문제인지 확인한다.
2) 문제의 변수 파악
3) 변수 간 관계식 만들기(점화식)
4) 메모하기(memoization or tabulation)
5) 기저 상태 파악하기
6) 구현하기
① DP로 풀 수 있는 문제인지 확인
애초에 이 부분 부터 해결이 매우 어렵다. 우선 DP의 조건 부분에서 써내렸듯이, 현재 직면한 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지를 판단해야 한다.
즉, 위에서 쓴 조건들이 충족되는 문제인지를 한 번 체크해보는 것이 좋다.
보통 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다.
② 문제의 변수 파악
DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것을 거친다. 즉, 문제 내 변수의 개수를 알아내야 한다는 것. 이것을 영어로 "state"를 결정한다고 한다.
예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 그 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있다.
또한, 문자열 간의 차이를 구할 때는 문자열의 길이, Edit 거리 등 2가지 변수를 사용한다. 해당 문제를 몰라도 된다.
또, 유명한 Knapsack 문제에서는 index, 무게로 2가지의 변수를 사용한다. 이와 같이 해당 문제에서 어떤 변수가 있는지를 파악해야 그에 따른 답을 구할 수 있다.
③ 변수 간 관계식 만들기
변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일하다. 또한 우리는 그 결과값을 그대로 이용할 것이므로 그 관계식을 만들어낼 수 있어야 한다.
그러한 식을 점화식이라고 부르며 그를 통해 우리면 짧은 코드 내에서 반복/재귀를 통해 문제가 자동으로 해결되도록 구축할 수 있게 된다.
예를 들어 피보나치 수열에서는 f(n) = f(n-1) + f(n-2) 였다. 이는 변수의 개수, 문제의 상황마다 모두 다를 수 있다.
④ 메모하기
변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장해야 한다. 이것을 메모한다고 하여 Memoization이라고 부른다.
변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.
이 결과 값을 저장할 때는 보통 배열을 쓰며 변수의 개수에 따라 배열의 차원이 1~3차원 등 다양할 수 있다.
⑤ 기저 상태 파악하기
여기까지 진행했으면, 가장 작은 문제의 상태를 알아야 한다. 보통 몇 가지 예시를 직접 손으로 테스트하여 구성하는 경우가 많다.
피보나치 수열을 예시로 들면, f(0) = 0, f(1) = 1과 같은 방식이다. 이후 두 가지 숫자를 더해가며 값을 구하지만 가장 작은 문제는 저 2개로 볼 수 있다.
해당 기저 문제에 대해 파악 후 미리 배열 등에 저장해두면 된다. 이 경우, 피보나치 수열은 매우 간단했지만 문제에 따라 좀 복잡할 수 있다.
구현하기
개념과 DP를 사용하는 조건, DP 문제를 해결하는 과정도 익혔으니 실제로 어떻게 사용할 수 있는지를 알아보고자 한다. DP는 2가지 방식으로 구현할 수 있다.
1) Bottom-Up (Tabulation 방식) - 반복문 사용
2) Top-Down (Memoization 방식) - 재귀 사용
구현 방법
바텀업(Bottom-Up)
가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식
바텀업 방식은 '상향식'이라고도 한다.
재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있는 장점이 있다.
위에 설명했던 피보나치 수열을 바텀업 방식으로 구현하면 아래와 같다. (탑다운 방식으로는 위에 이미 구현했음!) 동일한 원리를 적용하되 단순히 반복문을 이용하여 문제를 해결한 것으로 이해하면 된다!
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
dp = [0] * 100
dp[1] = 1
dp[2] = 1
n = 99
# 피보나치 수열 반복문으로 구현(Bottom-Up DP)
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n])탑다운(Top-Down)
큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
탑다운(메모이제이션) 방식은 '하향식'이라고도 한다.
점화식을 이해하기 쉬운 장점이 있다.
※ DP와 메모이제이션 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미하므로 DP와는 별도의 개념이다. --> 한 번 계산된 결과를 담아 놓기만 하고 DP를 위해 활용하지 않을수도 있다.
TIP
주어진 문제가 DP 유형인지 파악하는 것이 중요
먼저 그리디, 시뮬레이션, 완전탐색 등의 알고리즘으로 문제를 풀 수 있는지 검토한 후 풀 수 없다고 생각이 들면 DP를 사용해보자!
수열은 배열이나 리스트로 표현할 수 있다고 했는데, 메모이제이션은 때에 따라서 다른 자료형, 예를 들어 딕셔너리 자료형을 이용할 수도 있다. --> 사전 자료형은 수열처럼 연속적이지 않을 때 유용하다.
DP를 사용할 때, 일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (Top-Down) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 방법이다.
위의 피보나치 수열의 예제 코드처럼 재귀 함수를 작성한 뒤에 나중에 메모이제이션 기법을 적용해 소스코드를 수정하는 것도 좋다!!
