•
DP 알고리즘은 복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 기법
•
DP 알고리즘은 메모이제이션 기법을 활용하여 중복된 계산을 줄임으로써 답을 구해나간다.
◦
메모이제이션 기법은 동일한 계산을 반복해야 하는 경우에 한 번 계산한 결과를 저장해 두었다가 다시 씀으로써 중복 계산을 방지하는 기법
•
DP 알고리즘의 핵심은 문제의 재귀적인 구조(관계식)를 찾는 데에 있다.
◦
문제의 재귀적인 구조를 찾아 중복된 계산을 줄일 수 있기 때문이다.
•
DP 알고리즘 적용을 위한 3단계
1.
문제의 재귀적인 구조 파악
2.
수식으로 표현
3.
초기값 처리
•
DP table : 메모이제이션 기법을 활용하기 위해 값을 저장하는 공간
[예시 문제]
동전 1원, 3원, 4원을 가지고 N원을 만들어야 한다.
최소한의 동전의 갯수로 N원을 만드는 경우를 출력하는 프로그램을 작성하라
•
DP 알고리즘은 쓰이는 상황이 구체적이지 않고 재귀적인 구조를 파악해야 하므로 문제 해결 능력을 키우는 것이 중요하다.