동적계획법 깨닫기

동적계획법(Dynamic Programming)

---

동적계획법이라는 말을 처음 들었을 때 머리에 딱 박히지 않았다. 단어가 직관적이지 않아서 알고리즘 문제를 풀때도 어려움이 있었는데 이때 억지로 문제를 풀거나 다른 사람의 코드를 찾아보기보다 동적계획법이라는게 정확히 어떤 의미인지 인터넷에 검색해보고 책을 찾아봤다. 그랬더니 문제가 술술 풀려버렸다. ㅎ.ㅎ

계획법(programming)의 열받는 어원

동적 계획법을 구글에 검색했더니 어쩌다 지은 이름인지 위키백과에 나왔다.
대충 설명하면 한 수학자가 수포자인 군인에게 한 알고리즘(동적계획법)을 설명해야 했는데 수학적 용어나 어려운 말을 써버리면 더 머리 아파할 것이 뻔하기 때문에 거부감 없이 받아들이게 하기 위해서 공군에서도 많이 쓰던 단어인 계획법(programming)을 선택했다고 한다.

억지로 이름을 붙인거라 와닿지 않았던것 같다. 원래는 process로 지으려고 했다. 동적계획법 말고 동적프로세스라고 하니까 훨씬 친근해진 느낌.

동적계획법을 쓰는 경우

문제를 쪼갰을때 그 안에 똑같은 형태의 문제가 또 나올때 동적계획법을 사용하면 좋다. 정확히 어떤 상황인지는 아래에서 예시로 설명할 것이고 전문적인 말로는 최적 부분 구조를 가지는 경우라고 한다. 마트료시카 인형같은 느낌.

똑같은 구조의 문제가 계속 나오는 경우(최적부분구조)에 중복되는 값이나 중복 호출되는 함수가 있다면 동적계획법을 쓰기 가장 좋은 상황.

예시

동적계획법 적용 문제

끝

다 깨달은줄 알았으나 다른 문제를 푸니까 또 머리가 아프다……………………..