[Algorithm] 다이나믹 프로그래밍

토닉·2021년 8월 12일

다이나믹 프로그래밍

알고리즘

목록 보기

3/4

다이나믹 프로그래밍

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
이미 계산된 결과는 별도의 메모리 영역에 저장
구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성
동적 계획법이라고도 부른다.

일반적인 프로그래밍 분야에서의 동적이란?

프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법

반면에 다이나믹 프로그래밍에서는 별다른 의미 없이 사용된 단어

구현 조건

1. 최적 부분 구조(Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 잇으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 때
2. 중복되는 부분 문제(Overlapping Subproblem)
동일한 작은 문제를 반복적으로 해결해야 할 때

대표적인 문제

피보나치 수열

1,1,2,3,5,8,13,21,34,55,89,...
n번째 수는 n-1, n-2번째 수의 합을 나열한 수열
1+1= 2 , 1+2= 3, 2+3=5

피보나치 수열 문제는 다이나믹 프로그래밍의 사용 이유를 알려주는 대표적인 문제 중 하나입니다.
다이나믹 프로그래밍을 언제 사용하는지 알기 위해서는 위의 구현 조건에 적합한 문제인지 판별해야 합니다.

1. 최적 부분 구조
예를 들어 피보나치 수열의 5번째 수를 알고 싶다면
1+1 = 2(3번째) , 1+2= 3(4번째), 2+3= 5(5번째) 로 정답은 5
5번째의 식을 다시 본다면 2(3번째) + 3(4번째) 라는 것을 알 수 있습니다.
이를 봤을 때 5번째라는 큰 문제를 3번째와 4번째의 두 문제로 나누어서 풀고 합하여도 해결할 수 있기 때문에 최적 부분 구조에 적합하다고 할 수 있습니다.

2. 중복되는 부분 문제
위 처럼 3번째 4번째를 나누어서 풀 때 중복되는 부분이 있는지 확인해 보아야 합니다.
1+2=3(4번째) 풀이에서 2는 사실 3번째 풀이에서 나오는 결과 값입니다.
3번째 풀이를 할 때 만약 이 값을 어떤 메모리에 저장을 하게 된다면 4번째 풀이를 할 때에는 3번째 풀이를 할 필요가 없어질 것입니다. 이 방법이 바로 밑에 설명 된 메모이제이션 이라고 부릅니다.

점화식: 인접한 항들 사이의 관계식

# 재귀 함수로 구현
def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

위처럼 단순 재귀 함수로 해결하면 지수 시간 복잡도를 가지게 됩니다.(O(2^n))
다음과 같이 f(2)가 여러 번 호출되는 것을 확인할 수 있습니다.(중복되는 부분 문제)
f(30)을 계산하기 위해 약 10억 가량의 연산을 수행해야 합니다.

구현 조건을 만족하는지 확인
1. 최적 부분 구조
2. 중복되는 부분 문제

메모이제이션(Memoization)

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

같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옵니다.
값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 합니다.
탑다운과 보텀업 방식이 있습니다.

탑다운

하향식이라고도 불립니다.

보텀업

상향식이라고도 불립니다.
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식입니다.

결과 저장용 리스트(배열)는 DP 테이블이라고 부릅니다.

메모이제이션을 사용한 피보나치 수열 풀이(탑 다운)

d = [0] * 100

def fibo(n):
    if n == 1 or n == 2:
        return 1
    if d[n] != 0:
        return d[n]
    d[n] = fibo(n - 1) + fibo(n - 2)
    return d[n]

보텀업을 사용한 피보나치 수열 풀이

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

작은 문제들을 먼저 해결해논 다음에 큰 문제들을 해결하는 과정

동작 분석

다이나믹 프로그래밍 vs 분할 정복

둘 다 최적 부분 구조를 가질 때 사용할 수 있습니다.

최적 부분 구조
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황

차이점은 부분 문제의 중복!

다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됩니다.
분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않습니다.

다이나믹 프로그래밍 문제에 접근하는 방법

주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요!
가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토
일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법
코테에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다.