1. 동적 계획법(Dynamic Programming) 개요
동적 계획법은 복잡한 문제를 더 간단한 여러 개의 하위 문제로 나누어 푸는 방법론입니다.
이 기법은 주로 최적화 문제를 해결할 때 유용하며, 잘 정의된 규칙을 통해 문제를 반복적으로 해결합니다.
일반적으로 동적 계획법은 두 가지 조건을 충족해야 합니다:
- Optimal Substructure: 문제의 최적 해결 방법이 하위 문제의 최적 해결 방법으로 구성되어야 합니다.
- Overlapping Subproblems: 하위 문제가 여러 번 계산되는 경우가 발생해야 합니다.
2. 동적 계획법을 사용하는 경우
동적 계획법은 다음과 같은 경우에 주로 사용됩니다:
- 피보나치 수열 계산
- 최장 공통 부분 문자열(Longest Common Subsequence)
- 최소 편집 거리(Minimum Edit Distance)
- 배낭 문제(Knapsack Problem)
3. 알고리즘 문제: 배낭 문제(Knapsack Problem)
이제, 동적 계획법을 활용한 배낭 문제를 더 깊이 살펴보겠습니다. 이 문제는 주어진 무게 제한 내에서 최대 가치를 가져가는 아이템 선택 문제입니다.
문제 설명
가방의 무게 제한이 주어질 때, 각 아이템의 무게와 가치를 알고 있을 때 가방에 넣을 수 있는 아이템의 조합으로 최대 가치를 구하는 문제입니다.
입력은 다음과 같은 형태입니다:
- n: 아이템의 수
- W: 가방의 최대 무게
- weight[]: 각 아이템의 무게 배열
- value[]: 각 아이템의 가치 배열
입력 예시
n = 4
W = 7
weight[] = {1, 2, 3, 2}
value[] = {20, 5, 10, 40}
출력 예시
최대 가치: 60
4. 동적 계획법을 이용한 해결 과정
이 문제를 해결하기 위해 우리는 동적 계획법의 기본 아이디어를 적용합니다.
아이템을 하나씩 선택하면서 현재 가방에 담을 수 있는 무게를 고려하여 최대 가치를 계산합니다.
4.1 DP 테이블 초기화
DP 테이블은 2차원 배열로 초기화할 것입니다. 여기서 dp[i][j]는 i번째 아이템까지 고려했을 때 최대 무게 j에 대한 최대 가치를 저장합니다.
초기값은 모두 0으로 설정됩니다.
4.2 상태 전이
아이템을 포함할 경우와 포함하지 않을 경우 두 가지로 나누어 상태 전이를 정의합니다.
각 아이템 i에 대해 다음 두 가지 조건을 만족하는 경우 최대 가치를 계산합니다:
- 아이템
i를 포함하지 않는 경우:dp[i][j] = dp[i-1][j] - 아이템
i를 포함하는 경우:dp[i][j] = dp[i-1][j-weight[i-1]] + value[i-1](단,j >= weight[i-1])
4.3 최종 구현
이제 코틀린을 사용하여 위의 논리를 구현하겠습니다.
fun knapsack(n: Int, W: Int, weight: IntArray, value: IntArray): Int {
val dp = Array(n + 1) { IntArray(W + 1) }
for (i in 1..n) {
for (w in 0..W) {
if (weight[i - 1] <= w) {
dp[i][w] = maxOf(dp[i - 1][w],
dp[i - 1][w - weight[i - 1]] + value[i - 1])
} else {
dp[i][w] = dp[i - 1][w]
}
}
}
return dp[n][W]
}
5. 복잡도 분석
이 알고리즘의 시간 복잡도는 O(nW), 공간 복잡도 또한 O(nW)입니다.
여기에서 n은 아이템의 수, W는 가방의 최대 무게입니다.
그러나 공간 복잡도를 최적화할 수 있는 방법도 있습니다.
5.1 공간 복잡도 최적화 방법
현재 dp[i][j]는 이전 행의 정보만 필요하므로, 1차원 배열로 최적화할 수 있습니다.
fun knapsackOptimized(n: Int, W: Int, weight: IntArray, value: IntArray): Int {
val dp = IntArray(W + 1)
for (i in 0 until n) {
for (w in W downTo weight[i]) {
dp[w] = maxOf(dp[w], dp[w - weight[i]] + value[i])
}
}
return dp[W]
}
6. 결론
동적 계획법은 다양한 문제를 효율적으로 해결할 수 있는 강력한 도구입니다.
배낭 문제를 통해 동적 계획법의 개념과 구현 방법을 배웠습니다.
앞으로 다른 문제를 통해 추가적인 연습과 학습을 이어가길 바랍니다.
이 글이 코틀린을 사용한 코딩테스트 준비에 도움이 되길 바랍니다. 최적의 솔루션을 찾기 위해 꾸준히 학습하고 연습하세요!