다이나믹 프로그래밍 Dynamic Programming

 

다이나믹 프로그래밍이란?

 

메모리를 적절히 사용하여 수행 시간 호율성을 비약적으로 향상시키는 방법

이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

 

 

 

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

 

1. 최적 부분 구조 (Optimal Substructure)

: 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 구조

 

2. 중복되는 부분 문제 (Overlapping Subproblem)

: 동일한 작은 문제를 반복적으로 해결할 수 있는 문제

 

 

 

다이나믹 프로그래밍 구현 방식

 

TopDown(탑다운) & BottomUp(보텀업)

 

 

TopDown(탑다운, 하향식)

큰 문제를 해결하기 위해서 작은 문제들을 재귀적으로 호출하여 작은 문제가 모두 해결되었을 때 큰 문제의 답까지 얻을 수 있는 방식

 

메모이제이션 Memoization

한 번 계산한 결과를 메모리 공간에 메모하는 기법

같은 문제를 다시 호출하면 결과를 그대로 가져온다.

값을 기록해놓는다는 점에서 캐싱(Cashing)이라고도 부른다.

 

 

BottomUp(보텀업, 상향식)

아래에서부터 작은 문제를 하나씩 해결해나가면서 먼저 계산했던 값을 활용해서 다음 문제까지 차례대로 해결해나가는 방식

 

• 반복문 사용하여 구현
• 결과 저장용 리스트(배열)는 DP 테이블이라고 부른다.

 

 

 

다이나믹 프로그래밍의 대표 예시 문제

- 백준 2747번 피보나치 수

 

💻 코드

 

 

⬇ TopDown 방식

 

import sys

d = [0] * 50


def fivo(x):
    if x == 1 or x == 2:
        return 1

    if d[x] != 0:
        return d[x]

    d[x] = fivo(x - 1) + fivo(x - 2)
    return d[x]


n = int(sys.stdin.readline())

print(fivo(n))

 

 

 

 

 

⬇ BottomUp 방식

 

 

import sys

n = int(sys.stdin.readline())

d = [0] * 100

d[1] = 1
d[2] = 1

for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])