•
개념
◦
다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록하는 알고리즘이다.
◦
큰 문제를 작은 문제로 쪼개서 해결하는 과정에서, 작은 문제를 단 한 번만 푸는 것이다.
•
사용 조건
◦
DP가 적용되기 위해서는 2가지 조건을 만족해야 한다.
▪
Overlapping Subproblems
▪
Optimal Substructure
◦
Overlapping Subproblems
▪
DP는 기본적으로 문제를 이미 연산이 종료된 최소 단위로 나누어 전체 답을 계산한다. 따라서 동일한 작은 문제들이 반복해서 나타나는 경우 사용 가능하다.
▪
이진 탐색과 피보나치 수열을 예로 들 수 있다.
•
이진 탐색은 특정 데이터를 정렬된 배열 내에서 그 위치를 찾기 때문에 그 위치를 찾은 후 바로 반환할 뿐 재사용하지는 않는다.
•
피보나치 수열은 특정 값에 대한 연산이 반복적으로 나타나는 구조이다.
◦
Optimal Substructure
▪
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다.
•
그리디에서 본거 그거 맞다
◦
DP는 특정한 경우에 사용하는 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰일 수 있다.
◦
일반적으로 DP를 사용하기 전에는 아래의 과정을 거쳐 진행할 수 있다.
▪
1) DP로 풀 수 있는 문제인지 확인한다.
•
위 조건들에 부합하는 문제인지 확인해야 한다.
•
보통 특정 데이터 내에서 최대화, 최소화 계산을 하거나 데이터를 세야한다거나 확률 등의 계산의 경우에 DP를 사용할 수 있다.
▪
2) 문제의 변수 파악
•
현재 변수에 따라 그 결과 값을 찾고 전달하여 재사용하는 것이 DP다. 즉 문제 내 변수의 개수를 알아내야한다는 것인데, 이를 state를 결정한다고 한다.
◦
피보나치 수열에서는 n 번째 숫자를 구하는 것이므로 n이 변수가 된다.
▪
3) 변수 간 관계식 만들기(점화식)
•
변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일하다. 그 결괏값을 그대로 이용하므로 그 관계식을 만들어낼 수 있어야 한다.
▪
4) 메모하기(memoization or tabulation)
•
변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장해야한다. 이를 메모이제이션이라고 한다.
•
이 결과 값을 저장할때는 보통 조회가 빠른 배열을 사용하며 배열의 차원은 변수의 갯수에 따라 다양할 수 있다.
▪
5) 기저 상태 파악하기
•
가장 작은 문제에 대한 결괏값을 알아내야 한다. 보통 직접 계산해보는 경우가 많다.
▪
6) 구현하기
•
DP는 보통 2가지 방식으로 구현된다.
◦
Bottom-Up - 반복문 사용
◦
Top-Down - 재귀 사용
