DP는 알고리즘 문제 중에 가장 감이 잡히지 않는 유형이다. 개념 자체는 이해가 되지만 문제를 봤을 때 DP로 풀어야겠다고 바로 떠올리기가 힘들다. DP문제 임을 알고 풀지만 문제만 보고 DP 문제라고 판단하기가 쉽지 않다. 일단 대표적인 DP 문제 유형을 나름 정리하면서 감을 잡으려 하고 있다.
DP는 dymamic programming의 약자로, 직역하면 동적 프로그래밍이다. 동적 프로그래밍이라고 해서 동적할당 방법을 쓰지 않는다. 이름과는 무관하게 '동적'과 관련이 없어서 '기억하며 풀기'가 가장 의미있다는 의견이 많다.
DP는 큰 문제를 부분문제로 나누고 부분문제를 풀어가면서 결론적으로 큰 문제를 푼다는 개념이다. 이렇게만 들으면 분할정복과 다를 바가 없고, 앞서 이야기한 '기억하며 풀기' 랑도 연관이 없어보인다. 자세하게 이야기하면 DP는 부분문제들의 답을 배열이나 자료구조에 저장하면서 활용한다. 부분문제의 답을 저장해두고 큰 문제를 풀 때 사용함으로써 시간 복잡도를 줄인다.
예를 들어, 만약 S(n)을 구하기 위해 S(n-1)이나 그 전 값이 필요하다면, 재귀를 통해 S(n-1)이나 그 전 값을 구할 수 있다. 그러면 시간적으로 오래걸리고, 또 S(n+1)을 구할 때 이미 구했던 S(n-1)을 또 계산해야하는 중복이 발생하면서 시간이 복잡해질 수 있다. 그 때문에 부분문제의 답을 자료구조에 저장해두었다가 큰 문제를 풀 때 이를 활용하면 시간복잡도를 줄일 수 있다는 개념이 DP 문제이다. ('동적' 이라는 표현과 전혀 연관이 없다. '기억하며 풀기' 가 가장 적당한 듯 하다.)
동적 계획법(Dynamic Programming) (velog.io) 이 블로그랑 겐지충 프로그래머 :: 알고리즘 - Dynamic Programming(동적 계획법) (tistory.com) 이 블로그에서 설명을 잘해준다.
처음엔 무조건 재귀 형태일 때에 사용하는 기법인줄 알았다. 이건 지엽적인 부분이다. 더 큰 개념으로 DP는 '큰 문제를 부분문제로 해결할 때에 중복 계산을 줄이기 위해 부분문제의 답을 기억해두기' 라고 생각하면 좋을 듯 하다. 이런 부분이 필요한 경우를 정리해 보았다. 전체적인 DP 개념은 같으나 문제를 푸는 유형에 따라 주관적으로 나누어 본 것이다. 유형 이름도 맘대로 정했다.
- 최적의 선택을 위해 당장 최선의 선택을 포기해야만 하는 경우 (냅색 유형)
- 최종적으로 최적값을 구하기 위해 차례로 경우의 수를 계산하는데 순간순간마다 최적의 선택을 포기해야 할 때, (= 그리디 알고리즘과는 정반대, 그리디는 순간순간 마다 최적의 선택이 최종적 최적값을 구하는 것일 때) 이 경우 그 전 값을 포함하는 경우와 포함하지 않는 경우의 최적값을 저장해두면 그 다음 값을 포함시킬지 말지 결정하기 좋다.
- 12865번: 평범한 배낭 (acmicpc.net)
- 7579번: 앱 (acmicpc.net)
- DP 인덱스를 무조건 포함시킨 최적값을 구하는 경우 (인덱스 포함 유형)
- 현재 인덱스에 해당되는 조건을 무조건 포함시켰을 때 최적값을 구하는 것
- 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)
- 10844번: 쉬운 계단 수 (acmicpc.net)
- 1149번: RGB거리 (acmicpc.net)
- 가능한 모든 경우를 탐색하기 위해 그룹으로 나누었더니 부분문제인 경우 (그룹으로 나누는 유형)
- 쪼개보니 DP에 저장해 둘 수 있는 것 (쪼개보니 부분문제인 경우)
- 11066번: 파일 합치기 (acmicpc.net)
- 11049번: 행렬 곱셈 순서 (acmicpc.net)
위의 예시 말고도 재귀문제에서 시간을 줄이기 위해 사용하는 유형도 있다. 가장 대표적인게 피보나치 수를 구하는 문제인데 이런 유형들은 재귀로 알고리즘을 짤 때 바로 눈에 보이기 때문에 유형 나누는 것에 포함시키지 않았다. 재귀를 하면서 계산 로직에 진입하기 전에 if문으로 DP에 부분문제 값이 저장되어있는지를 확인해보고 있으면 계산로직을 돌리지 않고 값을 가져오는 방식이다.
DP의 모든 문제들을 내가 정리한 유형으로 구분할 수 없다.
이 문제들은 내가 정리한 유형 중에 속하지 않는다. 그냥 DP의 기본 개념인 '큰 문제를 풀기위해 부분문제 값이 저장되어야 할 때' 에 입각해서 푸는 것이 중요하다.
어려운 DP문제는 문제를 보는만으로 DP 알고리즘으로 풀어야하는지 감이 잡히지 않는다. 문제를 풀기위해 분석하다보니 내가 정리한 DP 유형이 보이는 경우도 있고 (2565번: 전깃줄 (acmicpc.net) 이 문제가 대표적이다. 문제를 풀기위해 분석하다 보면 가장 긴 증가하는 부분수열과 동일함을 알 수 있다.) 문제를 분석해보니 어느 유형에도 속하진 않지만 부분문제로 풀어야하는 경우 가 있을 수 있다.
DP 유형의 문제만 주구장창 푸는 것이 DP문제 푸는데 도움이 될 수 있지만 특정 문제를 마주했을 때 이것이 DP로 풀어야하는가 그리디인가, 백트래킹인가, 이분탐색인가, 분할정복인가, 자료구조를 적절히 활용하는 문제인가를 잘 파악하는 것이 중요하다. 문제를 분석하고 가장 효율적인 알고리즘을 탐색하는 능력을 길러야겠다.
처음 DP문제를 접할 땐, 재귀 형태 내에서 memorization하기만 하면 되는 알고리즘인 줄 알았다. 하지만 그런 형태가 아닌 문제도 나오게 되면서 다시 생각할 필요가 있었다. 그후 문제를 풀면서 DP 문제를 풀 땐 특정 조건을 성립하는 (예를 들어 현재 인덱스의 값을 무조건 포함하는 경우에서 최적값을 DP에 저장) memorization을 하는 것이 맞다고 생각했다. 하지만 이 방식은 백준 실버 문제에서는 잘 적용되었지만 골드문제를 풀 땐 어려웠다. 그리고나서 위에서 정리한 3가지 유형을 정리하기 시작했다. 유형을 정리하면서 DP는 '큰 문제를 부분문제로 해결할 때에 중복 계산을 줄이기 위해 부분문제의 답을 기억해두기' 라는 결론을 내리게 되었다. 사실 인터넷을 찾아보면 이 말은 어디에나 다 나온다. 하지만 글만 보고 DP문제란 이런 것이구나 라고 감을 잡기가 힘들다. 문제를 풀고 유형별로 정리하면서 DP의 정의를 몸소 깨닫는 것이 중요하다고 생각한다.
내가 DP 문제를 유형별로 정리했지만 확실하지도 않고 모든 문제가 저 유형에 속하지는 않는다. 그냥 내 편의대로 정리한 것이다. 하지만 모든 DP는 큰 문제를 부분문제로 해결한다는 본질은 변하지 않는다. 더 많은 DP 문제를 풀어보면서 감을 잡는 것이 굉장히 중요하다고 생각한다.
'알고리즘' 카테고리의 다른 글
| 알고리즘 유형 (백트래킹) (0) | 2023.08.25 |
|---|---|
| 알고리즘 시간 줄이기 (입출력 시간 줄이기 : 버퍼 비동기화 & io untied) (0) | 2023.05.21 |
| 알고리즘 시간 줄이기 (정렬 알고리즘) (2) | 2023.05.21 |
| cpp 복습 후 느낀 점 (0) | 2023.04.25 |
