[Algorithm] Dynamic Programming(동적 계획법) 정리 + 추천 문제 list
0. 들어가며
이번 주에는 Dynamic Programming(동적 계획법)알고리즘을 공부했습니다.
이번주에는 Back Tracking 알고리즘을 공부했습니다.
저는 알고리즘을 공부하며 크게 2가지의 알고리즘이 있다고 생각하는데요. 바로 찐 알고리즘과 그외 입니다.
- 찐 알고리즘은 바로 누군가가
"특정 상황에 적용 가능한 일련의 규칙이나 여러 행위 그리고 더 나아가 공식화한 형태로 표현한 것"
이라고 생각합니다.
예를 들면 다익스트라, 크루스칼, A* 알고리즘 등이 있습니다.
언급된 알고리즘들은 "특정 상황(ex: 최단경로)"에서 "일련의 규칙이나 여러 행위(ex: 현재 갈 수 있는 최단 경로에서 방문 가능한 노드를 방문하며 각 노드의 최단 경로 갱신을 반복)"하면 원하는 결과를 얻을 수 있습니다.
그러면 DP(Dynamic Programming)은 위의 개념 중 어떤 것에 해당되냐면 그외 입니다.
즉, 방법론 정도로 암기보다는 맥락을 이해하는게 중요하다고 생각합니다.
많은 분들이 이 DP 알고리즘을 어려워하는데 제가 생각하는 이유는 DP가 적용되는 범위가 굉장히 많고 어렵다고 생각합니다.
제가 DP알고리즘라고 판단 되었을 때 가장 중요하게 생각하는 방법은 DP Table 명확하게 정의하는 것입니다.
아래에 예제 문제들에서 자세히 설명할 예정이니 끝까지 읽어주시면 감사할 듯 합니다.
1. 다이나믹 프로그래밍이란.
DP 알고리즘은 큰 문제를 풀기 위해 작은 문제들의 정답이 필요해서, 작은 문제들의 정답을 저장하며 최적화 하는 방법입니다.
이때 작은 문제들의 정답을 저장해 최적화하는 기법을 메모이제이션(memoization)이라고 합니다.
이렇게만 보면 크게 어려운 게 없습니다. 배열이나 다양한 자료구조를 이용해 작은 문제들의 정답을 단순히 저장을 하면 최적화가 되는 알고리즘이기 때문에 글만 읽어서는 어려울 게 없습니다. 하지만 여기서 어려운 점은 바로
- "작은 문제의 정답을 어떻게 정의하는 가?"
- "작은 문제의 정답을 어떻게 저장하는가?"
- "작은 문제들의 정답을 큰 문제의 정답을 풀기위해 어떻게 사용해야하는가?"
입니다.
혹시 어디서 본 적이 있으신가요? 아마 분할정복(Divide and Conquer)알고리즘을 공부하셨다면 보셨을 텐데, 분할정복은 작은 문제를 큰 문제를 풀기위해 "쪼개는 게" 중요한 맥락이라면, DP는 이를 저장하기 위한 메모이제이션 기법이 적용되는게 조금 더 중요한 맥락인 알고리즘입니다.
DP를 설명하기 위해 가장 일반적으로 사용하는 예시인 피보나치를 보겠습니다.
$$F(n) := \begin{cases} 0 & \text{if } n = 0;\\ 1 & \text{if } n = 1;\\ F(n-1) + F(n-1) & \text{if } n > 1;\\ \end{cases}$$
피노차치 수열은 위와 같은 점화식을 가지고 있습니다. 아마 재귀로 한 번쯤은 짜 보셨을 거 같은데, 이를 이제 DP알고리즘을 적용해 작성해보겠습니다. 먼저 재귀로 짜면 아래와 같습니다.
예시 문제 : BOJ 10870 피보나치 수 5 (Python)
import sys
N = int(sys.stdin.readline())
def fib(i):
if i == 0 or i == 1:
return i
else:
return fib(i-2) + fib(i-1)
print(fib(N))재귀 함수에서 fib(i-1) + fib(i-2)를 호출하게 되지만 이 과정이 어딘가에 저장되지는 않고 휘발되어 버립니다. 그렇기 때문에 예를 들어 Fib(10)을 호출하게 되면 Fib(9) + Fib(8)이 호출되는데 Fib(9)에서 앞에서 호출을 원하는 Fib(8)을 또 호출하게 되고, 비효율적이게 됩니다. 그래서 추가적인 메모리를 사용해 이를 사전에 저장을 하면 호출되는 것을 막을 수 있습니다.
import sys
N = int(sys.stdin.readline())
arr = [-1] * (N+2)
arr[1] = 1
arr[0] = 0
def fib(i):
if arr[i] != -1 :
return arr[i]
else:
arr[i] = fib(i-1) + fib(i-2)
return arr[i]
print(fib(N))
0. 들어가기에서 DP Table을 잘 설정하면 좋다는 얘기를 했었습니다. 그럼 DP Table이 무엇일까요?
바로 작은 문제들을 저장하는 Table(자료구조(배열))입니다. 이를 명확히 정의해야 문제를 풀면서 정의가 잘못된 것도 느낄 수 있고, 디버깅도 쉬워지는 다양한 장점이 있습니다.
피보나치에서 만든 DP Table인 arr의 정의는 어떻게 될까요?
사람마다 다르게 정의할 수 있지만, 저는 $arr[i] = k$일 때 Fib(i) = k라고 정의했습니다.
위의 수식을 만족하기 위해 코드 중
arr[i] = fib(i -1) + fib(i - 2)를 추가해서 arr[i]에 fib(i)를 저장할 수 있도록 했습니다. 이런식으로 작은 정답을 저장하는 것을 메모이제이션(memoization)이라고 합니다.
이렇게 풀게된다면
단순히 재귀를 이용해 fib(5)를 계산하고자하면 전체 그래프를 계산해야 하지만 빨간 동그라미 두 부분도 동일하고 f(0), f(1), f(2), f(3) 같은 경우 여러번 계산되는 것들이 절약되어 기존의 $O(1.61...^N)$이였던 시간복잡도가 $O(N)$으로 수렴하게 됩니다.
2. DP 문제 파악 방법.
DP알고리즘은 주어진 큰 문제를 작은 문제들로 나누어서 해결한 뒤, 그 결과들을 저장하고 조합해 큰 문제를 해결하는 알고리즘입니다.
그리고 일반적으로 모든 경우의 수를 고려해서 작은 문제들을 모두 해결해보기 때문에 그리디나 일부 알고리즘에 비해 느리다는 단점이 있습니다만 최종적으로는 근사치가 아닌 정확한 값을 얻을 수 있기 때문에 이러한 정답을 원한다면 DP 알고리즘을 사용할 수 있습니다.
DP 알고리즘은 크게 2가지 방식으로 구현될 수 있습니다. 바로 Top-Down과 Bottom-up입니다.
어떤 문제를 먼저 호출하는가? 큰 문제인가 작은문제인가?로 구분할 수 있습니다.
Top-Down
Top-Down 방식으로 구현하는 것은 큰 문제를 먼저 호출하는 방식입니다.
예제를 먼저 살펴보겠습니다.
BOJ 1463 1로 만들기 입니다.
import sys
import math
sys.setrecursionlimit(10**7)
get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())
N = get_input()
dp = [-1] * (N + 1)
dp[0] = 0
def f(n):
if n == 1: return dp[0]
if dp[n] != -1: return dp[n]
if n % 3 == 0 : dp[n] = min(dp[n], f(n//3) + 1)
if n % 2 == 0 : dp[n] = min(dp[n], f(n//2) + 1)
dp[n] = min(dp[n], f(n-1) + 1)
return dp[n]
print(f(N))위 코드는 메모리 초과가 납니다. 왜냐하면
dp[n] = min(dp[n], f(n-1) + 1)위 코드에서 계속해서 값을 요청하게 되기 때문입니다. 다르게 구현하는게 가능하나 지금은 넘어가겠습니다.
중요한 것은 호출할 때 가장 먼저 요청하게 되는 값이 dp(N) -> arr[N]이라는 것입니다.
C언어로는 통과 가능합니다.
Bottom-Up
import sys
get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline())
N = get_input()
arr = [0] * (N + 1)
for i in range(2, N + 1):
arr[i] = arr[i - 1] + 1
if i % 2 == 0:
arr[i] = min(arr[i // 2] + 1, arr[i])
if i % 3 == 0:
arr[i] = min(arr[i // 3] + 1, arr[i])
print(arr[N])다음 코드를 실행하게 되면 arr[2] 부터 계산해 저장하게 됩니다.
이 문제는 입력 받은 N번째 즉 arr[N]을 얻고 싶지만 작은 문제부터 먼저 맞닥들이게 되므로 Bottom-Up으로 구현했다고 할 수 있습니다.
여기서 주의해야 하는 점은 먼저 "해결"하는 문제가 아니라 얻고자 하는 문제의 크기가 Top-Down인지 Bottom-up인지 구분하게 되고, 일반적으로는 재귀로 구현한다면 Top-Down, 반복문으로 구현하게 된다면 Bottom-up이라고 생각해도 큰 무리는 없습니다.
이 외의 문제를 만나게 된다면 그 때는 여러분의 능력으로 구분이 가능하시리라 생각됩니다.
3. 추천 문제 list
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
DP Table을 기준으로 생각을 해보겠습니다.
가장 기본적으로 생각할 수 있는 것은 어떤 배열에 정보를 저장한다는 것입니다.
문제에서 알 수 있는 것은 x크기의 타일의 경우의 수는 고정된다는 것이고 이것은 함수 f를 이용해 mapping이 가능하므로 배열을 가정해 경우의 수를 저장할 수 있을 것으로 생각됩니다.
그래서 DP Table은
$arr[x] = K$의 뜻은 $x$의 길이를 가진 타일의 경우의 수는 $K$입니다 라는 뜻입니다.
그럼 이게 작은 문제들이 큰 문제를 푸는데 어떻게 도움이 되냐면?
$arr[x] => \dots N_200$, $...N_11$ 이렇게 표현이 가능합니다.
이때 $N_2$길이를 가진 $arr[N_2]$ , $N_1$ 길이를 가진 $arr[N_1]$ 두 개가 작은 문제가 됩니다.
그래서 $arr[x] = arr[x-2] + arr[x-1]$로 정리 가능합니다.
아래의 예시 코드는 Bottom-Up 구조로 잤습니다.
(※ 어디서 많이 봤죠? 피보나치와 구조가 동일합니다. 우리는 문제에서 이렇게 우리가 풀었던 문제를 뽑아낼 수 있으면 좋습니다.
근데 사실 이런건 풀고나면 알게되는 거지, 보통 풀기 전에 이거 피보나치구나! 하지는 않는 것 같습니다.)
import sys
MOD = 15746
get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline())
N = get_input()
arr = [0, 1, 2] + [0] * (N + 1)
for i in range(3, N + 1):
arr[i] = (arr[i - 1] + arr[i - 2]) % MOD
print(arr[N])
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
import sys
from copy import deepcopy
get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())
arr = None
N = None
dp = None
def set_variable():
global arr, N, dp
N = get_input()
arr = [list(get_line()) for i in range(N)]
dp = [[0] * 3 for i in range(N)]
def solution():
global arr, N, dp
dp[0] = deepcopy(arr[0])
for i in range(1, N):
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2]
print(min(dp[N-1]))
if __name__ == "__main__":
set_variable()
solution()
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
이 친구는 Bottom-Up 접근법이 직관적이라 Bottom-Up으로 설명하겠습니다.
특정 위치 x을 a번 이동하는게 최적이라면, $x * 3 = a + 1, x * 2 = a + 1, x + 1 = a + 1$ 이 $x * 3, x * 2, x + 1$에서의 위치에서 최적값으으로 고려될 수 있음을 직관적으로 알 수 있습니다. 물론 다른 방식으로 최소가 나올 수 있지만, 알 수 없으므로 min 함수를 통해 연산을 진행해보면 됩니다.
import sys
get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline())
N = get_input()
arr = [987654321] * (N + 1)
arr1 = [0] * (N + 1)
arr[1] = 0
for i in range(1, N):
arr[i + 1] = min(arr[i] + 1, arr[i + 1])
if i * 3 <= N:
arr[i * 3] = min(arr[i * 3], arr[i] + 1)
if i * 2 <= N:
arr[i * 2] = min(arr[i * 2], arr[i] + 1)
print(arr[N])
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
import sys
get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())
N = None
arr = None
up_cnt = None
down_cnt = None
def set_variable():
global N, arr, up_cnt, down_cnt
N = get_input()
arr = list(get_line())
up_cnt = [0] * N
down_cnt = [0] * N
def solution():
global N, arr, up_cnt, down_cnt
for i in range(N):
up_cnt[i] = 1
down_cnt[N-1-i] = 1
for j in range(i):
if arr[i] > arr[j]:
up_cnt[i] = max(up_cnt[i], up_cnt[j] + 1)
if arr[N - 1 - i] > arr[N - 1 - j]:
down_cnt[N - 1 - i] = max(down_cnt[N - 1 - i] , down_cnt[N - 1 - j] + 1)
answer = 0
for i in range(N):
answer = max(answer, up_cnt[i] + down_cnt[i])
print(answer - 1)
if __name__ == "__main__":
set_variable()
solution()
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는
www.acmicpc.net
import sys
get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())
arr = None
N = None
cnt = None
def set_variable():
global arr, N, cnt
N = get_input()
arr = []
cnt = [0] * N
for _ in range(N):
idx, n = get_line()
arr.append((idx, n))
arr.sort()
def solution():
global arr, N
for i in range(N):
cnt[i] = 1
for j in range(i):
if arr[i][1] > arr[j][1]:
cnt[i] = max(cnt[i], cnt[j] + 1)
print(N - max(cnt))
if __name__ == "__main__":
set_variable()
solution()
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
import sys
get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())
s1 = None
s2 = None
cnt_arr = None
def set_variable():
global s1, s2, cnt_arr
s1 = sys.stdin.readline().rstrip()
s2 = sys.stdin.readline().rstrip()
cnt_arr = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
def solution():
global s1, s2
for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
if s1[i-1] == s2[j-1]:
cnt_arr[i][j] = cnt_arr[i-1][j-1] + 1
else:
cnt_arr[i][j] = max(cnt_arr[i][j-1], cnt_arr[i-1][j])
print(cnt_arr[-1][-1])
if __name__ == "__main__":
set_variable()
solution()
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
import sys
get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())
N, K = None, None
bag = None,
max_value = None
def set_variable():
global N, K, bag, max_value
N, K = get_line()
bag = list()
max_value = [0 for _ in range(K+1)]
for _ in range(N):
w, v = get_line()
bag.append((w, v))
def solution():
global N,K, bag, max_value
for w, v in bag:
for j in range(K, 0, -1):
if w <= j:
max_value[j] = max(max_value[j], max_value[j - w] + v)
print(max(max_value))
if __name__ == "__main__":
set_variable()
solution()