동적 계획법(DP) 풀이에 관한 고찰

항상 DP 문제를 접하고 풀 때마다 느끼는거지만 '재귀'를 이용해 문제를 풀고자 하면 항상 어디에서 막히거나 시간 초과에 걸린다. 메모이제이션을 제대로 못해서인지 아니면 내가 점화식을 제대로 못짜서인지는 모르겠지만, 다른 사람의 풀이를 보면 죄다 거의 반복문으로 풀어낸다.

 

나도 반복문으로 풀고 싶지 않은 것은 아니다. 매번 DP 문제를 풀 때마다 재귀를 통해 문제를 풀어왔기 때문에, 반복문을 통한 접근 방식에 익숙치 않아서 어떻게 접근해야 할지도 모르겠고, 사실 아직까지 Top-down과 Bottom-up 방식을 구분하여 점화식을 세우는 방법 조차 내겐 너무 벅찬 일이다.

 

언제쯤 DP 문제가 익숙해져서 술술 풀어낼 수 있을지는 모르겠다. 매일 최소 한 문제씩 DP 문제를 풀고 있긴 한데, 감이 잡히는 것 같지가 않다.

 

이제부터라도 DP 문제를 풀면, 시간이 얼마나 걸리더라도 어떻게 풀었는지 또 다른 사람들의 풀이는 어떤지 분석하고 블로그에 꼼꼼하게 기록하는 습관을 들여야겠다.