동적 계획법 (dp)를 공부하는 법
알고리즘 공부를 시작한지 얼마안돼 dp라는 알고리즘으로 분류된 문제들에서 막혔다. 꾸역꾸역 코드를 작성해도 시간초과가 뜰 뿐이었다. 알아보니 그러한 문제들은 dp라는 알고리즘 설계기법을 사용해 풀이하도록 제출된 문제들이었다. 그래서 dp에 대해 기초개념부터 차근차근 공부하고 다시 문제 풀이에 도전했지만 여전히 내게 너무 어렵게 다가왔다. 익숙치 않은 탓이라 생각하고 다른 사람들의 코드도 찾아가며 많은 문제를 풀려했는데, 근본적으로 해결이 안되고 억지로 끼워맞추고있다는 느낌이 너무 강하게 들었다. 결국 해결방법을 찾는데 알고리즘을 공부를 하는 시간 보다 많은 시간을 투자 했다.
아마 많은 사람들이 어려워 할 부분이라 생각한다. 그런데 어떻게 공부해야 하는지에 대한 정보는 많이 없었다. 대부분 dp가 무엇인지 그리고 dp문제들은 어떤것이 있고 어떻게 풀어나가면 되는지가 전부였다. dp문제들을 아무리 봐도 배열은 어떤식으로 구성해나가고 어떻게 해야 시간복잡도가 줄어들지 접근방식이 쉽사리 떠오르지 않았다. 많이 찾아보고 관련 문제도 꽤 풀어보았지만 아직도 어렵다고 느낀다. 그래도 조금이나마 익숙해지고 어떻게 공부해야하는지 방향은 어느정도 잡은 듯 하여 정리해 보려고 한다.
Dynamic programming
이미 대부분 dp가 무엇인지는 알고있을거라고 생각한다. dp는 Dynamic programming의 약자로 뒤에 ‘프로그래밍’ 때문에 프로그래밍 기술이라고 생각하기 쉽다. 하지만 우리가 아는 ‘프로그래밍’과는 다른 의미로 쓰였다. 원래 Dynamic programming은 Richard Bellman이 만든 수학적 최적화 기법이다. 이후 프로그래밍을 통해 알고리즘을 풀어나가는 알고리즘 설계방법으로도 쓰이면서 시간복잡도를 낯추고 메모리 낭비를 막는데 큰 효율을 보여준다. 이외에도 항공 우주 공학이나 경제학등 여러 학문에 이르러 널리 사용되고 있다고 한다.
그럼 이러한 dp를 적절히 잘 사용해서 문제를 해결하기 위해서는 어떻게 접근해야 할까?
1. 귀납적 추론
우선 내가 처음에 썼던 방법은 귀납적추론이었다. 문제가 요구하는 답을 각각의 변수마다 몇개 씩 직접 구해서 점화식을 세우고 풀이하였다. 이 방법은 기초적인 dp문제를 풀때 직관적이고 이해하기 쉽다. 그러나 문제가 조금만 복잡해져도 답을 몇개 도출하는데 시간이 많이 걸린다. 그 때는 그냥 간단한 코드를 작성해서 구하여 정리하고 다시 귀납적 추론으로 해결해도 된다. 나도 처음에는 너무 무식하게 풀이하고 있는 것이 아닌가 하는 생각이 들었지만 그렇게 기초 문제들을 풀이하다 보니 후에는 간단한 dp문제들을 보는 직관이 생겼다.
dp문제는 사실 어떻게 풀이할 것인지 생각하는데 풀 수 있느냐 없느냐가 달렸다. 그런데 dp의 개념은 알지만 어떤식으로 푸는지 모르면 문제가 어렵든 쉽든 그것이 dp문제인걸 알더라고 풀이하기 쉽지 않다. 그래서 처음에는 쉬운 대표문제를 찾아 이렇게 차근차근 풀어나가며 익숙해지고 직관력을 기르는 것이 좋다고 생각한다.
2. 이미지화
dp의 개념과 관련문제에 대해 알아보면 코드를 보더라도 이해하기 힘든 경우가 많았다. 그래서인지 시각화된 자료들을 많이 찾아 볼 수 있었는데 아무리 이해가 안됐던 문제라도 시각화된 이미지를 참고하여 코드와 비교하면서 생각하다보면 쉽게 이해가 되었던 적이 많다. 아마 이 글을 보고 있는 당신도 그랬던 기억이 있을것이다. 그 기억을 살려 바로 코드를 작성하지 않고 테이블이나 각 항의 관계를 머릿속에 그린후 이해하고 그것을 기반으로 코드를 작성하면 훨씬 쉽다. 머릿속에 그리는 것이 잘 안되면 손으로 그리면 된다.
3. 반복 연습 하기
어쩌면 당연하지만 다양한 문제를 접하고 반복해서 많이 풀어봐야 한다. dp문제들의 성격이 그렇듯 문제를 풀이할 아이디어를 얻기 위해서는 그것과 맞는 사고방식과 문제 해결 능력이 필요하다. 이런 감을 얻으려면 역시 자주, 많이, 다양하게 접하여 풀어보고 다른사람의 코드들도 분석해 볼 필요가 있다. 이미 풀어본 문제도 다시 풀어보면 원래 풀이했던 방법과는 다른 방식으로 풀이하는 자신을 발견하게 될지도 모른다. 그렇다면 자신의 코드를 비교해 보고 자신이 그 풀이방식을 어떻게 해서 떠올리게 됐는지 되새기며 공부하면 관련 문제에 대한 아이디어를 갈수록 더 쉽게 도출해 낼 수 있을거라고 생각한다.
4. 자신만의 기준 세우기
이 방법은 내가 갈피를 못잡고 해매다 선배에게 도움을 요청했을때 들은 방법이다. dp문제라고 해서 문제풀이 방식이 항상 같은것도 아니고 아주 많은 유형으로 다양하게 등장한다. 이런 광범위한 알고리즘 이기 때문에 문제를 어떤식으로 해결해 나갈 것인지 빠른시간에 방향을 잡으려면 자신만의 기준을 세우면 된다. 나는 ‘변수에 따라 나오는 결과값 그 자체가 다시 변수가 되어 다음 결과값에 영향을 미치는 문제’를 기준으로 잡았다. 그러니까 결과값들을 항으로 정리 할 수 있고 항들사이의 규칙이 있어 구하려는 항의 값을 다른 항들로 부터 도출해 낼 수 있는 문제들을 말한다. 이건 아직 초보인 나의 지극히 개인적인 생각일 뿐이다. 그래도 이렇게 기준을 잡고 문제 풀이 아이디어를 생각하면 적절한 아이디어를 생각해 내는데 도움이 많이 된다.
위에 알려준 4가지 방법은 내가 dp문제들을 어려워해서 많이 알아보고 느낀점들을 포함한다. 혹시 같은 문제를 겪고있다면 위의 방법들을 시도해 볼 만한 가치가 있다고 생각한다.
백준 온라인 저지 사이트의 게시판을 활용 하면 고수들의 많은 정보를 얻을 수 있다.