동적 프로그래밍(Dynamic Programming)은 복잡한 문제를 여러 개의 하위 문제(sub-problems)로 나누어 접근하여 해결하는 방법입니다. 특히 최적화 문제를 해결할 때 유용하게 사용됩니다. 이번 글에서는 동적 프로그래밍을 활용하여 최적화 문제를 해결하는 방법을 파이썬으로 구현하는 예제 코드를 살펴보겠습니다.
예제: 배낭 문제(Knapsack Problem)
배낭 문제는 주어진 공간(배낭)에 가치가 있는 물건들을 담을 때, 최대의 가치를 얻을 수 있는 조합을 찾는 문제입니다. 각 물건은 무게와 가치를 가지고 있고, 배낭에는 최대 무게까지만 담을 수 있습니다.
def knapsack(W, wt, val):
n = len(wt)
K = [[0 for j in range(W + 1)] for i in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i - 1] <= w:
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
else:
K[i][w] = K[i - 1][w]
return K[n][W]
위의 코드는 동적 프로그래밍을 이용해 배낭 문제를 해결하는 함수입니다. 이 함수는 배낭의 최대 무게(W), 각 물건의 무게(wt)와 가치(val)를 인자로 받아 최대 가치를 반환합니다.
동적 프로그래밍의 원리
동적 프로그래밍의 핵심 아이디어는 작은 하위 문제의 해결을 통해 큰 문제의 해결을 도출하는 것입니다. 배낭 문제에서도 이 원리를 활용하여 모든 물건을 고려하여 배낭에 담을 때, 물건을 담는 경우와 담지 않는 경우를 모두 고려합니다. 이렇게 하위 문제들을 풀어나가면서 최적의 해결책을 찾아갈 수 있습니다.
위의 코드에서는 2차원 배열 K를 사용하여 각 하위 문제의 최적해를 저장하고 있습니다. 이 배열의 크기는 물건의 개수(n)와 배낭의 최대 무게(W)를 기준으로 설정되었습니다. K[i][w]는 i개의 물건을 고려하여 w만큼의 무게를 가진 배낭에 담았을 때의 최대 가치를 의미합니다.
또한, 코드에서는 각 하위 문제를 반복문을 통해 풀어나가고 있습니다. 첫 번째 반복문은 물건의 개수를, 두 번째 반복문은 배낭의 무게를 기준으로 하여 하위 문제를 접근합니다. 하위 문제를 풀 때에는 물건을 담을 수 있는 경우와 담을 수 없는 경우를 모두 고려하여 최대 가치를 계산합니다.
마지막으로, 코드는 K[n][W]를 반환하여 전체 물건을 고려하여 W만큼의 무게를 가진 배낭에 담았을 때의 최대 가치를 반환합니다.
결론
동적 프로그래밍은 복잡한 최적화 문제를 풀기 위한 강력한 도구입니다. 이번에는 배낭 문제를 예로 들어 동적 프로그래밍의 개념과 코드 작성 방법을 살펴보았습니다. 다양한 최적화 문제에 동적 프로그래밍을 적용해 볼 수 있으며, 이를 통해 보다 효율적이고 최적의 해결책을 찾을 수 있습니다.