동적계획법 (3) 문제로 배우는 DP

안녕하세요 zzzzz님

강의에서 해당 문제를 탑다운과 바텀업 방식 두 가지로 풀이를 해드렸는데요.

결국에는 DP문제는 탑다운과 바텀업 두 가지 방법으로 다 풀 수 있습니다.

하지만 문제를 딱 봤을 때 바텀업으로 처음 접근할지, 아니면 탑다운으로 접근할 지 정해야 하는데, 이게 사람마다 다르고 상황마다 다르고 문제마다 다르더라고요.

저는 사실 탑다운 방식이 편한 문제를 어떤 사람은 바텀업이 자연스럽다고 느끼고, 평소의 저는 탑다운이 편하지만 어떤 문제는 바텀업이 편한 경우가 또 있더라고요.

정확하게 나누기는 어려운 것 같아요. 같은 문제도 사람마다 다르게 접근방법이 떠오르기 마련이니까요.

그래서 문제를 딱 봤을 때 탑다운으로 풀지 바텀업으로 풀지 정할정도가 되려면 DP문제를 많이 풀어보면서 두 가지 방식으로 다 풀어봐야 조금씩 감이 잡히는 것 같습니다.

다른 알고리즘의 경우에는 문제를 읽고 어느정도 감이 올 수 있는데, DP는 점화식을 생각해 내야되는 부분이 굉장히 큰데 그건 문제마다 너무 다르고 아이디어를 떠올리는 측면이 좀 강해서 결국 똑똑한사람(또는 연습이 많이 된 사람)이 유리한 부분입니다. 요령이 잘 없어요. 그래서 DP 문제를 항상 바텀업으로 풀었으면 탑다운으로도 푸는 연습을 하면 좋습니다.