6-1. 메모이제이션 (Memoization)
흔히 메모리제이션으로 착각하지만 정식 명칭은 메모이제이션입니다. 기존의 정보를 memo를 한다는 의미로 상태를 저장하는 방식을 통칭합니다.
6-2. 동적계획법 (Dynamic Programming)
동적계획법(Dynamic Programming)은 알고리즘 설계 기법의 하나로서
동적계획법 풀이는 단순하게 말하면 점화식의 연속입니다. 그리고 이런 점화식을 진행하는 방식에 따라 풀이를 다음과 같이 나눌 수 있습니다.
- 탑다운(Top-Down) : 최종 상태를 구하기 위해 아래 상태를 재귀적으로 구하는 방법
- 바텀업(Bottom-Up) : 가장 작은 상태에서부터 쌓아나가는 방법
보통 Python의 재귀 속도 문제로 Python에서는 Bottom-Up 방식으로 코드를 짜는 것을 추천합니다.
그리고 점화식의 설계는 대표적인 문제들을 아는 것과 이를 통해 감을 익히는 게 중요합니다.
우선 대표적인 동적계획법 예시들로 감을 익혀봅시다.
쉬운 피보나치부터
# bottom-up
N = int(input())
DP = [0 for _ in range(N+1)]
DP[1] = 1
for i in range(2, N+1): DP[i] = DP[i-1] + DP[i-2]
print(DP[N])
# Top-Down
N = int(input())
DP = [0 for _ in range(N+1)]
def fib(n):
if n < 2: return n
if DP[n] != 0: return DP[n]
DP[n] = fib(n-1) + fib(n-2)
return DP[n]
print(fib(N))
2차원 누적합과 부분합
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)] # 0-index
DP = [[0 for i in range(M+1)] for j in range(N+1)] # 1-index
for i in range(1, N+1):
for j in range(1, M+1):
DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1]
K = int(input())
for _ in range(K):
i, j, x, y = map(int, input().split())
print(DP[x][y] - DP[i-1][y] - DP[x][j-1] + DP[i-1][j-1])
계단 오르기
N = int(input())
lst = [0]
for i in range(N): lst.append(int(input()))
DP = [[0 for _ in range(2)] for _ in range(N+1)]
DP[1][0] = lst[1]
for i in range(2, N+1):
DP[i][0] = max(DP[i-2][0], DP[i-2][1]) + lst[i]
DP[i][1] = DP[i-1][0] + lst[i]
print(max(DP[N]))
최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)
N, A = int(input()), list(map(int, input().split()))
DP = [1 for _ in range(N)]
for i in range(1, N):
for j in range(i):
if A[j] < A[i]:
DP[i] = max(DP[i], DP[j]+1)
print(max(DP))
2차원 경로 (N-dimension Path)
N = int(input())
# Dp[i][j] : i, j 도착했을 때 최댓값
# Dp[i][j] = max(Dp[i-1][j-1], Dp[i-1][j]) + A[i][j]
A = [[0 for _ in range(N+1)] for i in range(N+1)]
DP = [[0 for _ in range(N+1)] for i in range(N+1)]
for i in range(1, N+1):
tmp = list(map(int, input().split()))
for j in range(1, i+1):
A[i][j] = tmp[j-1]
for i in range(1, N+1):
for j in range(1, i+1):
DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + A[i][j]
print(max(DP[-1]))
최장 공통 부분열 (LCS, Longest Common Subsequence)
A, B = input(), input()
A_len, B_len = len(A), len(B)
DP = [[0 for _ in range(B_len+1)] for _ in range(A_len+1)]
for i in range(A_len):
for j in range(B_len):
DP[i+1][j+1] = max(DP[i+1][j], DP[i][j+1])
if A[i] == B[j]:
DP[i+1][j+1] = max(DP[i+1][j+1], DP[i][j]+1)
print(DP[A_len][B_len])