다이나믹 프로그래밍(DP)이란?
여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 (점화식 필요)
DP를 푸는 과정
- 테이블 정의하기
- 점화식 찾기
- 초기값 정하기
-> 매번 점화식이 돌아갈 수 있게 하기 위한 초기값이 어디까지인지를 잘 고민해서 초기값 적용 필요
📍 점화식 구하는 게 어려우면 테이블만 정의해놓고 직접 테이블을 채워보자
예시 문제
1) BOJ 1463번: 1로 만들기(링크)
- 테이블 정의하기
D[i] : i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 - 점화식 찾기
3으로 나눠지면 3으로 나누기 -> D[k] = D[k/3] + 1
2로 나눠지면 2로 나누기 -> D[k] = D[k/2] + 1
1을 빼기 -> D[k] = D[k-1] + 1 - 초기값 정의하기
D[1] = 0
2) BOJ 9095번: 1, 2, 3 더하기(링크)
- 테이블 정의하기
D[i] : i를 1, 2, 3의 합으로 나타내는 방법의 수 - 점화식 찾기
D[i] = D[i-1] + D[i-2] + D[i-3] - 초기값 정의하기
D[1] = 1
D[2] = 2
D[3] = 4
3) BOJ 2579번: 계단 오르기(링크)
- 테이블 정의하기
D[i][j] : 현재까지 j개(j = 1, 2)의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의 최댓값 (단, i번째 계단은 반드시 밟아야 함)D[i]를 i번째 계단으로 올라섰을 때의 점수 합의 최댓값으로 정하면, 연속된 세 개의 계단을 모두 밟아서는 안된다는 조건을 만족할 수 없다!
- 점화식 찾기
D[k][1] = max(D[k-2][1], D[k-2][2]) + S[k]
D[k][2] = D[k-1][1] + S[k]
(S[k]는 계단에 적힌 점수) - 초기값 정의하기
D[1][1] = S[1]
D[1][2] = 0
D[2][1] = S[2]
D[2][2] = S[1] + S[2]
1차원 배열
- 테이블 정의하기
D[i] : i번째 계단까지 올라섰을 때 밟지 않을 계단의 점수 합의 최솟값 (단, i번째 계단은 반드시 밟지 않을 계단으로 선택해야 함) - 점화식 찾기
D[k] = min(D[k-2], D[k-3]) + S[k]
(S[k]는 계단에 적힌 점수)k번째 계단을 밟지 않으려면 k-2번째 계단이나 k-3번째 계단을 밟지 않아야 함
- 초기값 정의하기
D[1] = S[1]
D[2] = S[2]
D[3] = S[3]D[N-1]을 구하면 됨
📍 관점을 달리하면 또다른 점화식을 구할 수 있음
4) BOJ 1149번: RGB거리(링크)
- 테이블 정의하기
D[i][0] : i번째 집까지 칠할 때 비용의 최솟값 (단, i번째 집은 빨강)
D[i][1] : i번째 집까지 칠할 때 비용의 최솟값 (단, i번째 집은 초록)
D[i][2] : i번째 집까지 칠할 때 비용의 최솟값 (단, i번째 집은 파랑)인접한 집끼리 색상이 달라져야 하기 때문에 색상에 대한 정보를 테이블에 넣어야 함
- 점화식 찾기
D[k][0] = min(D[k-1][1] + D[k-1][2]) + R[k]
D[k][1] = min(D[k-1][0] + D[k-1][2]) + G[k]
D[k][2] = min(D[k-1][0] + D[k-1][1]) + B[k] - 초기값 정의하기
D[1][0] = R[1]
D[1][1] = G[1]
D[1][2] = B[1]
5) BOJ 11726번: 2×n 타일링(링크)
- 테이블 정의하기
D[i] : 2×i 크기의 직사각형을 채우는 방법의 수 - 점화식 찾기
D[n] = D[n-1] + D[n-2] - 초기값 정의하기
D[1] = 1
D[2] = 2
6) BOJ 11659번: 구간 합 구하기 4(링크)
Prefix Sum
: 문제를 풀면서 시간복잡도를 줄이는 데에 사용될 수 있음
D[i] = D[i-1] + A[i]
답: D[j] - D[i-1]
7) BOJ 12852번: 1로 만들기 2(링크)
테이블 추가하기
pre[i] = i가 되기 위해 바로 직전에 거쳐온 숫자
Grow up everyday