Algorithm/동적 프로그래밍이란?
개인적으로 공부하며 작성해둔 DP 학습정리
개요
DP(Dynamic Programming) 이란 ?
👉 큰 문제를 작은 부분 문제로 나누고
👉 중복 계산을 저장하여 재사용하는 기법
동적 프로그래밍을 사용하는 경우
1️⃣ Overlapping Subproblems
부분 문제가 반복적으로 등장한다
ex) 피보나치 수열
F(5)
├─ F(4)
│ ├─ F(3)
│ │ ├─ F(2)
│ │ └─ F(1)
│ └─ F(2)
└─ F(3)
F(3), F(2) 같은 계산이 계속 반복됨
2️⃣ Optimal Substructure
부분 문제의 최적해로 전체 최적해를 만들 수 있다
ex) 베낭 문제
최대 가치(용량 7)
=
max(
용량7에서 A 안 넣기,
용량(7 - A무게) + A가치
)
전체 최적해를 구하려면 이전 상태의 최적해가 필요하다!
구현 방법
DP는 다음과 같은 2가지 방식으로 구현할 수 있다.
- Bottom-Up (Tabulation 방식) - 반복문 사용
- Top-Down (Memoization 방식) - 재귀 사용
☑️ Bottom-Up 방식
반복문 기반 + Tabulation
기초 상태부터 차례대로 계산한다
아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식
메모를 위해서 dp 라는 배열을 만들고, 이것이 1차원이라 가정했을 때 dp[0] 이 기저상태이고 dp[n]을 목표 상태라고 한다.Bottom-Up은dp[0]에서부터 시작해서 **반복문을 통해 점화식으로 결과를 내서**dp[n]`까지 값을 전이시켜 재활용하는 방식이다.
Tabulation 은 뭐지?
반복을 통해 dp[0]부터 하나 하나씩 채우는 과정을 "table-filling" 하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다고 한다.
☑️ Top-Down 방식
재귀 + 메모이제이션
문제를 해결하려다 필요한 부분 문제를 재귀적으로 호출하고, 이미 계산된 값은 저장해뒀다가 재사용한다!
dp[0] 의 기저상태에서 출발하는 대신 dp[n] 의 값을 찾기 위해 위에서부터 호출을 시작해 dp[0] 까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식!
피보나치 예시처럼 f(n) = f(n-2) + f(n-1) 의 과정에서 하위에 동일한 계산이 반복적으로 나오게 되는데, 이미 이전에 계산을 완료한 경우 단순히 메모리에 저장되어있던 내역을 꺼내서 활용하면 된다.
그래서 Memoization 이라고 부른다!
차이 비교
| 구분 | Top-down | Bottom-up |
|---|---|---|
| 시작점 | 큰 문제 | 작은 문제 |
| 구현 | 재귀 | 반복문 |
| 계산 방식 | 필요할 때 | 미리 |
| 성능 | 느릴 수 있음 | 보통 빠름 |
| 메모리 | stack 사용 | 없음 |
| 직관성 | 좋음 | 설계 필요 |
예시 코드
// 단순 재귀를 통해 Fibonacci를 구하는 경우
// 동일한 계산을 반복하여 비효율적으로 처리가 수행됨
public static int naiveRecursion(int n){
if(n <= 1){
return n;
}
return naiveRecursion(n-1) + naiveRecursion(n-2);
}
// DP Top-Down을 사용해 Fibonacci를 구하는 경우
public static int topDown(int n){
// 기저 상태 도달 시, 0, 1로 초기화
if(n < 2) return topDown_memo[n] = n;
// 메모에 계산된 값이 있으면 바로 반환!
if(topDown_memo[n] > 0) return topDown_memo[n];
// 재귀를 사용하고 있음!
topDown_memo[n] = topDown(n-1) + topDown(n-2);
return topDown_memo[n];
}
// DP Bottom-Up을 사용해 Fibonacci를 구하는 경우
public static int bottomUp(int n){
// 기저 상태의 경우 사전에 미리 저장
bottomup_table[0] = 0; bottomup_table[1] = 1;
// 반복문을 사용하고 있음!
for(int i=2; i<=n; i++){
// Table을 채워나감!
bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2];
}
return bottomup_table[n];
}