1. DP 알고리즘
•
DP(동적 계획법)란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 의미한다.
•
DP 알고리즘은 메모이제이션 기법을 이용하여 효율적으로 답을 구하는 알고리즘이다.
•
DP 알고리즘을 이용하려면 문제의 재귀적은 구조(관계식)를 파악해야 한다.
•
DP 알고리즘 기본 Flow
1.
문제의 재귀적인 구조 파악
2.
(수식으로 표현)
3.
(초기값 처리)
•
[문제]
동전 1원, 3원, 4원을 가지고 N원을 만들어야 한다.
최소한의 동전의 개수로 N원을 만드는 경우를 출력하는 프로그램을 적성하시오. 답이 여러 가지인 경우 아무 경우나 출력하시오.
(단, N은 1,000,000 이하의 자연수이고, 시간 제한은 1초이다.)
시간 제한이 1초이므로, 약 1억 번의 연산을 넘기면 안 됨.
1.
문제의 재귀적인 구조 파악
•
동전 i원을 만드는 상황은 i-1인 경우, i-3인 경우, i-4인 경우만 살펴보면 된다.
2.
수식으로 표현
•
3.
초기값 처리
•
관계식으로 접근할 수 없는 경우를 따로 처리해 주어야 한다.
python
2. 실제 문제에서 DP 알고리즘
•
문제를 보고 DP 알고리즘을 사용할 수 있는지 확인
◦
문제에서 재귀적인 구조(관계식)가 있는지 파악
•
문제의 재귀적인 구조가 없다면
◦
브루트 포스, 그리디, 수학과 같은 다른 방식의 접근이 필요함.
◦
(재귀적인 구조가 없는 게 아니라 못 찾은 것일 수도 있으니, 다시 한번 생각해 보기)
