- 동적 계획법(Dynamic Programming)
동적 계획법은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.
문제를 작은 것부터 풀어본다는 것은 작은 문제들을 먼저 풀어서 그 해를 이용하여 문제를 해결하는 것이다.
작은 문제란 원래 주어진 문제와 같은 문제이며, 작은 문제를 부분 문제라고 한다. 작은 문제의 입력은 원래 문제의 입력의 일부분이다.
- 대표적인 DP문제
- 가장 긴 증가 순서
- 서열 정렬
- 합이 최대 K 되는 숫자
- 배낭문제
- 가장 긴 증가 순서
숫자가 일렬로 나열되었을 때 가장 긴 증가 순서(Longest Increasion Subsequence)를 찾는다.
증가 순서는 숫자들이 반드시 이웃해야만 하는 것은 아니다.
일렬로 주어진 숫자들로 만든 그래프에서 어떻게 가장 긴 경로를 찾아야 할까?
- 주어진 숫자들을 가지고 그래프를 만든다.
- 가장 왼쪽 정점으로부터 하나씩 차례로 각 정점으로 들어오는 간선의 왼쪽 끝 정점까지 계산된 경로의 길이들 중에서 가장 긴 것에 1을 더하여 경로의 길이를 계산
- 각 점의 경로 길이 중에서 가장 긴 것을 리턴한다.
def longest_increasing_subsequence(arr):
n = len(arr)
# dp[i]는 arr[i]를 마지막 원소로 가지는 가장 긴 증가 부분 수열의 길이
dp = [1] * n
# 모든 요소에 대해 증가 부분 수열을 탐색
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
# dp 배열에서 최댓값이 LIS의 길이
lis_length = max(dp)
# LIS를 구성하는 실제 수열을 복원
lis = []
current_length = lis_length
for i in range(n - 1, -1, -1):
if dp[i] == current_length:
lis.append(arr[i])
current_length -= 1
lis.reverse() # 역순으로 추가했으므로 뒤집기
return lis_length, lis
# 예제 배열
array = [10, 20, 10, 30, 20, 50]
length, sequence = longest_increasing_subsequence(array)
print("가장 긴 증가 부분 수열의 길이:", length)
print("가장 긴 증가 부분 수열:", sequence)알고리즘의 수행 시간: O(n²)
- 서열 정렬
서열 정렬(Sequence Alignment)은 어느 DNA가 다른 DNA로 변형되는데 얼마나 많은 변이가 필요한가를 계산하는 문제
변이는 삽입, 삭제, 대체의 연산 / ex. TTCAACA -> ATTGCGC로 만드는데 필요한 최소의 연산 횟수
편집 거리(Edit Distance) - S를 T로 변환시키는데 필요한 최소의 편집 연산 횟수
서열 정렬 알고리즘과 편집 거리 알고리즘은 동일하다.
편집 거리 알고리즘도 마찬가지로 삽입, 삭제, 대체(수정) 3개의 연산을 사용한다. 구현은 DP테이블을 이용해 구현한다.
위와 같이 DP테이블을 만든다. S에는 원래 문자, T에는 바꾸려는 문자를 둔다. S에 'script', T에 'scope'를 두게 되면
script는 6글자이므로 테이블의 세로는 0~6까지, scope는 5글자이므로 테이블의 가로는 0~5까지 이다.
표를 채워가는 순서에 맞춰 채워간다. 채워갈 때 현재 위치 기준 왼쪽, 왼쪽 대각선 위, 위쪽 숫자 중 가장 작은 숫자에서 +1을 하여 표를 채워간다. 이때 문자가 같으면 +1을 하지말고 왼쪽 대각선 위에 있는 숫자를 그대로 가져온다.
예를 들어 위에 'script' 를 'scope'로 바꿀 때 앞에 s가 같으므로 +1이 아닌 왼쪽 대각선 위의 숫자 0을 그대로 쓴다.
위처럼 테이블이 작성된다. 따라서 최소 편집 거리는 오른쪽 맨아래 숫자인 3이 된다.
def min_edit_distance(str1, str2):
m, n = len(str1), len(str2)
# DP 테이블 초기화
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
# DP 테이블 채우기
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]: # 문자가 같으면 편집 필요 없음
dp[i][j] = dp[i - 1][j - 1]
else: # 삽입, 삭제, 교체 중 최소값 선택
dp[i][j] = 1 + min(dp[i - 1][j], # 삭제
dp[i][j - 1], # 삽입
dp[i - 1][j - 1]) # 교체
return dp[m][n]
# 예제 문자열
string1 = "sunday"
string2 = "saturday"
result = min_edit_distance(string1, string2)
print(f"'{string1}'와 '{string2}'의 최소 편집 거리: {result}")
- 합이 최대 K 되는 숫자
n개의 숫자에 대해 합이 K가 되는 숫자들을 찾는 문제이다.
주어진 숫자들 중에서 합이 K가 되는 숫자들이 없으면 그 합이 K에 가장 가까운 숫자들을 찾는다.
ex. S = [3, 4, 5, 6], K = 13일 때, 합이 최대 K 되는 숫자 문제를 위한 동적 계획 알고리즘으로 해를 찾는다.
S = [0, 3, 4, 5, 6]
K = 13
n = len(S) - 1
T = [[0 for _ in range(K+1)] for _ in range(n+1)]
for i in range(1, n+1):
for j in range(K+1):
if S[i] > j:
T[i][j] = T[i - 1][j]
else:
T[i][j] = max(T[i - 1][j], S[i] + T[i - 1][j - S[i]])
print('T[', n, ',', K, '] =', T[n][K])알고리즘 수행시간 : O(nK)
- 배낭 문제
배낭 문제(Knapsack) - n개의 물건이 각각 무게와 가티를 가지고 배낭의 용량 K가 주어질 때 어떤 물건을 배낭에 담아야 최대의 가치를 얻을까?
[1] 물건을 차례로 하나씩 다음과 같은 결정을 내린다:
배낭의 용량을 1kg씩 증가시키며 물건을 배낭에 담는 것이 유리한지 담지 않는 것이 나은지 결정한다.
[2] return 마지막 물건에 대해 Kkg일 때 가치
https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C
배낭 문제 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 최적화의 유명한 문제이다. 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이
ko.wikipedia.org
W = [5, 4, 6, 3]
V = [10, 40, 30, 54]
K = 10
n = len(W)
T = [[0 for _ in range(K+1)] for _ in range(n+1)]
for i in range(n):
for j in range(K+1):
if W[i] > j:
T[i][j] = T[i-1][j]
else:
T[i][j] = max(T[i-1][j], V[i] + T[i-1][j - W[i]])
print('최대 가치:', T[n-1][K])알고리즘의 수행 시간 : O(nK)