진행자

김민기

다이나믹 프로그래밍(DP) 정의

중복된 결과를 저장해, 동일한 부분이 발생했을 때 저장한 결과를 재활용해 실행 시간을 줄이는 알고리즘이다.

스크린샷 2024-05-03 231237.png

다이나믹 프로그래밍(DP)의 특징

장점

  1. 중복 계산을 줄일 수 있다.
  2. 효율적인 시간 복잡도를 가질 수 있다.

예시) 피보나치 수열

def fibo(n):
    if n <= 1:
        return n
    fib_numbers = [0, 1]
    for i in range(2, n + 1):
        fib_numbers.append(fib_numbers[i - 1] + fib_numbers[i - 2])
        # 리스트에 이미 저장되어 있던 i-1, i-2 값을 재활용해서
        # 반복적인 연산을 줄임.
    return fib_numbers[n]

Example)
print(fibo(3))

1. i가 2부터 4까지 반복
i = 2일 때,
fib_numbers = [0, 1, 1(0 + 1) -> 값 재활용]

i = 3일 때,
fib_numbers = [0, 1, 1, 2(1 + 1) -> 값 재활용]

2. return에서 값 출력
2출력

단점

  1. 메모리 사용량이 커서 문제의 크기가 커질수록 필요한 메모리가 증가한다.

ex) 앞서 제시한 피보나치 문제에서 n = 1 n = 2 에서의 결과값을 저장해야 하므로 추가적인 메모리가 소모된다.

다이나믹 프로그램의 방식 2가지