[SW 정글 19일차] 동적 프로그래밍과 분할정복법

동적 프로그래밍(DP)은 '큰 문제를 '작은 문제를 해결하며 나온 해'를 결합하여 해결하는 것'이다. 이는 분할 정복법과 유사해 보인다. 분할 정복법 또한 '원래 문제를 몇 개의 부분 문제로 분할하며 재귀적으로 해결'한다. 이렇게 찾은 부분 문제의 해를 결합하여 원래 문제의 해를 찾는다. 그렇다면 DP와 차이점은?

 

DP는 문제에 최적 부분 구조(optimal substructure)와 중복 부분 문제(overlapping subproblems)가 있을 때 적용할 수 있다. 최적 부분 구조란, 부분 문제의 최적해가 원래 문제의 최적해 속에 포함되어 있다는 것이다. 중복 부분 문제는 부분 문제들을 해결해 가는 과정에서 중복되는(=동일한 값을 계산하기 위한) 값을 반복해서 풀게 되는 것이다.

위 그림은 분할 정복법으로 피보나치수열의 다섯번 째를 나타낼 때까지 필요한 함수 호출이다. fibo(3)은 두 번 계산되며 fibo(2)와 fibo(1)을 각각 두 번씩 총 네 번 호출해야 함을 알 수 있다. 시간 비효율적이며, 메모리 낭비가 있다. 이를 Overlapping Subproblem이라고 한다. 이런 비효율을 해결하기 위해 DP의 Memoization(메모이제이션)을 활용할 수 있다.

 

Memoization(메모이제이션) - Top-Down

F = {1:1, 2:1}

def fib2(n):
	if n in F:
    	return F[n]
    else:
    	F[n] = fib2(n-1) + fib2(n-2)
        return F[n]
print(fiv2(5))
print(F)

 

• 기록(저장)을 해두고, 재사용하는 구조

계산해서 이미 저장해둔 것은 '바로' 리턴하자!

 

위 코드와 같이 F dictionary에 n이 있으면 F의 value 값을 '바로' return 하고, 그렇지 않으면 재귀(fib2(n-1) + fib2(n-2))로 구한 값을 F[n]에 저장하고, value 값을 return 하는 것이다. 'F[n]'에 저장하는 것이 memoization 요소임을 알 수 있다. 이렇게 중복 부분 문제를 해결 가능하다.

 

Tabulation(타뷸레이션) - Bottom-Up

F = {}

def fib3(n):
	F[1] = F[2] = 1
    for i in range(3, n+1):
    	F[i] = F[i-1] + F[i-2]
    return F[n]
print(fib3(5))
print(F)

• 재귀식으로 상향식 해법을 찾아서 반복문으로 전환하여 중복 부분 문제 해결하는 구조

밑에서부터 저장하는 것을 쌓아가자!

 

위 코드와 같이 fib3 함수가 실행될 때 비어 있는 F dictionary는 반복문이 진행될 수록 값이 key 값이 증가하며 동시에 value 값이 저장된다. 이를 DP의 Tabulation이라고 한다.

 

한 DP 강의 자료에 '문제를 봤을 때, DP 문제인지도 모르는 경우가 많다'고 써져 있었다. 부분 문제가 독립적이지 않고, memoization, tabulation을 활용할 수 있다면 DP가 아닌지 의심해보는 것이 좋겠다.

---

벌써 정글에서 WEEK3가 시작되었다.

시간이 정말 빠르게 흘러간다.

어제의 나보다 오늘 1%만 더 나아지자. 100일이면 2.7배.