다이나믹 프로그래밍
- 전체 문제를 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘
- 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성되는 문제, 즉 최적 부분 구조를 가지는 문제에 대해 적용 가능하다.
DP 가정
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다.
DP, 그리디, 분할정복
- 참고로 그리디는 항상 그 순간에 최적이라고 생각되는 것을 선택하면서 풀이해 나가는 것이고, 다이나믹 프로그래밍은 중복된 하위 문제들의 결과를 저장해뒀다가 풀어나간다는 차이점이 있다.
- 또한 분할 정복으로 분류되는 병합 정렬과 퀵 정렬은 중복된 하위 문제들을 푸는 것이 아니기 때문에 다이나믹 프로그래밍으로 분류하지 않는다.
알고리즘 | 풀이 가능한 문제들의 특징 | 풀이 가능한 문제 및 알고리즘 |
다이나믹 프로그래밍 | 최적 부분 구조, 중복된 하위 문제들 | 배낭 문제, 피보나치 수열, 다익스트라 |
그리디 | 최적 부분 구조, 탐욕 선택 속성 | 분할 가능 배낭 문제, 다익스트라 |
분할 정복 | 최적 부분 구조 | 병합 정렬, 퀵 정렬 |
최적 부분 구조
- 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우 최적 부분 구조라고 한다.
- 이런 유형의 문제는 분할 정복으로 풀 수 잇으며, DP 또는 그리디 알고리즘으로 접근해볼 수 있는 문제의 후보가 된다.
중복된 하위 문제들
- DP로 풀 수 있는 문제들과 다른 문제들의 차이는 중복된 하위 문제들을 갖는다는 점이다.
- 예를 들어 피보나치 수열을 재귀로 풀면 반복적으로 동일한 하위 문제들이 발생한다.
DP 방법론
상향식 방법 (Bottom Up)
- 더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나간다.
- 데이터를 테이블 형태로 만들어 반복문을 통해 문제를 플어나가며, 일반적으로 이 방식만을 다이나믹 프로그래밍으로 지칭하기도 한다.
def fibo(n):
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
하향식 방법 (Top Down)
- 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어나간다.
- 기존 재귀 풀이와 거의 동일하면서도 이미 풀어봤는지 확인하여 재활용하는 효율적인 방식으로, 이 방식을 특별히 메모이제이션이라고 따로 지칭하기도 한다.
def fibo(n):
if n <= 1:
return n
if dp[n]:
return dp[n]
dp[n] = fibo(n - 1) + fibo(n - 2)
return dp[n]
DP 활용 알고리즘
LIS (최장 증가 부분 수열)
- 특정 수열의 부분 수열 중에서 오름차순으로 정렬된 가장 긴 부분 수열로, 구성 원소가 연속적일 필요는 없다.
- 시간 복잡도는 O(n^2)
- 구성 원소를 출력하려면, 각 부분 문제마다 최적의 선택지를 기록하고 재귀 함수를 이용해서 각 부분에서 내린 선택을 되짚어가며 실제 답을 출력한다.
문제
https://www.acmicpc.net/problem/14002
n = int(input())
a = list(map(int, input().split()))
# d[i] : a[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
# d[i] = max(d[j] + 1), 0 <= j <= i - 1, a[j] < a[i]
d = [1] * n
# v[i] : a[i]의 앞에 와야 하는 수의 인덱스
v = [-1] * n
for i in range(1, n):
for j in range(i):
if a[i] > a[j] and d[i] < d[j] + 1:
d[i] = d[j] + 1
v[i] = j
ans = []
last_index = d.index(max(d))
while last_index > -1:
ans.append(a[last_index])
last_index = v[last_index]
ans.reverse()
print(max(d))
print(" ".join(map(str, ans)))
배낭 문제
- 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 집들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.
- 배낭 문제는 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우, 두 가지로 나눌 수 있으며, 짐을 쪼갤 수 있는 경우를 분할가능 배낭 문제, 짐을 쪼갤 수 없는 경우를 0-1 배낭 문제라고 한다.
- 분할가능 배낭 문제는 그리디로, 0-1 배낭 문제는 다이나믹 프로그래밍으로 해결할 수 있다.
0-1 배낭 문제
https://www.acmicpc.net/problem/12865
n, k = map(int, input().split())
w = [0]
v = [0]
for _ in range(n):
a, b = map(int, input().split())
w.append(a)
v.append(b)
# d[i][j]: i번째 물건까지 고려했을 때, 배낭에 넣은 무게의 합이 j일 때의 가치의 최대값
# i번째 물건을 넣지 않은 경우 = d[i - 1][j]
# i번째 물건을 넣은 경우 = d[i - 1][j - w[i]] + v[i]
d = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, k + 1):
# 무게 j를 만들때 i번째 물건을 썼냐 안썻냐 비교
d[i][j] = d[i - 1][j]
# 대신 물건을 뺏을 때 가방의 무게가 음수가 되는지 확인, 즉 물건의 무게가 가방의 제한을 넘어가는 경우
if j - w[i] >= 0:
d[i][j] = max(d[i][j], d[i - 1][j - w[i]] + v[i])
print(d[n][k])
분할가능 배낭 문제
def fractional_knapsack(capacity, cargo):
pack = []
# 단가 계산 역순 정렬
for c in cargo:
pack.append((c[0] / c[1], c[0], c[1]))
pack.sort(reverse=True)
# 단가 순 그리디 계산
ans = 0
for p in pack:
if capacity - p[2] >= 0:
capacity -= p[2]
ans += p[1]
else:
fraction = capacity / p[2]
ans += p[1] * fraction
break
return ans
LCS (최장 공통 부분 수열)
- 주어진 수열들의 가장 긴 공통의 부분 수열의 길이를 구하는 알고리즘
- 생명공학의 염기서열의 유사성 분석과 컴퓨터 공학에서 파일을 비교해주는 diff 유틸리티의 기반 메커니즘으로 사용된다
문제
https://www.acmicpc.net/problem/9251
a = input()
b = input()
n = len(a)
m = len(b)
a = " " + a
b = " " + b
# d[i][j]: a가 i까지 b가 j까지 있을 때 LCS의 길이
# a[i] == b[j] -> d[i][j] = d[i - 1][j - 1] + 1
# a[i] != b[j] -> d[i][j] = max(d[i][j - 1], d[i - 1][j])
d = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i] == b[j]:
d[i][j] = d[i - 1][j - 1] + 1
else:
d[i][j] = max(d[i][j - 1], d[i - 1][j])
print(d[n][m])
'Python > Algorithm' 카테고리의 다른 글
빅오 표기법 (Big-O) (0) | 2022.06.08 |
---|---|
투 포인터와 슬라이딩 윈도우 (0) | 2022.03.04 |
그래프 관련 알고리즘 (0) | 2022.03.01 |
버블 정렬, 선택 정렬, 삽입 정렬 (0) | 2022.03.01 |
트라이 (0) | 2022.02.27 |