[알고리즘] DP

❗다이나믹 프로그래밍(Dynamic Programming, 동적계획법)

• 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 중간 결과값을 저장하고 큰 문제를 해결할 때 저장한 값을 사용하여 문제를 해결하는 것이다.
• DP를 사용하기 위해선 2가지 조건을 만족해야 한다.

[1]. Overlapping Subproblems(겹치는 부분 문제)

• 동일한 작은 문제를 반복적으로 해결한다.

[2]. Optimal Substructure(최적 부분 구조)

• 큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 답을 모아서 다시 큰 문제를 해결한다.

❗메모이제이션(Memoization)

• 변수 값에 따른 결과를 어딘가에 저장을 해야 한다. 이것을 메모한다고 하여 메모이제이션(Memoization)이라고 한다.
• 결과 값을 저장할 때 배열을 활용하며 그 때마다 다르다.

❗탑다운(Top-Down)

• 탑다운 방식은 위에서 언급한 메모이제이션 방식으로 불리우며 위에서 아래 즉, 하향식이라고도 할 수 있다.
• dp[0]의 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서부터 바로 호출을 시작하는데 이 때 호출을 할 때 사용하는 것이 바로 재귀다.
• 아래 예시 문제와 코드를 보자.

현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 한다.
예를 들어, 4m의 네트워크 선이 주어진다면

1) 1m + 1m + 1m + 1m
2) 2m + 1m + 1m
3) 1m + 2m + 1m
4) 1m + 1m + 2m
5) 2m + 2m

의 5가지 방법을 생각할 수 있다. (2), (3), (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다. 그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법이 나올까?

import sys
input = sys.stdin.readline

N = int(input())
memoization = [0] * (N+1)

def func(x):
    if x == 1 or x == 2:
        return x
    # 이미 처리된 결과라면?
    if memoization[x] != 0:
        return memoization[x]
    memoization[x] = func(x-1) + func(x-2)
    return memoization[x]

print(func(N))

• 위와 같이 재귀를 활용하고 Cut-Edge를 통해 시간을 잡아먹는 불필요한 경우를 제외하면 탑다운 방식으로 구현한 DP 코드가 된다.

❗바텀업(Bottom-Up)

• 바텀업 방식은 작은 문제부터 규칙성을 파악하여 점화식을 세워 반복문을 통해 해결하는 방식을 말한다.
• 문제는 위와 동일하며 바텀업 방식으로 구현한 코드를 확인하자.

import sys
input = sys.stdin.readline

N = int(input())
dp = [0] * (N+1)
dp[1] = 1
dp[2] = 2
for i in range(3, N+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[N])

[레퍼런스]

이코테 2021 - Dynamic Programming
인프런 - 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)