dynamic programming
dynamic programming은 하나의 문제를 패턴을 찾아 부분 문제로 나눠서 특정 범위에 대한 계산을 하고
그것을 이용해서 원하는 범위의 답을 계산하는 풀이 방법이라고 생각한다.
알고리즘 강의에서 교수님도 말했지만 dynamic이라는 영어 뜻과는 거리가 있다.
메모이제이션을 이용한 풀이? 재귀를 더 효율적으로 이용하는 그런 느낌이라는 생각이 들었다.
그리디에서도 썼지만 최적 부분 구조란 하나의 문제를 부분 문제로 나눈 뒤 결합하여 풀 수 있는 구조이다.
이 부분으로 나눈 문제가 다음 부분에 대해 영향을 미치는 관계가 계속되면 DP로 문제를 풀이할 수 있다.
초기 값 설정과, 점화식을 세우고, 앞에서 계산한 것으로 뒤에를 또 계산하는 것이다.
풀이가 직관적으로 떠오르지 않아서 유형을 익히는 것이 많이 중요하다고 생각이 드는데
대표적인 문제로는
- 재귀 수열
- 0-1 배낭 문제
- LIS (가장 긴 증가 수열)
- 행렬 곱셈
등이 있다.
이런 문제들은 이것이 DP로 풀이된다는 것을 모르면 사실 아이디어를 떠올리기 굉장히 어렵다.
그렇기에 다음 글은 배낭 문제에 대해서 좀 더 공부를 해보고자 한다.
DP의 구현 방법은 크게 top-down과 bottom-up 방식이 있다.
두 개가 다르다기 보다는 같은 점화식을 어디서부터 계산하느냐의 차이로
문제에 따라 구현의 편의성이 어떤 것이 좋을지 보고 접근하는 방법의 차이로 알고 있다.
top-down
이 방법은 최종 결과에서 시작해서 이전 결과를 통해 어떻게 최종 결과를 생성하는지를 분석한다.
예를 들어 피보나치 수열을 예시로 들면 f(n)을 정의하고 답이라고 두고 시작한다.
이렇게 f(n)을 계산하려면 f(n-1), f(n-2)가 필요하고 그러면 재귀를 통해 내려간다.
이 때 계산한 값은 dp 배열에 저장한다.
코드로 보면
1
2
3
4
5
6
7
long long dp[100];
long long fib(int n) {
if(n <= 1) return n;
if(dp[n] != -1) return dp[n];
return dp[n] = fib(n-1) + fib(n-2);
}
이렇게 아래로 내려갔다가 위로 올라오며 계산을 하게 된다.
재귀의 깊이와 메모이제이션 초기화에서 실수하기 좋기에 주의해야 한다.
bottom-up
이는 시작값을 가지고 그 값으로 다음 값을 계산하고, 계산하고 하는 방식이다.
점화식을 구하고 for문을 통해서 dp 배열들을 밑에서부터 채워가며 마지막 칸을 답으로 만든다.
역시 피보나치를 예시로 들면
1
2
3
4
5
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
dp[i]를 채우기 위해 dp[i-1], dp[i-2]가 필요하니까, 그게 준비된 순서대로 for문을 돌리는 것이다.
개인적으로는 bottom-up 방식이 점화식만 구할 수 있다면 구현하는게 훨씬 편하다고 느껴진다.
마지막 DP에 대한 감상은 문제를 풀다보면
1
2
3
이거 그리디인가? -> DP임
저번에 이 유형 DP 였는데? -> 그리디임
이건 진짜 DP다 -> 백트래킹임
정말 이런다.
이 세가지 문제 유형은 태그 없이 문제 풀다보면 정말 구분하기가 어렵다.
같은 문제 같아도 조건을 조금 바꾸면 DP <-> 그리디로 바뀌는 경우도 있고
문제 풀면서 느끼지만 반례 열심히 만들어보면서 디버깅하는 방법이 최선인 것 같다.