(이 DP가 아니다.)
1. DP란?
Dynamic programming으로, 동적 프로그래밍 혹은 동적 계획법이라고도 한다.
(들은 바로는 그럴싸한 이름을 짓고자 이렇게 지었다고 한다.)
하나의 문제를 단 한 번만 풀자!
라고 외치면서 등장한 알고리즘 '설계 기법'이다. 재귀에 대한 최적화라고도 한다.
재귀에서 문제를 부분 문제로 나눌 때, 계속해서 연산해야 하는 몇 가지 부분 문제가 존재할 수 있는데 이를 '중복된 부분 문제'라고 한다. 그리고 DP에서는 이 중복된 부분 문제의 결과를 저장하고, 필요할 때마다 (재연산 없이) 이전의 결과만을 불러와 사용한다.
문제를 맞이했을 때, "DP로 풀거야!" 한다면 DP의 사용 가능 조건 2가지를 확인해야 한다.
첫째, 큰 문제를 작은 문제로 나눌 수 있다.
둘째, 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
언뜻 봐도 분할 정복과 비슷한데.. 뭐가 다를까? 이를 정리하면 다음과 같다.
💔 분할정복 (Divide and Conquer)
- 작은 문제로 쪼개는데, 중복은 없다.
- 쪼개진 작은 문제들의 솔루션을 만든다.
- 거꾸로 올라가면서 전체의 해답을 만든다.
▶ 즉, 문제를 작은 문제로 / 중복 없이 / 재귀적으로 쪼개서 해결한 다음 → 다시 (거꾸로) 재귀로 큰 문제로 조합하면서 올라오는 방식이다.
🧲 동적 계획법 (Dynamic Programming)
- 작은 문제로 쪼개는데, 중복될 수 있다.
- 쪼개진 작은 문제들의 솔루션을 만들고, 테이블에 저장한다.
- 작은 문제 솔루션을 갖고 종합해서 더 큰 문제의 솔루션을 만든다.
▶ 즉, 문제를 작은 문제로 / 중복 가능하게 쪼개서 해결한 다음 → 테이블에 저장해 놓고 → 더 큰 문제를 해결할 때, 테이블에 저장된 작은 문제들의 솔루션을 읽어와 조립해서 푼다.
아직 잘 안 와닿는가..? 백준 문제를 풀어보면 확 와닿을 것이다.
분할정복 : 백준 2630번 색종이 만들기 / DP : 백준 2748번 피보나치 수 2
DP는 엄청난 시간 개선이라는 장점을 갖지만, 작은 솔루션들을 저장할 테이블을 추가로 만들어야 한다는 점에서 공간(메모리) 추가와 같은 단점이 있다. 한 가지를 원하면, 다른 한 가지를 내어 주어야 하듯이 이를 "Time-Memory Trade-off"라고 부른다고 한다. (역시 세상만사 기브 앤 테이크군..)
2. 하향식 vs. 상향식
DP를 구현할 때, 하향식 접근과 상향식 접근 두 가지로 나눌 수 있다.
(그 전까지 피보나치 수열을 구현할 때는 아래와 같이 했지만, 이제 DP로 구현해 보자!)
def fibonacci(num):
if num == 1 or num == 2:
return 1
return fibonacci(num-1) + fibonacci(num-2)1) 하향식 접근 (Top-Down)
- n부터 시작한다.
- 재귀를 사용한다.
- 메모이제이션(memoization)
- 부분 문제에 대한 결과(작은 문제들의 솔루션)을 메모 배열에 저장한다.
- 필요할 때마다 메모 배열에서 값을 불러와 사용한다.
피보나치 수열을 하향식으로 구현하면 다음과 같다.
def fibonacci(num):
global memo
if num == 1 or num == 2:
return 1
if memo[num]: # 값이 이미 있으면, 가져다가 쓴다!
return memo[num]
memo[num] = fibonacci(num-1) + fibonacci(num-2)2) 상향식 접근 (Bottom-Up)
- 최초값으로부터 시작한다.
- 재귀를 사용하지 않는다. 반복문을 사용한다.
- 타뷸레이션(Tabluation)
- 테이블을 채워나간다는 느낌으로, 하나씩 다 미리 계산한다.
피보나치 수열을 상향식으로 구현하면 다음과 같다.
def fibonacci(num):
f = [0,1] # 처음 두 개의 값이 주어진다.
for i in range(2, num+1):
f.append(f[i-1] + f[i-2])
return f하향식(Top-Down)의 장점은 재귀로 인한 가독성(?) 혹은 직관성(?)이 있지만, 재귀 호출 스택이 Recursion Error를 발생시킬 수 있다는 문제를 가진다.
반면, 상향식(Bottom-Up)의 장점은 재귀가 없어 상대적으로 빠르지만, 어떤 입력이 들어와도 처음부터 계산하므로 불필요한 연산이 생긴다는 단점이 있다.
(줄 친 부분은 '함수'로 만들었을 경우에 그런 것이고, 전역에서 for문을 돌려버리면 상관 없다. 대신 상향식의 치명적인 단점은.."구현이 매우 복잡함"이라고 한다.)
앞서 fibonacci를 상향식/함수 X 방식으로 구현하면 다음과 같다.
# f의 리스트를 전부 -1로 초기화 하고 시작한다.
f[1] = 1
f[2] = 1
for i in range(3, n+1):
f[i] = f[i-1] + f[i-2]이러면 이미 f 배열(global)에 값이 채워져 있으므로, 가져다 쓰기만 하면 된다!
3. DP 접근 step
DP 문제는 결국
반복 연습을 통해 감을 잡자!
밖에 답이 없지만, 그래도 DP를 열정적으로 설명해 준 형준이의 방법을 빌리자면 다음과 같다.
step 1. DP로 풀 만한가? 혹은 풀어야 하나?
👉 문제를 쪼갰을 때 중복될 거 같다!
👉 재귀 느낌이 난다!
👉 위 두 개를 고려했을 때, 최적 구조(작은 문제로 큰 문제를 해결)을 만족한다..?
step 2. 뭘 (매개변수로) 저장할지 생각하기 → 메모이제이션/타뷸레이션
step 3. 작은 문제들의 해들을 구해보면서 → 점화식을 찾아가기 ★쫄지 않는다.★
step 4. 하향식 or 상향식 풀이
👉 첫 느낌이 재귀..? 기하학(그림)이다..? → 하향식
👉 수만 깔끔하게 주어지고, 규칙을 찾아가야 할 것 같다? → 상향식
(그래도 하향식보다는 상향식이 최고라고 한다.)
4. 백준 예제
[실버]
1) 1로 만들기
2) 거스름돈
3) 타일 장식물
[골드]
1) 배낭 문제
2) LCS
