다이나믹 프로그래밍

 

다이나믹 프로그래밍 (Dynamic Programming)

어떤 문제를 공간을 더 사용하며 연산속도를 증가시키는 방법이다. 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 것이다.

 

다이나믹 프로그래밍의 조건

1. 최적 부분 구조 

    • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

 

2. 중복되는 부분 문제

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

 

* 뒤로 돌릴 수 없을 때, 특정한 상태가 있을 때, 최적해를 구해야할 때

 

 

대표적 예시 : 피보나치 수열

 a_n= a_n-1 + a_n-2, a₁ = 1, a₂ = 1

 

피보나치 수열을 재귀함수로 구현하면 다음과 같다.

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)
    
print(fibo(4))

 

💥 문제 발생

- f(n)의 함수에 n이 커질수록 수행 시간이 늘어난다.

- 예를들어, f(6)일 경우, f(3)이 3번 호출되고, f(2)는 5번 호출되며, f(1) 또한 3번 호출된다. 

- 즉, 이미 계산한 값을 반복하여 호출하기 때문에 매우 비효율적이다.

- 시간복잡도 : O(2^N)

 

❓ 문제를 해결하는 아이디어

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

✅ 문제의 해결

• 탑 다운(Top-Down) 방식 - 하향식

  : 재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방법

 

- 메모이제이션(캐싱) 기법

    : 한번 구한 결과를 메모리 공간에 저장해두고 같은 식을 다시 호출하면 결과를 그대로 가져오는 기법

# 메모이제이션을 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현 (탑다운 dp)
def fibo(x):
    # 종료 조건
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    # 아직 계산되지 않은 문제라면 점화식에 따라 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(fibo(6))

 

- 호출되는 순서 f(6) f(5) f(4) f(3) f(2) f(1) f(3) f(4)

- 시간 복잡도 : O(N)

 

• 보텀 업(Bottom-Up) 방식 - 상향식  *권장*

  : 반복문을 이용하여 작은 문제를 해결하고, 해결된 작은 문제를 모아 차근차근 큰 문제의 답을 도출하는 방법

d = [0] * 100

# 첫 번째, 두 번째 피보나치 수 초기화
d[1] = 1
d[2] = 1
n = 6

# 피보나치 함수를 반복문으로 구현(보텀업 dp)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

 

 

* 이것이 코딩테스트다 with 파이썬 - 나동빈