[알고리즘] 동적계획법(DP)과 memoization 1

Hyo Kyun Lee·2022년 1월 13일
0

알고리즘

목록 보기
14/45

14. 동적계획법

Dynamic Programming, DP
분할정복과 비슷한 개념이긴하지만 memoization(이전 결과값의 저장과 활용)이 추가된 알고리즘을 말한다.

분할정복기법은 큰 문제를 반으로 나누어 잘게 쪼개고, 분할된 문제를 풀면서(혹은 정렬하면서) 큰 문제를 해결하는 과정을 의미하였다.

다만 분할정복의 단점은 분할된 문제들을 푸는 단계(step, 일련의 과정)들마다 동일한 해결기법을 계속 적용해야한다는 점이다.
이는 기존 완전이진트리에 정렬이 잘 된 data에 한해서는 빠르게 문제를 풀 수 있지만, 반복적으로 동일한 값을 사용하게되는 경우(*피보나치수열)엔 급속도로 성능이 저하된다.

14-1. 동적계획법의 적용

동적계획법을 적용할 수 있는 가장 직관적인 형태는 점화식으로 표현되어, 기존에 도출하였던 결과값을 이후에 다시 이용하는 경우이다.

  • D(N) = D(N-1) + D(N-2)

위와 같은 피보나치수열 점화식이 있다고 가정해보자.

이를 분할정복(완전이진트리 구성)으로 해결한다고 했을때, 위와 같이 불필요한 데이터 중복과 공간낭비가 발생하여 성능저하를 일으키는 요인이 발생한다.

이때 동적계획법, 특히 memoization을 이용하면 N이 커져도 시간복잡도를 2^n에서 n으로 매우 효율적으로 줄일 수 있다.

14-2. memoization

이전의 값들을 별도 배열에 저장하는 기법을 의미한다.

D(N)의 값은 미리 저장된 D(N-1), D(N-2) 값을 이용하여 도출한다.
이 방법이 분할정복과 DP와 다른 점이고, 이 관점이 컴퓨터적인 사고를 검증하는데 적합하기 때문에 DP관련한 문제종류가 매우 많고 활용이 많이 된다.

14-3. 알고리즘 구현

첫번째, 두번째는 초기값을 미리 지정해주어야 한다.

#피보나치수열
#DP의 가장 대표적인 예시
result = [0] * 100

def dp(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        result[n] = dp(n-1) + dp(n-2)
    return result[n]

print(dp(30))

0개의 댓글