동적 계획법 (Dynamic Programming)
수정하기
문서 생성 2021-11-20 09:48:35 최근 수정 2022-04-29 20:53:09
- 동적 계획법 고안자인 벨만(Richard E. Bellman)은 dynamic이란 단어가 멋있어서 선택했다고 한다. 그래서 전산학 전반에서 일반적으로 사용하는 동적(dynamic)과 프로그래밍(programming)과는 전혀 관련이 없는 의미이다.
- Programming은 최적화 연구 분야에서 최적의 프로그램을 찾아낸다는 의미
- 동적 계획법은 분할 정복과 같은 접근 방식을 의미한다. 동적 계획법은 어떤 부분 문제가 다른 부분 문제를 푸는 데 사용할 수 있을 때 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용해서 속도의 향상을 꾀하는 알고리즘 설계 기법이다.
- 한 번 계산한 값을 저장해 뒀다가 다시 재활용하는 최적화 기법을 메모이제이션(memoization)이라고 부른다.
- 재귀 호출을 사용하는 방법을 탑다운(top-down) 방식이라 부른다.
- 가장 먼저 호출하는 문제가 가장 큰 문제이기 때문에
- 반복문을 사용하는 방법을 바텀업(bottom-up) 방식이라 부른다.
- 작은 문제부터 차례차례 값을 확인하기 때문에