[Java] 동적 계획법 (DP: Dynamic programmig) 이해하기 <적용문제>
1. 동적 계획법이란?
동적 계획법(Dynamic programming)은 중복 계산을 줄이기 위해 작은 문제들을 풀면서
그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘을 말한다.
해당 알고리즘의 특징은 메모이제이션(Memoization) 기법을 사용하여 중복 계산을 피하고,
경우의 수가 많은 경우에도 효율적으로 계산할 수 있다. 일반적으로 재귀적으로 구현된다.
메모이제이션(Memoization) 이란?
이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 속도를 빠르게 하는 방법이다.
동적 계획법 알고리즘을 구현할때 다음과 같은 단계를 따른다.
1. 문제를 하위 문제로 쪼갠다.
2. 하위 문제를 재귀적으로 해결한다.
3. 결과를 저장한다. (메모이제이션)
4. 저장된 결과를 이용하여 큰 문제를 해결한다. (해당 단계를 통해서 중복 계산을 피한다.)
2. DP 문제가 성립할 조건
최적 부분 구조(Optimal Substructure)
- 작은 문제의 최적해를 구한 후 그것을 이용하여 큰 문제의 최적해를 구할 수 있다.
중복 부분 문제(Overlapping Subproblem)
- 동일한 작은 문제를 반복적으로 해결해야 하는 성질이다.
3. 동적 계획법의 종류 (탑다운, 바텀업)
Top-down
큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이다. 이 때 해결해 놓은 하위
문제를 저장해 놓기 위해 메모이제이션(Memoization)이 사용된다. 이는 중복 계산을 방지
하고 작은 문제들을 한 번만 푸는 것이 특징이다.
Bottom-up
작은 문제부터 차례대로 해결해 나가는 방식이다.
이 알고리즘의 핵심은 이전에 '계산한 부분 문제'의 결과를 저장해두고 나중에 같은 부분
문제가 나타날 때 다시 계산하지 않고 저장된 값을 사용하여 시간을 절약한다.
탑다운 방식과 바텀업 방식은 동일한게 아닌가?
아니다. 둘다 동일한 계획적 탐색의 종류 중에 하나지만 각각 해결방식이 다르다.
탑다운 방식은 작은 부분 문제를 '재귀적인 호출'을 이용하여서 해결하는 방식이고,
바텀업 방식은 작은 부분 문제부터 시작하여 '반복문'을 통해 해를 계산하고 저장해둔
뒤 이전에 계산 문제의 해를 점점 더 큰 문제로 해결하는 방식이다.
<적용문제>
Top-down 방식으로 풀면 된다.
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
<참조>