DP란?
DP(Dynamic Programming)는 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다.
대표적인 예시로 피보나치 수열이 있다.
피보나치 수열을 구할 때 흔히 재귀함수를 사용하는데, return f(n) = f(n-1) + f(n-2)로 나타난다. 하지만 이 과정에서 동일한 값을 여러 번 구하게 되면 연산수가 기하급수적으로 증가한다.
재귀함수를 사용하면 이미 구한 값도 다시 구하게 되면서 연산 수가 늘어난다. 이 문제점을 해결하기 위해 DP를 사용한다.
한 번 구한 값은 저장해놨다가 필요할 때 꺼내 쓰자!
이때 한 번 구한 값을 저장하는 것을 메모이제이션(Memoization)이라고 한다.
DP를 적용하기 위해서는 다음의 두 가지 조건을 만족해야 한다.
-
최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 부분 문제의 최적해로부터 구해질 수 있어야 한다.
-
중복되는 부분 문제(Overlapping Subproblems): 부분 문제가 중복되어 여러 번 반복 계산되어야 한다.
문제1
백준 1463번 '1로 만들기' 문제를 풀어보았다.
https://www.acmicpc.net/problem/1463
import sys
input = sys.stdin.readline
def min_operations(N):
# dp[i]는 i를 1로 만들기 위한 최소 연산 횟수
dp = [float('inf')] * (N + 1)
dp[1] = 0 # 1에서 1로 가는 데는 연산이 필요 없으므로 0
for i in range(2, N + 1):
# 1을 빼는 경우
dp[i] = dp[i - 1] + 1
# 2로 나누어 떨어지는 경우
if i % 2 == 0:
dp[i] = min(dp[i], dp[i // 2] + 1)
# 3으로 나누어 떨어지는 경우
if i % 3 == 0:
dp[i] = min(dp[i], dp[i // 3] + 1)
return dp[N]
N = int(input())
print(min_operations(N))
문제2
백준 11053번 '가장 긴 증가하는 부분 수열' 문제를 풀어보았다.
https://www.acmicpc.net/problem/11053
import sys
input = sys.stdin.readline
def solution(N, lst):
N = len(lst)
# dp: 각 요소까지 가는 데 가장 긴 증가하는 길이
dp = [1] * N # 최소 길이는 1
long = 1 # 현재까지 제일 긴 증가하는 길이
now_max = lst[0]
for i in range(1, N):
for j in range(i):
if lst[i] > lst[j]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
N = int(input())
lst = list(map(int, input().split()))
print(solution(N, lst))글로벌소프트웨어캠퍼스와 교보DTS가 함께 진행하는 챌린지입니다.
