Coding Test(다이나믹 프로그래밍)

다이나믹 프로그래밍

- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

- 이미 계산된 결과는 별도의 메모리 영역에 저장 ==> 메모이제이션(Memoization)

TopDown(메모이제이션) : 하향식

BottomUp : 상향식

<조건>

1. 최적 부분 구조(Optimal Substructure)

- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

2. 중복되는 부분 문제(Overlapping Subproblem)

- 동일한 작은 문제를 반복적으로 해결해야 한다.

 

다이나믹 프로그래밍 vs 분할 정복

- 2개 모두 최적 부분 구조를 가질 때 사용(큰 문제를 작은 문제로 나눌 수 있을 때)

- 차이점은 부분 문제의 중복

  다이나믹 프로그래밍 : 각 부분 문제들이 서로 영향을 미치며 부분 문제 중복

  분할 정복 : 동일한 부분 문제가 반복적으로 계산되지 x

 

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘

LIS의 개념은 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것이다.

어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며,

이 수열이 오름차순을 유지하면 '증가하는 부분 수열'이 되는 것이다. 

그러므로 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이 LIS이다.

dp = [0 for i in range(n)]
for i in range(n):
    for j in range(i):
        if data[i] > data[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1