코딩테스트에서 알고리즘 문제를 효과적으로 해결하는 방법 중 하나는 동적 계획법(Dynamic Programming, DP)입니다. 동적 계획법은 복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 접근 방식으로, 최적화 문제를 해결하고 계산을 줄이는 데 매우 유용합니다. 이번 강좌에서는 동적 계획법의 기초부터 시작하여 실제 문제를 통해 이론을 살펴보고, C# 프로그래밍 언어를 사용하여 문제를 해결하는 방법을 단계별로 설명하겠습니다.
동적 계획법의 이해
동적 계획법은 기본적으로 두 가지 중요한 성질인 최적 부분 구조와 중복 쌍 문제를 활용합니다. 최적 부분 구조는 문제의 최적 해결 방법이 그 하위 문제의 최적 해결 방법으로 구성된다는 것을 의미합니다. 중복 쌍 문제는 동일한 하위 문제를 여러 번 해결하는 대신, 그 결과를 저장하여 필요할 때 재사용하는 것입니다. 이를 통해 효율성을 획기적으로 높일 수 있습니다.
동적 계획법의 적용 예시
동적 계획법은 다음과 같은 문제에 사용됩니다:
- 피보나치 수열 계산
- 최장 공통 부분 수열(longest common subsequence)
- 최소 경로 문제
- 0-1 배낭 문제
- 동적 행렬 곱셈
문제 소개: 0-1 배낭 문제
이번 강좌에서는 0-1 배낭 문제를 통해 동적 계획법을 적용해 보겠습니다. 문제는 다음과 같이 설명됩니다:
무게의 제한이 있는 배낭이 있습니다. 각 아이템은 고유한 무게와 가치를 가집니다. 각 아이템은 0개 또는 1개만 사용할 수 있으며, 배낭에 담을 수 있는 최대 가치는 무엇인지 계산하세요.
예시로 다음과 같은 아이템 목록이 있다고 가정해 봅시다:
| 아이템 | 무게 | 가치 |
|---|---|---|
| 아이템 1 | 1 | 1 |
| 아이템 2 | 2 | 6 |
| 아이템 3 | 3 | 10 |
| 아이템 4 | 5 | 16 |
배낭의 최대 무게는 7입니다. 이 경우 최대 가치는 얼마일까요?
문제 풀이 과정
1단계: 문제 정의
우리는 재귀적인 사고 방식으로 문제를 해결하려고 할 수 있지만, 이는 중복된 계산을 야기할 수 있습니다. 따라서, 동적 계획법을 사용하여 하위 문제의 해결책을 저장하고 재사용하는 방식으로 접근합니다.
2단계: 상태 정의
먼저 우리가 해결해야 할 문제를 정의합니다. dp[i][w]를 사용하여 첫 i개의 아이템을 고려했을 때, 무게 w를 초과하지 않으면서 최대 가치를 저장합니다. i는 아이템의 인덱스, w는 배낭의 무게입니다.
3단계: 상태 전이 방정식
이제 상태 전이 방정식을 정의해야 합니다. i 번째 아이템을 포함하는 경우와 포함하지 않는 경우를 나누어 생각합니다.
- 아이템 i를 포함하지 않을 경우: dp[i][w] = dp[i-1][w]
- 아이템 i를 포함할 경우(이때 아이템의 무게가 w를 넘어서는 안 됨): dp[i][w] = dp[i-1][w – weight[i]] + value[i]
최종적으로, 두 경우 중 최대값을 선택합니다:
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
4단계: 초기 조건 정의
기본적으로 아이템이 없거나 무게가 0인 경우에는 최대 가치는 0입니다. 따라서 다음과 같이 초기화합니다:
for w in range(max_weight + 1):
dp[0][w] = 0
for i in range(n + 1):
dp[i][0] = 0
5단계: 최종 솔루션
모든 하위 문제를 해결한 후, dp 배열의 마지막 요소는 최적의 해를 나타냅니다. 이를 출력하여 결과를 확인합니다.
6단계: C# 코드 구현
using System;
class Program
{
static void Main(string[] args)
{
int[] weights = new int[] { 1, 2, 3, 5 };
int[] values = new int[] { 1, 6, 10, 16 };
int maxWeight = 7;
int n = weights.Length;
int[,] dp = new int[n + 1, maxWeight + 1];
// 초기화
for (int w = 0; w <= maxWeight; w++)
dp[0, w] = 0;
for (int i = 0; i <= n; i++)
dp[i, 0] = 0;
// 동적 계획법 적용
for (int i = 1; i <= n; i++)
{
for (int w = 1; w <= maxWeight; w++)
{
if (weights[i - 1] <= w)
dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - weights[i - 1]] + values[i - 1]);
else
dp[i, w] = dp[i - 1, w];
}
}
Console.WriteLine("최대 가치: " + dp[n, maxWeight]);
}
}
결과 확인
위 코드를 실행하면 주어진 배낭 문제에 대한 최대 가치를 출력하게 됩니다. 이 경우 결과는 17이 됩니다. 이는 아이템 2와 아이템 3을 선택하여 최대 무게를 초과하지 않으면서 최대 가치를 얻을 수 있음을 의미합니다.
결론
이번 강좌를 통해 동적 계획법의 기초와 0-1 배낭 문제를 해결하는 과정을 살펴보았습니다. 동적 계획법은 많은 알고리즘 문제에서 활용될 수 있으며, 문제 해결 능력을 키우는 데 큰 도움을 줄 것입니다. 연습을 통해 다양한 문제를 해결해 보시고, 더 깊이 있는 이해를 쌓으시길 바랍니다.
다음 강좌에서는 더 다양한 동적 계획법 응용문제를 다루어 보겠습니다. 감사합니다!