DP 개요
DP, 다이나믹 프로그래밍은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 문제해결에 패러다임으로 볼 수 있습니다.
큰 문제를 작은 문제로 나누어서 그 답을 저장해두고 재활용한다.
사용이유
DP는 일반적인 재귀(Navie Recursion) 방법과 유사합니다. 하지만 일반적인 재귀를 사용할 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있습니다.
피보나치 수열을 예시로 들겠습니다.
피보나치의 재귀 함수는 아래와 같습니다.
return f(n) = f(n-1) + f(n-2)f(n)을 구하기 위해서 f(n-1)에서 한 번 구한 값들을 f(n-2)에서 같은 과정을 반복해버립니다.
크기가 커질수록 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 증가되게 됩니다.
그러나 한 번 구한 작은 문제의 결과값을 저장하고 재사용하면 매우 효율적으로 문제를 풀 수 있게 되고, 시작복잡도를 줄일 수 있습니다.
O(n^2) => O(f(n))
DP 사용 조건
DP를 사용하기 위해서는 다음 2가지 조건을 만족해야 합니다.
1. Overlapping Subproblems(겹치는 부분 문제)
2. Optimal Substructure(최적 부분 구조)
Overlapping Subproblems
DP는 기본적으로 문제를 나누고 결과값을 재활용해 전체값을 구합니다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능합니다. 즉 해당 부분 문제가 반복적으로 나타나지 않는다면 사용이 불가능 합니다.
Optimal Substructure(최적 부분 구조)
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미합니다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일해야 합니다.
f(10)이나 f(20)을 구할 때 중간과정인 f(5)는 항상 5를 나타난다는 뜻입니다.
DP 사용
DP는 특정한 경우에 사용하는 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 사용할 수 있습니다.
일반적으로 아래와 같은 순서로 진행합니다.
1. 문제 파악(DP로 풀 수 있는지 확인)
2. 변수 파악
3. 변수 간 관계식 만들기(점화식)
4. 메모하기(memorization or tabulation)
5. 기저 상태 파악하기
6. 구현하기
1 문제 파악
위의 조건들이 충족되는 문제인지 체크한 후 DP로 풀 수 있는지 없는지 판단을 합니다.
2. 변수 파악
DP는 현재 변수에 따라 그 결과값을 찾고 전달하여 재사용합니다. 즉 문제 내의 변수를 알아야 이것을 영어로 state라 합니다.
예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 그 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있습니다.
또한, 문자열 간의 차이를 구할 때는 문자열의 길이, Edit 거리 등 2가지 변수를 사용합니다.
또, 유명한 Knapsack 문제에서는 index, 무게로 2가지의 변수를 사용한다. 이와 같이 해당 문제에서 어떤 변수가 있는지를 파악해야 그에 따른 답을 구할 수 있습니다.
3 변수 간 관계식 만들기 (점화식)
변수들 간의 관계식을 점화식이라 하면 점화식을 통해 반복/재귀를 통해 문제를 해결할 수 있게 됩니다.
문제를 해결 할 때 점화식을 정확하고 빠르게 파악하는게 중요합니다.
4. 메모하기
점화식까지 파악했다면 변수의 값에 따른 결과를 저장해야 합니다.
결과를 저장할 배열을 미리 만들고 저장된 배열의 값을 사용하므로서 문제를 해결해 나갑니다.
5. 기저 상태 파악하기
가장 작은 문제의 상태를 알아야 합니다. 피보나치 수열을 예로 들면 f(0) = 0, f(1) = 1인 경우 입니다.
해당 기저 문제에 대해 파악한 후 미리 배열에 저장하면 됩니다.
6. 구현하기
DP는 다음의 2가지 방식으로 구현할 수 있습니다.
1. Bottom - Up (Tabulation 방식) - 반복문 사용
2. Top - Down (Memorization 방식) - 재귀 사용
① Bottom-Up 방식
이름에서 보이듯이, 아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식입니다.
메모를 위해서 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때, dp[0]가 기저 상태이고 dp[n]을 목표 상태라고 하자. Bottom-up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.
왜 Tabulation?
사실 위에서 메모하기 부분에서 Memoization이라고 했는데 Bottom-up일 때는 Tabulation이라고 부른다.
왜냐면 반복을 통해 dp[0]부터 하나 하나씩 채우는 과정을 "table-filling" 하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다고 한다.
사실상 근본적인 개념은 결과값을 기억하고 재활용한다는 측면에서 메모하기(Memoization)와 크게 다르지 않다.
② Top-Down 방식
이는 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.
피보나치의 예시처럼, f(n) = f(n-2) + f(n-1)의 과정에서 함수 호출 트리의 과정에서 보이듯, n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 된다.
이 때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다. 그래서 가장 최근의 상태 값을 메모해 두었다고 하여 Memoization 이라고 부른다.
참조
https://hongjw1938.tistory.com/47
