다이나믹 프로그래밍 문제를 해결할 수 있는 5가지 단계(Steps)

  다이나믹 프로그래밍 문제를 공부할 때 좋은 교육용 자료를 해외 사이트에서 찾아서 공유한다.

  ▶ 다이나믹 프로그래밍 문제를 해결할 수 있는 5가지 단계(Steps): https://www.youtube.com/watch?v=aPQY__2H3tE 

 

  ▶ 예시 문제: Longest Increasing Subsequence (LIS)

  LIS는 증가하는 가장 긴 부분 수열을 찾는 문제다. 예를 들어 [3, 1, 8, 2, 5]라는 수열이 있을 때, LIS는 [1, 2, 5]이다.

[1단계] Visualize examples (예제를 시각화하기)

  다이나믹 프로그래밍은 그래프 형태로 표현하면 이해하기 쉬운 경우가 많다.  예를 들어 LIS는 DAG (Directed Acyclic Graph) 그래프 형태로 표현이 가능하다.

[2단계] Find an appropriate subproblem (적절한 부분 문제를 찾기)

  모든 증가하는 부분 수열은 원본 수열(original sequence)의 부분집합이다. 또한 모든 LIS는 시작점(start)과 끝점(end)이 존재한다. 따라서 다음과 같이 부분 문제를 정의하는 것이 좋다.

  LIS[k] = 인덱스 k에서 끝나는 LIS의 길이

  구체적으로 [3, 1, 8, 2, 5]라는 수열이 있을 때 LIS 값은 다음과 같다.

LIS[0] = 1
LIS[1] = 1
LIS[2] = 2
LIS[3] = 2
LIS[4] = 3

[3단계] Find relationships among subproblems (부분 문제 간의 관계 찾기)

  [3, 1, 8, 2, 5]를 생각해보자. 이때 LIS[4]를 해결하기 위해서는 LIS[0] ~ LIS[3]를 이미 계산한 상태여야 한다. 또한 arr[4]보다 arr[2]가 더 크기 때문에, arr[2]를 제외한 인덱스 0, 1, 3만 고려해야 한다.

  따라서 LIS[4] = 1 + max{LIS[0], LIS[1], LIS[3]}으로 정의가 가능하다. 결과적으로 LIS[4] = 3인 것을 알 수 있다.

[4단계] Generalize the relationship (관계를 일반화하기)

  이러한 사실을 토대로 유추하건데, LIS[x] = 1 + max{LIS[k] | k < x, arr[k] < arr[x]}로 정리가 가능한 것을 알 수 있다.

[5단계] Implement by solving subproblems in order (코드로 구현하기)

  결과적으로 원소의 개수가 N개일 때, LIS[0] ~ LIS[N - 1] 중에서 가장 큰 값을 고르면 된다.

 

def lis(arr):
    lis = [1] * len(arr)
    for i in range(1, len(lis)):
        subproblems = [lis[k] for k in range(i) if arr[k] < arr[i]]
        lis[i] = 1 + max(subproblems, default=0)
    return max(lis, default=0)

print(lis([3, 1, 8, 2, 5]))