[자료구조] 동적계획법

동적계획법 

0) 정의 

-> 다이나믹 프로그래밍 (Dynami Programming, DP) 라고도 불리며, 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어서 작은

문제의 정답들을 결합하여 알고리즘을 푸는 과정 

 

* 동적계획법을 풀어나감에 있어, 점화식의 공식을 찾아나가야 함 

 

1) Bottom Up 방법 

-> 작은 문제에서 큰 문제로 반복문 호출 

def fib(n):
    fibList = [1, 1]
    for i in range(2, n + 1):
        fibList.append(fibList[i-2] + fibList[i-1]) 
    return fibList[-1]

2) Top Down 방법 

-> 큰 문제에서 작은 문제로 재귀 호출 

def fib(n):
    if n == 0 or n == 1: 
        return 1 
    else:
        return fib(n-1) + fib(n-2)

* 위와 같은 방법들은 피보나치 값 하나를 구하기 위해 많은 계산량이 필요하고, 그와 동시에 중복된 계산이 발생한다.

---

2. 메모이제이션 (Memoization)

0) 정의 

-> 앞에서 했던 계산을 어딘가에 저장해두고, 필요한 경우 불러와서 활용할 수 있도록 하여 중복된 계산이 발생하는 것을 방지

 

1) 코드 

-> 메모이제이션을 활용할 딕셔너리 (또는 배열)를 선언 

memo = {0: 1, 1: 1}

def fibo(n):
    if n in memo:
        return memo[n]
    else:
        result = fib(n-1) + fib(n-2)
        memo[n] = result 
        return result

딕셔너리에 값이 저장되어 있다면 저장된 값을 불러오도록 하고, 그렇지 않다면 재귀함수를 활용하여 값을 찾는다. 

찾은 값을 딕셔너리에 다시 저장하고, 그 값을 반환 ! 

 

* 메모이제이션은 배열 혹은 해시를 활용하는 것이 핵심 

 

2) 활용 

Q. data = [3, 4, 5, 6, 1, 2, 5]가 주어졌을 때, 이웃하지 않는 숫자들의 합의 최대값을 구하여라 

 

해당 문제를 Bottom-Up 방식으로 풀어나가보자.

1) 데이터의 배열이 인덱스 0에 위치한 3 하나만 가지고 있다고 가정 

-> 합의 최댓값 = 3 

 

2) 데이터의 배열이 3만 가지고 있다, 인덱스 1에 위치한 4가 추가되었다고 가정 

-> 합의 최댓값 = 바로 이전 값인 3과, 현재 값인 4 둘 중의 최대값의 합이 최대값이 될 수 있음   ∴  4

 

3) 인덱스 2에 위치한 5가 추가되었다고 가정 

-> 합의 최댓값 = 바로 이전 값인 4와, 현재값인 5와 5와 이웃하지 않은 n = 0에서의 3과의 합 중 더 큰 값   ∴ 8 

 

4) 인덱스 3에 위치한 6이 추가되었다고 가정 

-> 합의 최댓값 = 이전 값인 8과 현재 값인 6과 6과 이웃하지 않은 n = 1에서의 4와의 합 중 더 큰 값  ∴ 10

    . . . 

 

7) 인덱스 6에 위치한 5가 추가되었다고 가정 

-> 합의 최댓값 = 이전 값인 12와 현재 값인 5와 5와 이웃하지 않은 n = 5에서의 10과의 합 중 더 큰 값    ∴15

 

 이를 점화식으로 나타내면 다음과 같다. 

이를 코드로 나타내면 다음과 같다. 

def solution(data):
    if len(data) == 1:
        return data[0]
    result = [data[0], max(data[0], data[1])]   
    for i in range(2, len(data)):   # Bottom-Up 
        result.append(max(result[i-1], result[i-2] + data[i])