Dynamic Programming(동적 계획법)

본 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리하는 글입니다.

 

 

피보나치의 재귀

def Fibonacci(n):
  if n == 1 or n == 2:
    return 1
    
  return Fibonacci(n-1) + Fibonacci(n-2)

 

피보나치의 수열을 재귀함수로 구현했다고 하자.

이전의 두 수의 합이 다음의 수가 되는데, 만약 F(5)를 구하기 위해서 위와 같은 재귀함수를 작성했다면

 

그림과 같이 함수가 호출되어 구해질 것이다.

문제는 색깔로 구분되어있듯 같은 값을 계속 호출하여 또다시 계산한다는 점이다.

한 번 계산한 값을 다시 계산한다니 듣기만 해도 비효율적인데 호출횟수가 늘어나면 매우 비효율적이 된다.

 

이 문제를 해결하려면 어떤 방법을 쓰면 될까?

첫째로는 값을 처음 계산할 때 저장해두고 다시 그 값이 호출되었을 때 가져와 쓰는 방법이 있을 것이고,

두 번째는 역으로 F(1)부터 계산해서 F(5)까지 올라가며 값이 계산될 때 필요한 값을 미리 계산해두는 방법이 있을 것이다.

 

첫 번째 방법은 위에서 아래로 내려오는 Top-Down 방식인 Memorization

두 번째 방법은 아래서 위로 올라가는 Bottom-Up 방식인 Dynamic Programming이라고 한다.

(Dynamic Programming은 좁은 의미로 쓰일 때는 Bottom-Up방식만, 넓은 의미로 쓰일 때는 두 방식을 모두 일컫는다.)

 

Memorization

cache = [-1, -1, -1, -1, -1, -1]

def Fibonacci(n):
  if n == 1 or n == 2:
    return 1

  if cache[n] < 0: # 처음 불러와진 값
    cache[n] = Fibonacci(n-1) + Fibonacci(n-2) #값을 저장
    return cache[n]
  else:#이미 불러와진 적이 있는 값
    return cache[n]

 

Memorization은 위에서 말했듯 값이 처음 호출된 순간 그 값을 저장해놓았다가 필요할 때 꺼내쓴다.

이러한 것을 caching한다고 한다.

 

Dynamic Programming

array = [-1, -1, -1, -1, -1, -1]

def Fibonacci(n):
  for i in range(1, n+1):
    if i == 1 or i == 2:
      array[i] = 1
    else:
      array[i] = array[i-1] + array[i-2]
      
  return array[n]

 

Dynamic Programming은 값을 계산 시 필요한 값들을 미리 계산해두고 값을 계산할 때 가져와쓰는 방식을 말한다.

Memorization과 달리 기본적인 값부터 목표 값까지 올라가듯 계산한다는 점에서 차이가 있다.

 

Memorization vs Dynamic Programming

Memorization	Dynamic Programming
Top-Down	Bottom-Up
실제로 필요한 Sub Problem만 푼다.	재귀에 필요한 오버헤드가 없다.

 

동적 계획법의 용도

동적계획법은 점화식으로 표현할 수 있는 문제를 계산하는데 사용할 수 있는 기법이다.

그래서 점화식으로 표현할 수 없다면 동적 계획법으로 풀 수 없다.

 

대표적으로는 최솟값, 최댓값을 구하는 문제인 최적화 문제나

특정 조건을 만족하는 해의 개수를 구하는 Counting 문제에 적합하다.

또한 점화'식'이기 때문에 수치적인 값을 구하는 문제에 사용된다.

 

즉, 동적 계획법은 점화식으로 표현할 수 있는 문제를 중복 없이 효과적으로 풀기 위해 사용하는데,

주로 최적화 문제나 Counting 문제에 쓰인다.

 

동적 계획법 vs 분할과 정복

동적 계획법은 점화식으로 표현할 수 있는 문제를 계산하는데 사용한다고 하였다.

앞서 풀었던 백준 2579 - 계단 오르기의 점화식을 간단하게 가져와보자.

 

S(i) = max(S(i-2), S(i-1)) + stairs[i] (i>1), S(0) = 0, S(1) = 1

 

i번째 계단에 도착할 때 가질 수 있는 가장 높은 점수는

① i-2번째 계단에서 i번째 계단을 오를 때의 점수

② i-1번째 계단에서 i번째 계단을 오를 때의 점수

중 max값이다.

 

라는 점화식이다.

i-2번째 계단의 값인 S(i-2)나 i-1번째 계단의 값인 S(i-1)은

i번째 계단의 값인 S(i)와 로직이 동일하지만 그보다 작은 문제라 할 수 있다.

여기서 S(i-1)이나 S(i-2)와 같은 문제들을 Sub Problem이라고 하는데

동적 계획법은 이러한 Sub Problem을 풀어서 원래의 문제를 푸는 방식이다.

(애초에 점화식이 원래 값 = Sub Problem의 조합 꼴이기 때문에 그렇다)

 

 

문제의 Sub Problem을 풀어서 원래 문제를 해결한다는 아이디어는 분할과 정복의 아이디어와 비슷한데,

분할과 정복은 Sub Problem이 로직은 같지만 영역이 서로 겹치지 않는, 즉 Disjoint한 반면,

동적 계획법은 로직이 같음은 동일하지만 그 영역이 서로 겹치는, 즉 Overlapping된 Sub Problem들이라는 점에서 구분된다.

 

예를 들어 Quick Sort의 경우 대표적인 분할과 정복 알고리즘 중 하나인데,

pivot을 기준으로 동일한 로직을 수행하는 영역이 좌/우로 나뉘어 겹치지 않음을 볼 수 있다.

그에 반해 계단 오르기와 같은 문제의 경우 i-1까지의 최댓값을 구하는 영역과 i-2까지의 최댓값을 구하는 영역이 겹친다.

 

Optimal Substructure

이렇게 Sub Problem들의 해를 통해서 원래 문제를 푸는 방식에서 주의해야할 사항이 있는데 바로

'최적해의 일부분이 그 부분에 대한 최적해인가?'를 꼭 생각해야한다.

즉, Sub Problem의 해가 정말로 최적(최소 or 최대)값이 맞는가?를 체크하고 넘어가야한다.