Skip to content

Latest commit

 

History

History
142 lines (96 loc) · 4.98 KB

동적 계획법(Dynamic Programming).md

File metadata and controls

142 lines (96 loc) · 4.98 KB
Raw

동적 계획법 (Dynmaic Programming)

복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법


흔히 말하는 DP가 바로 '동적 계획법'

  • 처음 진행되는 연산은 기록
  • 이미 진행되었던 연산이라면 다시 연살할 때 기록되어 있는 값을 호출
  • 시간 & 자원절약 가능

한 가지 문제에 대해서, 단 한 번만 풀도록 만들어주는 알고리즘

조금 장난스럽게 말하면 답을 재활용하는 거다.

실행시간을 줄이기 위해 많이 이용되는 수학적 접근 방식의 알고리즘이라고 할 수 있는데,
엄밀히 말해 동적 계획법은 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가깝다.

동적 계획법은 특히 Optimal Substructure에서 효과를 발휘한다.

Optimal Substructure : 답을 구하기 위해 이미 수행한 똑같은 계산을 계속 반복하는 문제 구조(== 최적부분구조)


접근방식


커다란 문제를 쉽게 해결하기 위해 작게 쪼개서 해결하는 방법인 분할 정복 알고리즘과 매우 비슷하다. 하지만 원래의 문제를 부분적인 간단한 문제로 만드는 과정에서 차이점이 존재한다.

일반적으로 상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다. 다만 '정렬'과 같은 몇몇 요소에 대해서는 동일한 문제를 다시 풀게 되는 단점이 없다. (그 예시로 퀵정렬이나 병합정렬은 매우 빠르다.)

동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 속도를 향상시킨다.


즉, 쉽게 말해 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 나중에 전체의 답을 구하는 것이다.

이 과정에서 '메모이제이션'이 사용된다는 점이 분할 정복과 다르다.


조건


  • 작은 문제에서 반복이 일어남

  • 같은 문제는 항상 정담이 같음


이 두 가지 조건이 충족한다면, 동적 계획법을 이용하여 문제를 풀 수 있다.
같은 문제가 항상 정답이 같고, 반복적으로 일어난다는 점을 활용해 메모이제이션(Memoization)으로 큰 문제를 해결해 나가는 것이다.

메모이제이션(Memoization) : 한 번 계산한 문제는 다시 계산하지 않도록 저장해두고 활용하는 방식

피보나치 수열에서 재귀를 활용하여 풀 경우, 같은 연산을 계속 반복함을 알 수 있다.

피보나치_재귀적 풀이: O(2ⁿ)

def fibo(n):
    if n >= 2:
        return fibo(n-1) + fibo(n-2)
    else:
        return n

이 때, 메모이제이션을 통해 같은 작업을 되풀이 하지 않도록 구현하면 효율적이다.

피보나치_메모이제이션 풀이(Top-Down): O(N)

dp_Memo = [0] * 11
dp_Memo[0] = 1
dp_Memo[1] = 1

def fibo_Memo(n):

    # 한번도 계산한 적이 없는 경우

    if dp_Memo[n] == 0:
        dp_Memo[n] = fibo(n-1) + fibo(n-2)
    

    # 새롭게 추가 값 혹은 저장된 값 반환

    return dp_Memo[n]  

이처럼 같은 연산이 계속 반복적으로 이용될 때, 메모이제이션을 활용하여 값을 미리 저장해 둘수 있다.

피보나치 구현에 재귀를 활용했다면 시간복잡도는 O(2^n)이지만, 동적 계획법을 활용하면 O(N)으로 해결할 수 있다.


구현 방식


- Bottom-up : 작은 문제부터 차근차근 구하는 방법
- Top-down : 큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그때 해결하는 방법 (재귀 방식)

Bottom-up은 해결이 용이하지만, 가독성이 떨어짐
Top-down은 가독성이 좋지만, 코드 작성이 힘듬



동적 계획법은 어떤 문제에 적용?


  • 동적 계획법 = 소문제의 결과를 다른 소문제를 푸는데 사용하는 풀이법

  • 우선 최적성의 원리를 만족하는지 판단해야 한다.
    ▶ 최적성의 원리 : 부분해가 전체 문제의 해를 구하는데 사용되는지를 의미

  • 최적성의 원리가 적용되는 것이 확인되었으면 주어진 문제를 소문제로 분해하여 최적해를 제공하는 점화식을 도출해야 한다.

동적 계획법 vs 분할 정복


  • 동적 계획법 : 소문제 종속적
    소문제가 상위 문제에 영향을 끼치며 원소들이 종속적이다.
    (cf. 피보나치 수열)

  • 분할 정복 : 소문제 독립적
    각각 분할된 원소들이 정렬 과정에서 다른 원소들의 영향을 미치지 않는다.
    (cf. 퀵 정렬, 병합 정렬)