DP

다이내믹 프로그래밍(Dynamic Programming, DP)

다이내믹 프로그래밍(DP)은 문제를 더 작은 하위 문제로 분할하고 각 하위 문제의 해결책을 저장하여 중복 계산을 방지하는 알고리즘 설계 패러다임이다.

DP의 핵심 개념

• 최적 부분 구조 : 큰 문제를 작은 하위 문제로 분할할 수 있는 성질
• 중복 부분 문제 : 하위 문제를 반복해서 해결하지 않도록 메모이제이션 또는 테이블을 사용하여 해결책을 저장

DP의 동작 방식

1. 문제 정의
   • 문제를 작은 하위 문제로 분해하는 방법을 고민한다.
2. 중복 부분 구조 확인
   • 중복 계산이 발생하는지 확인한다. 중복 계산을 피해야 하므로 각 부분 문제를 한 번만 계산하게 한다.
3. 문제 해결
   • Top-Down DP에서는 재귀 호출을 사용하고, 중간 결과를 확인하여 중복 계산을 피한다.
   • Bottom-Up DP에서는 반복문을 사용하여 작은 문제부터 큰 문제로 해결한다.

Top-Down과 Bottom-Up DP

Top-Down(재귀적)

• 구현 방식
  • 이 방법은 재귀 함수를 사용하여 문제를 해결한다. 이때 중간 계산 결과를 저장하고 중복 계산을 피하기 위해 메모이제이션(캐싱)을 사용한다.
• 특징
  • 중복 계산을 피하기 위해 중간 계산 결과를 저장하고, 필요한 경우에만 다시 계산한다.
• 주로 재귀적 문제를 해결하는데 사용되며, 상위 문제를 하위 문제로 나누어 해결하는 경우에 유용하다. f(6)을 구하려면 f(5), f(4)를 알아야하며, f(4)를 구하기위해서는 f(3), f(2)를 알아야하듯이 위에서 아래로 내려가는 방식이다.

Bottom-Up(반복적)

• 구현 방식
  • 이 방법은 반복문을 사용하여 문제를 해결한다. 작은 하위 문제부터 시작하여 상위 문제를 해결해 나간다.
• 특징
  • 중복 계산이 없으며, 작은 문제부터 해결하여 큰 문제를 해결하는 방식이다.
• 상태가 하위 문제에 의해 완전히 결정될 때, 작은 하위 문제를 풀어 큰 문제를 해결해야 할 때 사용된다.

리스트가 주어질 때 연속된 인덱스를 가장 크게 만드는 방법을 예시로 보자.

index	0	1	2	3	4	5	6	7
value	-2	1	-3	4	-1	2	1	-5

위와 같은 리스트가 주어졌을 때 연속된 값을 구한다면 아래와 같이 될 것이다.

index	0	1	2	3	4	5	6	7
value	-2	1	-3	4	-1	2	1	-5
	-2	-1
		1	-2	2
				4	3	5	6	1

0번째와 1번째 인덱스를 더했을 경우와 첫번째 인덱스부터 다시 시작하는 경우 중 더 큰것은 후자이다. 이런 방식으로 계속해서 반복하다보면, 6번째 인덱스의 값 6이 가장 큰 것을 알 수 있다.

DP를 이용하지않은 피보나치 수열

def fibo(n):
    if n in [1, 2]:
        return 1
    return fibo(n-1) + fibo(n-2)

assert fibo(10) == 55
assert fibo(100) == 354224848179261915075 # 안끝난다.

피보나치의 반복횟수가 많아지면 엄청나게 오래걸리고 한번했던 계산을 재귀를 돌면서 계속해서 하게 된다. 하지만 DP를 이용한다면 어떻게 될까?

DP를 이용한 피보나치 수열

memo = {1: 1, 2: 1}


def fibo(n):
    if n in memo:
        return memo[n]
    memo[n] = fibo(n - 1) + fibo(n - 2)
    return memo[n]


assert fibo(10) == 55
assert fibo(100) == 354224848179261915075

memo라는 딕셔너리에 이미 값을 저장해두면서, 새로운 값만 추가한다. 이를 이용하여 이미 계산한 값은 꺼내 쓰기만 하면 된다. 위 방식은 Top-down 방식으로 푼 것이다.