1. 동적 계획법이란?
동적 계획법(Dynamic Programming)은 큰 문제를 작은 하위 문제들로 쪼개어 해결하는 알고리즘 기법입니다. 이 때, 작은 하위 문제들의 해결 결과를 저장해두고 재활용하는 메모이제이션(Memoization) 기법을 사용합니다. 동적 계획법은 중복되는 계산을 효율적으로 제거하여 실행 시간을 줄일 수 있습니다.
2. 메모이제이션과 탑다운 방식
동적 계획법의 주요 기법 중 하나인 메모이제이션(Memoization)은 계산한 값을 배열에 저장하여 중복 계산을 피하는 방식입니다. 탑다운(Top-Down) 방식은 재귀적으로 큰 문제를 작은 문제로 나누어 해결하면서 메모이제이션을 사용하는 방식입니다.
def fibonacci(n):
if n <= 1:
return n
if memo[n] != -1:
return memo[n]
memo[n] = fibonacci(n-1) + fibonacci(n-2)
return memo[n]
n = 10
memo = [-1] * (n+1)
print(fibonacci(n))
3. 바텀업 방식과 테이블 생성
바텀업(Bottom-Up) 방식은 작은 문제부터 큰 문제까지 순차적으로 해결해 나가는 방식입니다. 이 때, 테이블을 생성하여 작은 문제들의 해결 결과를 저장하고 활용합니다.
def fibonacci(n):
table = [0] * (n+1)
table[1] = 1
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
n = 10
print(fibonacci(n))
2. 메모이제이션과 탑다운 방식
메모이제이션(Memoization)은 동적 계획법에서 사용되는 기법으로, 계산한 값을 저장해두고 나중에 재사용하여 중복 계산을 피하는 방식입니다. 탑다운(Top-Down) 방식은 재귀적으로 큰 문제를 작은 문제로 나누어 해결하면서 메모이제이션을 사용하는 방식입니다.
메모이제이션 예시
def fibonacci(n, memo):
if n <= 1:
return n
if memo[n] != -1:
return memo[n]
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
n = 10
memo = [-1] * (n+1)
print(fibonacci(n, memo))
탑다운 방식 예시
def fibonacci(n):
if n <= 1:
return n
table = [0] * (n+1)
table[1] = 1
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
n = 10
print(fibonacci(n))
3. 바텀업 방식과 테이블 생성
바텀업(Bottom-Up) 방식은 동적 계획법에서 사용되는 방식 중 하나로, 작은 문제부터 순차적으로 해결해 나가는 방식입니다. 이 때, 작은 문제들의 해결 결과를 테이블에 저장하여 활용합니다.
테이블 생성 예시
def fibonacci(n):
table = [0] * (n+1)
table[1] = 1
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
n = 10
print(fibonacci(n))
출력: 55
바텀업 방식은 메모이제이션과 달리 재귀함수를 사용하지 않고 반복문을 통해 작은 문제부터 큰 문제를 해결하면서 테이블에 값을 저장합니다. 이렇게 저장된 테이블은 중복 계산을 피하고 효율적인 계산을 가능하게 합니다.
4. 기초 동적 계획법 문제
4.1 피보나치 수열
피보나치 수열은 이전 두 항을 더하여 현재 항을 만드는 규칙으로 이루어져 있는 수열입니다. 동적 계획법을 활용하여 효율적으로 피보나치 수열을 구할 수 있습니다.
def fibonacci(n):
if n <= 1:
return n
table = [0] * (n+1)
table[1] = 1
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
n = 10
print(fibonacci(n))
출력: 55
4.2 이항 계수
이항 계수는 조합론에서 사용되는 개념으로, 주어진 크기의 집합에서 특정 개수의 원소를 선택하는 경우의 수를 나타냅니다. 이항 계수는 동적 계획법을 활용하여 효율적으로 계산할 수 있습니다.
def binomial_coefficient(n, k):
table = [[0] * (k+1) for _ in range(n+1)]
for i in range(n+1):
for j in range(min(i, k)+1):
if j == 0 or j == i:
table[i][j] = 1
else:
table[i][j] = table[i-1][j-1] + table[i-1][j]
return table[n][k]
n = 5
k = 2
print(binomial_coefficient(n, k))
출력: 10
5. 최장 증가 부분 수열
최장 증가 부분 수열(Longest Increasing Subsequence)은 주어진 수열에서 원소들을 선택하여 만들 수 있는 가장 긴 증가하는 부분 수열을 말합니다. 동적 계획법을 사용하여 최장 증가 부분 수열을 효율적으로 구할 수 있습니다.
코드 예시
def longest_increasing_subsequence(nums):
n = len(nums)
table = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
table[i] = max(table[i], table[j] + 1)
return max(table)
nums = [10, 22, 9, 33, 21, 50, 41, 60]
print(longest_increasing_subsequence(nums))
출력: 5
위의 예시에서 입력 수열 [10, 22, 9, 33, 21, 50, 41, 60]에서 최장 증가 부분 수열은 [10, 22, 33, 50, 60]으로 5개의 원소를 가지고 있습니다.
6. 배낭 문제
배낭 문제(Knapsack Problem)는 제한된 용량을 가진 배낭에 가치가 있는 물건들을 넣어 물건들의 가치의 합을 최대화하는 문제입니다. 동적 계획법을 사용하여 배낭 문제를 효율적으로 해결할 수 있습니다.
코드 예시
def knapsack(weights, values, capacity):
n = len(weights)
table = [[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:
table[i][j] = max(values[i-1] + table[i-1][j-weights[i-1]], table[i-1][j])
else:
table[i][j] = table[i-1][j]
return table[n][capacity]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(weights, values, capacity))
출력: 9
위의 예시에서 입력으로 주어진 물건들의 무게(weights)와 가치(values) 배열, 그리고 배낭의 용량(capacity)은 각각 [1, 3, 4, 5], [1, 4, 5, 7], 7 입니다. 배낭에 넣을 수 있는 물건들의 조합으로 가장 최대의 가치를 가지는 경우는 [3, 4] 물건을 넣어서 가치 9를 얻는 경우입니다.
7. 최대 연속 부분 배열 합 문제
최대 연속 부분 배열 합(Maximum Subarray Sum) 문제는 주어진 배열에서 연속된 부분 배열의 합 중 가장 큰 값을 찾는 문제입니다. 이 문제는 분할 정복 알고리즘을 사용하여 효율적으로 해결할 수 있습니다.
코드 예시
def max_subarray_sum(arr):
def max_crossing_sum(arr, low, mid, high):
left_sum = float('-inf')
current_sum = 0
for i in range(mid, low-1, -1):
current_sum += arr[i]
if current_sum > left_sum:
left_sum = current_sum
right_sum = float('-inf')
current_sum = 0
for i in range(mid+1, high+1):
current_sum += arr[i]
if current_sum > right_sum:
right_sum = current_sum
return left_sum + right_sum
def max_subarray_sum_recursive(arr, low, high):
if low == high:
return arr[low]
mid = (low + high) // 2
left_sum = max_subarray_sum_recursive(arr, low, mid)
right_sum = max_subarray_sum_recursive(arr, mid+1, high)
crossing_sum = max_crossing_sum(arr, low, mid, high)
return max(left_sum, right_sum, crossing_sum)
return max_subarray_sum_recursive(arr, 0, len(arr)-1)
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr))
출력: 6
위의 예시에서 입력으로 주어진 배열은 [-2, 1, -3, 4, -1, 2, 1, -5, 4]입니다. 이 배열에서 최대 연속 부분 배열의 합은 [4, -1, 2, 1]로 총 합이 6입니다.
8. 행렬 제곱 문제
행렬 제곱(Matrix Power) 문제는 주어진 행렬을 자연수 n번 곱하는 문제입니다. 행렬의 곱셈은 시간 복잡도가 높기 때문에 분할 정복 알고리즘을 사용하여 효율적으로 행렬을 제곱할 수 있습니다.
코드 예시
def matrix_multiply(a, b):
n = len(a)
c = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
c[i][j] += a[i][k] * b[k][j]
return c
def matrix_power(matrix, n):
def matrix_power_recursive(matrix, n):
if n == 1:
return matrix
if n % 2 == 0:
half = matrix_power_recursive(matrix, n // 2)
return matrix_multiply(half, half)
else:
half = matrix_power_recursive(matrix, (n-1) // 2)
return matrix_multiply(matrix_multiply(half, half), matrix)
return matrix_power_recursive(matrix, n)
matrix = [[1, 2], [3, 4]]
n = 3
result = matrix_power(matrix, n)
for row in result:
print(row)
출력:
[37, 54] [81, 118]
위의 예시에서 입력으로 주어진 행렬은 [[1, 2], [3, 4]]이고, 행렬을 3번 제곱한 결과는 [[37, 54], [81, 118]]입니다.
9. DP 최적화 기법
다이나믹 프로그래밍(Dynamic Programming)은 중복되는 부분 문제에 대한 연산을 피하기 위해 이전에 계산한 결과를 저장하고 재활용하는 기법입니다. 이러한 DP 기법을 최적화하기 위해 여러 방법들이 존재합니다. 여기서는 Knapsack 문제의 공간 최적화와 LCS(Longest Common Subsequence) 문제의 바텀업 및 공간 최적화에 대해 소개하겠습니다.
9.1 Knapsack 문제의 공간 최적화
Knapsack(배낭) 문제는 가방에 담을 수 있는 최대 가치의 물건들을 선택하는 문제입니다. DP를 이용하여 효율적으로 해결할 수 있는데, 이때 공간 최적화 기법을 사용하여 메모리 사용량을 줄일 수 있습니다.
코드 예시
def knapsack(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for j in range(capacity, weights[i] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(weights, values, capacity))
출력: 9
위의 예시에서 입력으로 주어진 weights는 [1, 3, 4, 5]이고, values는 [1, 4, 5, 7]입니다. 가방의 용량(capacity)은 7이며, 최대로 담을 수 있는 가치의 합은 9입니다.
9.2 LCS 문제의 바텀업 및 공간 최적화
LCS(Longest Common Subsequence) 문제는 주어진 두 문자열에서 가장 긴 공통 부분 수열을 찾는 문제입니다. 이 문제도 DP를 이용하여 해결할 수 있으며, 바텀업 및 공간 최적화 기법을 사용하여 효율적으로 구현할 수 있습니다.
코드 예시
def lcs(s1, s2):
m = len(s1)
n = len(s2)
dp = [[0] * (n + 1) for _ in range(2)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1
else:
dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[i % 2][j - 1])
return dp[m % 2][n]
s1 = "ABCD"
s2 = "ACDF"
print(lcs(s1, s2))
출력: 3
위의 예시에서 입력으로 주어진 문자열은 s1 = "ABCD"과 s2 = "ACDF"입니다. 이 두 문자열의 가장 긴 공통 부분 수열의 길이는 3입니다.
10. 실전 문제 및 응용 예제
실전 문제와 응용 예제를 통해 다이나믹 프로그래밍(Dynamic Programming)을 적용하는 방법을 살펴보겠습니다. 다음은 대표적인 실전 문제와 응용 예제입니다.
10.1 편집 거리(Edit Distance) 문제
편집 거리 문제는 주어진 두 문자열을 최소 편집 횟수로 변환하는 문제입니다. 편집 연산은 문자 삽입, 삭제, 교체로 이루어집니다.
코드 예시
def min_edit_distance(s1, s2):
m = len(s1)
n = len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
return dp[m][n]
s1 = "kitten"
s2 = "sitting"
print(min_edit_distance(s1, s2))
출력: 3
위의 예시에서 입력으로 주어진 문자열은 s1 = "kitten"과 s2 = "sitting"입니다. 두 문자열을 변환하기 위해 최소 3번의 편집 작업이 필요합니다.
10.2 도둑질(Thievery) 문제
도둑질 문제는 일렬로 놓인 집들에 대해 동시에 훔칠 수 있는 최대 금액을 구하는 문제입니다. 단, 인접한 두 집을 동시에 훔치는 것은 불가능합니다.
코드 예시
def max_stolen_value(houses):
n = len(houses)
if n == 0:
return 0
if n == 1:
return houses[0]
dp = [0] * n
dp[0] = houses[0]
dp[1] = max(houses[0], houses[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + houses[i])
return dp[n - 1]
houses = [1, 3, 1, 5, 2]
print(max_stolen_value(houses))
출력: 8
위의 예시에서 입력으로 주어진 집들은 [1, 3, 1, 5, 2]입니다. 동시에 훔치는 경우를 피해서 훔칠 수 있는 최대 금액은 8입니다.
10.3 최대 부분 증가 수열(Longest Increasing Subsequence) 문제
최대 부분 증가 수열 문제는 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제입니다.
코드 예시
def longest_increasing_subsequence(nums):
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
nums = [10, 22, 9, 33, 21, 50, 41, 60]
print(longest_increasing_subsequence(nums))
출력: 5
위의 예시에서 입력으로 주어진 수열은 [10, 22, 9, 33, 21, 50, 41, 60]입니다. 이 수열에서 가장 긴 증가하는 부분 수열의 길이는 5입니다.