Algorithm) Dynamic Programming

다이나믹 프로그래밍( 동적 계획법)

다이나믹 프로그래밍 : 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 

다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식 

• 탑 다운(하향식)
• 보텀 업(상향식)

 

일반적으로 프로그래밍 분야에서 동적(dynamic)이란?

• 자료구조에서 동적 할당(dynamic allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미
• 반면 다이나믹 프로그래밍에서 ‘다이나믹’은 별 의미 없이 사용된 단어

 

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

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

 

피보나치 수열

다이나믹 프로그래밍으로 효과적으로 계산할 수 있음

1, 1, 2, 3 , 5 , 8, 13, 21, 34 ,55, …

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

피보나치 수열을 점화식으로 표현하면 다음과 같음

피보나치 수열 점화식

 

단순 재귀로 피보나치 수열 해결 

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

 

단순 재귀의 시간 복잡도 분석 

- 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가짐
- f(n)이 여러 번 호출되는 것 확인(중복되는 부분 문제)

피보나치 수열의 효율적인 해법 : 다이나믹 프로그래밍 

다이나믹 프로그래밍의 사용 조건 만족하는지 확인

1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있다
   • f(4)를 구하기 위해 f(3), f(2)를 구하는 문제로 나눌 수 있음
2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결
   • f(n)이 여러 번 호출 되는 것 확인할 수 있음

→ 피보나치 수열은 다이나믹 프로그래밍의 사용 조건 만족

 

메모이제이션(memoization)

메모이제이션은 다이나믹 프로그래밍 구현 방법중 하나

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

같은 문제를 다시 호출하면 메모했던 결과 그대로 가져옴

값을 기록해 놓는다는 점에서 캐싱(cashing)이라고도 함

 

탑다운 vs 보텀업

탑다운(메모이제이션) 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 함

다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식

결과 저장용 리스트는 DP 테이블이라고 부름

엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념

• 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아님
• 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수 있음

 

탑다운 다이나믹 프로그래밍 

메모이제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는 $O(N)$

# 한 번 계산된 결과를 memoization하기 위한 리스트 초기화
d = [0]* 100

# 피보나치 함수를 재귀함수로 구현(탑다운)
def fibo(x):
    print('f(' + str(x) + ')', end=' ')
    # 종료 조건
    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(2) f(3) f(4) 8

 

보텀업 다이나믹 프로그래밍

작은 문제를 미리 구하고 작은 문제를 토대로 앞으로의 큰 문제를 해결함

d = [0]*100
d[1]=1
d[2]=1
n = 99
for i in range(3, n+1):
    d[i]=d[i-1]+d[i-2]
print(d[n]) # 218922995834555169026

 

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

공통점 :

최적 부분 구조를 가질 때 사용할 수 있음

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

차이점 : 부분 문제의 중복

다이나믹 프로그래밍 : 각 부분 문제들이 서로 영향을 미치며 부분 문제 중복

분할 정복 : 동일한 부분 문제가 반복적으로 계산되지 않음

 

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

주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요 

가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토

-> 다른 알고리즘으로 풀이 방법이 떠오르지 않는다면 다이나믹 프로그래밍 고려 

일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤어(탐다운)작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있음 

일반적인 코딩테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우 많음

 

예제 1) 개미 전사

개미 전사: 문제 해결 아이디어 

 

파이썬 코드 

n = int(input())
arr = list(map(int, input().split()))
d = [0]*100

# 보텀엄 방식
d[0] = arr[0]
d[1] = max(arr[0], arr[1])
for i in range(2, n):
    d[i] = max(d[i-1], d[i-2]+arr[i])
print(d[n-1]) # 8