가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python)

개념

가장 긴 증가하는 부분 수열 다시 말하면 LIS라고도 하는 이것은 다이나믹 프로그래밍 기법 중에 하나입니다. 말 그대로 어떤 수열이 주어졌을 때 해당하는 수열에서 오름차순 혹은 내림차순으로 가장 긴 증가하는 부분의 숫자가 몇 개가 존재하는지를 카운트하는 알고리즘입니다. 예시와 함께 알아보겠습니다.

 

array = [10, 20, 10, 30, 20, 50]일때 가장 긴 증가하는 부분의 숫자를 출력하시오 라는 문제가 있다고 가정하면 10, 20, 30, 50 즉 4가 정답입니다. 이중 for문이 있다면 쉽게 해결할 수 있습니다. array의 길이만큼의 리스트 dp를 1로 초기화한 후 이중 for문으로 조회하면서 해당하는 값에 1을 더한 값과 원래 값의 max값을 넣어주면 되는 것입니다.

소스코드는 다음과 같습니다.

---

소스코드

arr = [10, 20, 10, 30, 20, 50]
n = len(arr)
dp = [1] * n
 
for i in range(1, n):
  for j in range(i):
    if arr[j] < arr[i]:
      dp[i] = max(dp[i], dp[j]+ 1)
 
print(dp)
print(max(dp))