이 글을 쓰게 된 계기
아래 링크의 백준 문제를 풀고 있었는데, 1시간이 넘도록 고민을 해도 어떻게 경우의 수를 줄일지 방법이 생각나지 않았다.
고민 끝에 다른 사람들이 남긴 힌트를 봤는데, 내가 왜 이걸 생각하지 못했는지 너무 허무했다.
(TMI - 문제를 접근했을 때 당시의 의식의 흐름, 이후 개인 참고용)
행렬의 개수가 최대 500개이기 때문에, 곱셈 연산자를 나열하는 경우의 수를 499!로 보았고, 이것은 이전 곱셈 결과를 재활용하는 방법밖에 없을 것이라고 생각해 DP로 문제를 해결하는 방법을 고민함.
A(BC)와 (AB)C가 다르기 때문에 최솟값을 구하기 위해서는 2개의 행렬이 곱해지는 모든 경우의 수를 따져보아야 하고, 그 경우의 수에 따라 3개의 행렬이 곱해지는 모든 경우의 수를 따져보아야 하고, ... 그 경우의 수에 따라 n개의 행렬이 곱해지는 모든 경우의 수를 따져보아야 한다.
k(0<k<n)개의 행렬이 곱해지는 모든 경우의 수를 따져보았다고 하더라도, 곱셈 횟수가 비교적 많은 경우가 있다고 하더라도 그것이 나중에 다른 행렬과 곱해져 실제로는 현재 곱셈 횟수가 비교적 적은 경우보다 총 곱셈 횟수가 적어질 수도 있으므로 함부로 무시할 수는 없다.
backtracking으로 가지치기를 할 수도 있을 것 같으나 그렇다고 하더라도 499!는 견딜 수 없을 것이다.
예전부터 DP 문제를 풀 때 이런 전략을 가지고 가면 좋겠다는 생각이 있었는데, 그것을 어딘가 정리한 적이 없었다.
이번 경험도 내가 생각하고 있었던 그 전략과 상통하는 것 같아 아예 DP 문제를 풀 때 어떤 전략과 사고를 가지고 풀면 좋을지 정리해보려고 한다.
DP 문제 풀이 전략
DP를 어디에 적용하면 좋은가?
- 이전에 계산한 결과값을 다시 사용하면 바람직할 때, 또는 이전에 계산한 결과값을 사용해야만 할 때
- 최적화 문제를 풀 때. 지금의 값이 현재는 최적인 것 같지만 전체를 보았을 때 아닌 경우
- 어떠한 문제가 그 하위문제로 계속 나뉘어질 수 있는 경우
DP를 적용하려고 생각했다면, 어떤 전략을 가져가야 하는가?
- 나는 무엇을 구해야 하는가? 문제에서 원하는 것은 무엇이고 원하지 않는 것은 무엇인가?
- 때로는, 문제에서 원하는 것만 저장하면 되는데, 그밖의 다른 것까지 저장해야 한다고 착각해 스스로 머리를 복잡해지게 만들어 문제를 풀지 못하는 경우가 있다.
- 문제에서 원하는 것이 무엇인지 다시 한번 보고, 내가 무엇을 저장해야 하는지 결정한다.
- 문제에서 원하는 것이 무엇인지 다시 한번 보고, 내가 지금 생각하고 있는 풀이에서 필요 없는 것이 무엇인지 다시 한번 생각한다.
- 내가 저장하려는 어떤 값이 정해졌다면, 어떻게 저장해야 하는가?
- DP의 메모이제이션은 대부분 배열 형태로 많이 저장이 된다. 나중에 다른 자료구조를 사용하게 되더라도, 일단 배열 형태로 생각해보자. DP에서 막히게 되는 주요 원인은 아이디어를 생각하지 못해서이지, 자료구조가 적합하지 않아서가 아니다. 아이디어를 생각한 뒤 자료구조를 변경해도 늦지 않다.
- 배열 형태에서, 어떤 것을 축(차원)으로 설정할지 생각한다. 내가 지금 생각하고 있는 축 조합이 정답이 아니라는 생각이 들면 다른 여러 조합들을 시도해본다. 생각보다 문제를 다시 한 번 살펴보면 축으로 삼을 만한 후보들이 그렇게 많지 않다. 후보들을 여러 개 조합해보다가 올바른 축이 정해졌다면, 문제는 비교적 쉽게 풀린다.
- DP의 메모이제이션 배열 차원이 1차원으로 해결되지 않는다면, 차원 수를 늘려가며 생각해본다. 물론 이것이 차원을 늘려서 해결될 수 있는 문제인지는 고려가 필요하다. 1번의 고려가 한 번 더 필요한 시점이다. 대부분 2차원 배열로도 웬만한 것들은 풀릴 수 있다.
- 가능하다면, 그림을 그려 가며 문제를 풀어보자.
- 여기까지 올바른 스텝을 밟아왔다면, 아하 모멘트가 생겼을 것이다. 만약 그랬다면, 데이터를 저장하기 위해 어떤 연산을 해야 하는지 생각한다.
- 그렇지 않다면, 1번과 2번으로 돌아가자.
- 1번과 2번의 고려가 끝났다면 이 과정은 비교적 쉽다.
- 점화식을 먼저 생각하는 것이 아니라, 자료구조를 먼저 생각한 뒤 그곳에서부터 점화식을 이끌어낸다. 점화식을 먼저 생각하는 것은 너무 어렵다.
- 사람은 여러 차원을 한꺼번에 같이 생각하는 것이 어렵다. 그것이 DP 문제를 힘들게 하는 원인 중 하나일 것이다. 2차원 테이블로 나타내면 그제서야 한눈에 보이면서 문제의 실마리가 잡히는 경우가 있었다.
- 마지막으로, 구현한다.
References
다른 자료 전혀 참고하지 않은 온전히 제 머리 속에서 나온 생각입니다.
이 글을 읽는 여러분들의 생각은 제 생각과 다를 수 있겠지만 아 이런 생각 하는 사람도 있구나 하고 참고해주세요.
여러분들은 DP 문제 어떻게 전략 짜시는지 공유해주시면 감사하겠습니다.
