Dynamic Programming
소개
알고리즘 풀이법에서 가장 와닿지 않는 용어 중 하나다. 그래서 용어를 이해하는 시간을 가져보려고 한다.
DP란 최적화 문제를 연구하는 수학 이론에서 왔으며, 우리가 전산학 전반에서 일반적으로 사용하는 동적(dynamic), 혹은 프로그래밍(programming)이란 단어와는 아무런 관련이 없습니다.
실제로 이름을 지은 사람도 내용과 상관없이 이름이 멋있어서 지었단다.
따라서 DP를 직독직해하면 전혀 와닿지 않는다. (역동적으로 프로그래밍하기!? 뭔가 움직이면서 코드를 짜야 할 것 같다)
찾아본 내용 중 가장 쉽게 이해하는 용어로는 기억하며 풀기 였다.
쉽게 생각해, 노트에 적어가면서 풀었던 내용을 참고하며 다음 문제를 풀어나가는 것이다.
DP는 분할 정복과 같은 접근 방식이지만, 문제를 나누는 방식에서 그 차이점이 발생한다.
바로, 부분 문제가 중복 되는 경우를 줄여서 속도를 향상하는 것이다.
계산한 값들을 재사용하기 위해 보관하는 곳을 캐시(cache) 라고 하는데 우리는 부분 문제의 값들을 여기에 저장한다.
이처럼 함수의 결과를 마련 해두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법을 메모이제이션(memoization) 이라고 부른다.
메모이제이션을 적용할 수 있는 경우
이렇게 좋은 방법을 매번 쓸 수 있다면 정말 좋겠지만 역시 사용할 수 있는 조건이 필요하다. 다음을 보자.
프로그래밍에서 사용하는 함수는 수학의 함수와 의미가 조금 다르다. 수학에서의 함수는 입력이 같다면, 출력도 같다는 걸 보장해주지만, 프로그래밍에서는 전역 변수, 입력 파일, 클래스의 멤버 변수 등에 의해 입력이 같아도 출력이 같지 않을 수 있다.
따라서 우리가 구하는 부분 문제들이 입력에 대해 출력이 같다고 보장되는 참조적 투명성(referential transparency) 을 지킬 때 메모이제이션을 적용할 수 있다.
DP 접근법
사람은 똑똑하지 않으니, 항상 단계별로 문제를 풀어나가야 한다.
- 주어진 문제를 완전 탐색을 이용해 해결.
- 참조적 투명성을 만족한다면 메모이제이션을 적용하여 속도 향상.
즉, 모든 걸 일일이 탐색하는 코드로 짜고 문제가 중복된다고 생각하면 메모이제이션을 적용하는 것이다. (머리가 좋다면 단번에 메모이제이션을 적용하지만, 이는 많은 경험이 필요할 것이다)
정리
문제를 나누어 계산할때 부분 문제들이 같은 답을 낼 경우, 이를 중복 된다고 하는데 이 경우 메모이제이션 을 이용하여 캐시 에 값을 저장하는 것이다. 그래서 다음 번 같은 문제를 만난 경우 노트에서 적어뒀던 답을 찾듯이 캐시에서 그 값을 찾는 것이다. 우리는 이를 기억하며 풀기 즉, Dynamic Programming이라고 한다.
참고
이 내용은 90% 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략에서 발췌한 내용입니다.
이광근 교수의 저서 “컴퓨터 과학이 여는 세계”에서는 다이나믹 프로그래밍을 본질적인 의미를 더 살려서 기억하며 풀기 로 더욱 적절하게 번역하였다.
