[Algorithm] 다이나믹 프로그래밍 DP 잘 풀어보기
DP는 복잡한 문제를 작은 부분 문제로 나누어 일반화 하여 해결하는 알고리즘 기법이다.
문제를 엄청 작은 부분 문제로 나누어본다는 이야기는 구하고자 하는 값을 "점화식"을 세워서 해결할 수 있다는 것이다. 뭔가 불가능해보이지만, 노트에 써서 어떤 규칙이 보이면, 그 규칙을 가지고 점화식을 세워서 풀 수 있다는 이야기이다. 초항 또는 두 번째 항을 구한 후 나머지 항을 계속 구해가다가 원하는 값에 도달하면 결과를 얻을 수 있을 것이다.
대체적으로 DP를 이야기할 때 가장 먼저 이야기 하는 것은 피보나치 수열이다.
피보나치 수열은 a1 = 1, a2 = 1이고, A(n) = A(n-2) + A(n-1)을 점화식으로 한다. 직전, 2직전 항을 더할 경우 현재항이 나오게 되는 구조인 것이다. 이와 같은 문제들은 너무나 많고, 다양하게 나올 수 있다. 이번 포스팅에서는 DP 문제의 판별 방법과 접근 방법(점화식 도출), 예시를 살펴보도록 할 것이다.
1. DP 문제 판별 방법
DP 문제는 그리디와 비슷한 부분이 없지 않아 있다.
1) 최적 부분 구조
: 문제를 작은 부분 문제로 나누었을 때, 그 부분 문제의 답을 이용해 전체 문제의 답을 찾아낼 수 있는지를 확인해야 한다.
: 부분 문제를 해결하면 전체 문제를 해결할 수 있는지를 확인한다.
2) 중복 부분 문제
: 동일한 작은 부분 문제가 여러 번 반복해서 계산되는지 확인해야 한다.
: 피보나치 수열에서 가지를 뻗어나가면, f(3)을 여러 번 계산해야 하는 것 처럼.
: 이 부분이 그리디와 DP를 갈라주는 부분이라고 할 수 있겠다.
: DP는 중복되는 부분을 계산하지 않고, 빠르게 연산하여 지수 시간 내에 연산을 끝내는 방법으로 진행한다.
3) 제한 조건이 복잡함
: 그리디보다는 문제의 제한 조건이 복잡한 편이 많다. 최적화 문제에 쓰이는 경우가 많다.
2. DP 문제 접근 방법
문제 이해 -> 상태 정의 -> 초기 조건 설정 -> 점화식 유도 -> 최적해 결정 -> 구현
위의 절차에 따른다.
1) 문제 이해
- 문제의 정의: 문제를 정확히 이해하고, 입력과 출력 조건을 명확히 파악한다.
- 목표: 최종적으로 무엇을 구해야 하는지 명확히 해야 한다. 예를 들어, 최솟값, 최댓값, 가능한 경우의 수 등.
가장 힘들 수 있는 부분으로, 정확히 조건을 파악해내고, 어떤 것을 구해야 하는지 꼼꼼히 적어놓아야 한다.
아니면 구현하고 있는데, 문제 조건을 잘못봐서 다시 풀어낼 수도 있다. 기초적인 이해를 반드시 해야 하는 측면도 있으며, 상태정의에 필요한 정보들을 획득할 수 있으니, 꼭 이해를 모두 하고, 파악을 하고 넘어가야 한다.
2) 상태 정의
- DP 배열 정의: 문제를 해결하기 위해 필요한 상태를 정의한다. 예를 들어, dp[i]는 i번째 항을 의미할 수 있다.
- 1차원 배열: dp[i]가 i번째 상태를 나타냄
- 2차원 배열: dp[i][j]가 i번째와 j번째 상태를 나타냄
- 상태 설명: 각 상태가 무엇을 의미하는지 명확히 설명한다.
점화식을 세우는 것이 아니라, 그 점화식으로 무엇을 얻어낼 지를 정의하는 것이다. 편의상 배열 이름을 dp라고 한다. 이때, 구하고자 하는 i번째의 값을 반환할 수 있을 것을 dp라고 정의해도 되고, 구하는 것이 여려 개라면 그 배열의 인덱스를 가지고 있는 배열이라고 해도 된다. 문제마다 다를 수 있기 때문에, 문제 이해를 잘 하고, 구하고자 하는 것에 따라 상태 정의를 달리하면 될 것이다.
3) 초기 조건 설정
- 기본값 설정: DP 배열의 초기 조건을 설정. 이는 가장 작은 문제를 의미한다.
- 예를 들어, 피보나치 수열에서는 dp[0] = 0, dp[1] = 1로 설정한다.\
기본값이 있어야 점화식을 풀 수 있다. 이는 문제에서 주어진 예시나 문제 이해를 통해 도출해 낼 수 있을 것이다.
4) 점화식 유도
- 문제 분할: 문제를 작은 부분 문제로 나누고, 이들 간의 관계를 파악.
- 상태 전이: 현재 상태와 이전 상태(또는 부분 문제들) 간의 관계를 찾는다. 이를 통해 점화식을 유도.
- 예를 들어, 피보나치 수열의 경우 dp[n] = dp[n-1] + dp[n-2]
- 일반화: 특정 예제를 통해 유도된 점화식을 일반화하여 전체 문제에 적용한다.
가장 어려운 부분이다. 만약 아래에 나올 동전 1 문제 같은 경우, 아직도 잘 이해가 안되는데, 반복문을 왜 두번을 돌아서, dp 배열은 1차원만 쓰는지... 점화식을 정확히 정의해놓으면, 이런 뒤의 구현들이 편리해진다.
5) 최적해 결정
- 최종 상태 확인: 문제에서 구하고자 하는 최종 상태를 확정한다. 이는 DP 배열의 어떤 값을 의미하는지 명확히 하는 것이다.
- 예를 들어, 피보나치 수열에서는 dp[n]이 최종 값
전체 점화식을 짜두고, 상태 정의 했던 것을 점화식과 연관지어보고, dp 정의를 마친다.
6) 구현 및 검증
- 구현: 유도된 점화식을 바탕으로 코드를 구현
- 테스트: 다양한 입력값을 통해 코드가 올바르게 동작하는지 검증
5)에서까지 빌드된 로직을 실제로 구현하는 것이다.
위의 단계를 축소하여 진행할 수도 있고, 아니면 한 번에 팍 떠올라서 문제를 풀 수도 있다.
실제로, 점화식을 알고 있는 문제를 만나는 경우, DP는 구현이 어렵지 않기 때문에 금방 풀 수 있다.
다만, 어려운 수학문제처럼 생각을 오래해야 하는 것뿐이다.
3. 예시 문제
DP는 문제들이 엄청 많다. 그중 쉬운문제부터 쉬워보이지만 힘든 문제들을 소개한다.
0) 피보나치(백준 1003)
func solution_1003() {
let t = Int(readLine()!)!
var arr = [Int]()
for _ in 1...t {
arr.append(Int(readLine()!)!)
}
var zeroArr = [1, 0]
var oneArr = [0, 1]
for i in 2...40 {
zeroArr.append(zeroArr[i-2] + zeroArr[i-1])
oneArr.append(oneArr[i-2] + oneArr[i-1])
}
for i in arr {
print("\(zeroArr[i]) \(oneArr[i])")
}
}
가장 익히 알고 있는 피보나치이다.
다만, 단순하게 구하는 것이 아니라, dp의 과정에서 얻어지는 하위값들 중 0, 1의 개수에 대해 물어보고 있다.
"0, 1이 구해지는 것도 부분의 연산의 결과 값이 계속 누적되어 뒤에 영향을 미친다."
는 것을 코드에 잘 반영해주면 된다.
1) 계단 오르기(백준 2579)
func solution_2579() {
let n = Int(readLine()!)!
var arr = [Int](repeating: 0, count: n + 1)
var dp = [Int](repeating: 0, count: n + 1)
for i in 1...n {
arr[i] = Int(readLine()!)!
}
dp[1] = arr[1]
if n > 1 {
dp[2] = arr[1] + arr[2]
}
if n > 2 {
for i in 3...n {
dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i])
}
}
print(dp[n])
}
한 번에 두 계단 상승 또는 한 계단을 상승할 수 있는데, 한개 - 한개 올라갈 수는 없다.
마지막 도착 계단은 반드시 밟아야 하고, 시작점은 계단에 포함이 안 된다는 조건이 있다.
이 두 개의 조건을 고려해보면,
두 번째 아래 계단에서 현재로 점프한 상황과
하나 아래 계단에서 현재로 올라온 상황을 생각해볼 수 있다.
그 둘 중 최댓값에 현재의 계단 점수를 합하면 현재까지 올라온 계단의 최대 점수임을 보장할 수 있다.
초기값을 dp[2]까지 구해놓았기 때문에, dp[3]부터 값을 구해준다. 이를 고려하여 반복문 내부의 조건을 잘 설정해주면 답을 구할 수 있다.
2) 정수 삼각형(백준 1932)
// 정수 삼각형(최대 값을 가진 합 추출)
func solution_1932() {
let n = Int(readLine()!)!
var arr = [[Int]]()
var dp = [[Int]](repeating: [Int](repeating: -1, count: n), count: n)
for _ in 1...n {
arr.append(readLine()!.split(separator: " ").compactMap { Int($0) })
}
print(dynamicProgram(0, 0))
func dynamicProgram(_ idx: Int, _ depth: Int) -> Int {
if depth == n - 1 {
dp[depth][idx] = arr[depth][idx]
return arr[depth][idx]
}
if dp[depth][idx] == -1 {
let maxVal = max(dynamicProgram(idx, depth + 1), dynamicProgram(idx + 1, depth + 1)) + arr[depth][idx]
dp[depth][idx] = maxVal
return maxVal
} else {
return dp[depth][idx]
}
}
}
합이 최대가 되는 경로에 있는 수의 합을 출력해야 된다. 대각선 왼쪽 또는 오른쪽에 있는 것 중 선택할 수 있다.
이차원 배열의 행을 하나 내려가서, i번째와 i + 1번째의 값을 확인해주면 될 것이다. 재귀적으로 맨 아래까지 내려갔다가, 올라오는 과정에서는 max값을 dp에 저장해주면서 올라오면 된다.
3) RGB 거리
// RGB 거리(최소비용 찾기)
func solution_1149() {
let n = Int(readLine()!)!
var arrR = [0]
var arrG = [0]
var arrB = [0]
for _ in 1...n {
let arr = readLine()!.split(separator: " ").compactMap { Int($0) }
arrR.append(arr[0])
arrG.append(arr[1])
arrB.append(arr[2])
}
var dp = [[Int]](repeating: [Int](repeating: 0, count: 3), count: n + 1)
dp[1][0] = arrR[1]
dp[1][1] = arrG[1]
dp[1][2] = arrB[1]
for i in 2...n {
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arrR[i]
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arrG[i]
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arrB[i]
}
print(dp[n].min()!)
}
각 집을 빨강(R), 초록(G), 파랑(B)으로 색칠할 때, 인접한 집끼리 다른 색이 되도록 하면서 전체 비용을 최소화하는 문제다.
dp[i][0], dp[i][1], dp[i][2]는 i번째 집까지 각각 빨강, 초록, 파랑으로 색칠했을 때의 최소 비용을 저장한다.
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + R[i]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + G[i]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + B[i]
현재 칠하는 집이 빨강이면, 이전 집은 초록 또는 파랑이어야 하는 점을 이용한다.
4) 동전 1
// 동전 1(DP)
func solution_2293() {
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
let n = input[0]
let k = input[1]
var coins = [Int]()
var dp = [Int](repeating: 0, count: k + 1)
dp[0] = 1
for _ in 0..<n {
coins.append(Int(readLine()!)!)
}
for c in coins {
for i in stride(from: c, to: k + 1, by: 1) {
dp[i] = (dp[i] + dp[i - c]) % 2100000000
}
}
print(dp[k])
}
5) 평범한 배낭
func solution_12865() {
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
let (n, k) = (input[0], input[1])
var arr: [[Int]] = []
var dp = [[Int]](repeating: [Int](repeating: 0, count: k + 1), count: n + 1)
for _ in 1...n {
arr.append(readLine()!.split(separator: " ").compactMap { Int($0) })
}
for i in 1...n {
let (weight, value) = (arr[i - 1][0], arr[i - 1][1])
for w in 0...k {
if w >= weight {
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value)
} else {
dp[i][w] = dp[i - 1][w]
}
}
}
print(dp[n][k])
}
/**
점화식
dp[i][w]는 i번째 아이템까지 고려했을 때, 배낭의 허용 무게가 w일 때 얻을 수 있는 최대 가치를 의미합니다.
다음과 같은 점화식을 사용할 수 있습니다:
현재 아이템 i를 선택하지 않는 경우: dp[i][w] = dp[i-1][w]
현재 아이템 i를 선택하는 경우:
이때, i번째 아이템의 무게가 w보다 작거나 같은 경우, 즉 w >= weight[i]
선택했을 때의 가치는 dp[i-1][w-weight[i]] + value[i]
따라서, 최종 점화식은 다음과 같습니다:
dp[i][w]=max(dp[i−1][w],dp[i−1][w−weight[i]]+value[i])
단, w < weight[i]일 경우에는 아이템 i를 선택할 수 없으므로:
dp[i][w]=dp[i−1][w]
초기 조건
dp[0][w]는 0으로 초기화합니다. (0개의 아이템을 고려할 때 얻을 수 있는 최대 가치는 0입니다)
dp[i][0]도 0으로 초기화합니다. (배낭의 허용 무게가 0일 때 얻을 수 있는 최대 가치는 0입니다)
*/
4. 마치며
DP는 점화식 추출에 어려움이 많다. 가장 많은 시간을 써야 하기도 한다.
풀이 중에 특이 케이스를 걸러내기 위해 조건문을 과다 투어하여 전체 코드의 길이가 과하게 길어진다면 잘못 구현하고 있을 가능성이 99%이다. 그렇기 때문에, 구현 전에 탄탄하게 점화식을 짜놓고, 간단한 증명을 해본 다음, 구현을 하는 것이 필요하다.
DP 구현은 그렇게 어렵지 않으니까!
'Algorithm' 카테고리의 다른 글
| [Algorithm] Swift로 그리디 풀이해보기 (0) | 2024.06.29 |
|---|---|
| [Algorithm] BFS 떠올리기, Swift로 구현하기 (0) | 2024.06.28 |
| [Algorithm] 우선 순위 큐 Swift 구현 (0) | 2024.04.04 |
| [Algorithm] 기수 정렬(Radix Sort) 알고리즘(Swift 구현) (0) | 2023.03.08 |
| [Algorithm] 힙 정렬(Heap Sort) 알고리즘(Swift 구현) (0) | 2023.02.22 |
댓글