[Algorithm] 동적 계획법(dynamic programming)

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

동적 계획법은 부분 문제를 풀고 결과를 저장한 후, 다음 부분 문제를 푸는 과정에서 저장된 결과를 사용한다. 그렇기 때문에 문제가 '최적 부분 구조'와 '중복되는 부분 문제'를 갖고 있다면 동적 계획법으로 해결이 가능하다

 

최적 부분 구조 : 답을 구하기 위해서 했던 계산을 반복해야 하는 문제의 구조

 

 

상향식 접근을 사용하는 것이 중요!

 

메모이제이션

프로그램이 동일한 계산을 반복할 때 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거해 프로그램의 실행 속도를 빠르게 하는 기법이다. 

 

예제 - 최장 증가 부분열

주어진 리스트에서 '최장 증가 부분열'을 찾아보자. 최장 증가 부분열이란, 증가하는 순서대로 숫자를 고른 부분열의 길이가 최대가 되는 배열이다. 예를 들어 리스트 [94, 8, 78, 22, 38, 79, 93, 8, 84, 39]가 있다고 하면 가장 길게 증가하는 부분열은 [8, 22, 38, 79, 93] 또는 [8, 22, 38, 79, 84]가 된다.

 

이를 동적 계획법으로 구현할 경우, 이전 원소가 현재 원소보다 작은 경우 이것이 오름차순 항목의 후보가 될 수 있기 때문에 길이를 1 증가시킨 후 이 값을 비교해 현재 길이에 저장시킨다.

 

 

구현 코드

def solution(seq):
    L = [1] * len(seq)
    for cur, val in enumerate(seq):
        for pre in range(cur):
            if seq[pre] <= val:
                L[cur] = max(L[cur], L[pre]+1)
    return max(L)