[python] 동적 계획법으로 해결될 수 있는 문제 유형
동적 계획법(Dynamic Programming)은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 방법입니다. 이 방법은 중복되는 계산을 피하고 시간복잡도를 크게 줄일 수 있습니다. 동적 계획법은 다양한 문제 유형에서 사용될 수 있으며, 아래는 몇 가지 예시입니다.
1. 피보나치 수열
피보나치 수열은 이전 두 항을 더하여 다음 항을 구하는 수열입니다. 동적 계획법을 이용하여 피보나치 수열을 구하는 것은 중복 계산을 피할 수 있으므로 효율적입니다.
def fibonacci(n):
if n <= 1:
return n
else:
fib = [0] * (n+1)
fib[1] = 1
for i in range(2, n+1):
fib[i] = fib[i-1] + fib[i-2]
return fib[n]
2. 최장 증가 부분 수열
주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 문제입니다. 동적 계획법을 이용하여 이 문제를 해결할 수 있습니다.
def longest_increasing_subsequence(arr):
n = len(arr)
lis = [1] * n
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j] and lis[i] < lis[j] + 1:
lis[i] = lis[j] + 1
return max(lis)
3. 배낭 문제
주어진 무게와 가치를 가진 물건들을 가방에 넣을 때, 가치의 합이 최대가 되도록 물건을 선택하는 문제입니다. 동적 계획법을 이용하여 배낭 문제를 해결할 수 있습니다.
def knapsack(weights, values, capacity):
n = len(weights)
knap = [[0] * (capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, capacity+1):
if weights[i-1] <= j:
knap[i][j] = max(knap[i-1][j], values[i-1] + knap[i-1][j-weights[i-1]])
else:
knap[i][j] = knap[i-1][j]
return knap[n][capacity]
동적 계획법은 이 외에도 다양한 문제 유형에서 사용될 수 있습니다. 이를 잘 활용하여 효율적인 알고리즘을 작성할 수 있습니다.