[Python] 가장 긴 증가하는 부분 수열 길이를 찾는 LIS 알고리즘

🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다.

 

이번 포스팅에서는 가장 긴 증가하는 부분 수열 길이를 찾는 LIS(Longest Increasing Subsequence) 알고리즘 동작 과정을 이해해보고 Python으로 구현하는 방법에 대해 알아보자.

 

가장 긴 증가하는 부분 수열의 길이를 찾아보자.

---

1. 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열이란 무엇일까? 단어로만 이해하기에는 잘 와닿지 않는다. 다음과 같은 수열이 주어져 있다고 가정하자.

 

 

위 수열에서 오름차순으로 증가하는 부분 수열 중 가장 길이가 긴 수열이 바로 가장 긴 증가하는 부분 수열을 의미한다. 그리고 그 가장 긴 수열의 길이를 찾아주는 알고리즘이 LIS 알고리즘이다. 위 수열에서 3번째, 5번째 값인 10, 20을 빼주면 10 - 20 - 30 - 50 으로 길이가 4인 가장 긴 길이의 증가하는 부분 수열이다. 

 

헷갈릴 수도 있는데 수열의 원소들을 아무것도 건드리지 않고 부분 길이가 가장 긴 것을 찾는게 아니라 수열에서 임의의 원소들을 삭제했을 때 나올 수 있는 가장 긴 길이의 증가하는 부분 수열을 의미한다.

2. LIS 알고리즘 동작과정

그렇다면 LIS 알고리즘이 어떻게 가장 긴 증가하는 부분 수열의 길이를 찾는지 살펴보자. 여기서 다이나믹 프로그래밍의 DP 테이블을 활용하는데, DP 테이블의 원소값은 주어진 수열의 특정 값을 마지막 원소로 가지는 부분 수열의 최대 길이를 의미한다. 그래서 초기 DP 테이블 값은 모두 자기 자신의 원소를 의미하는 것으로 1로 초기화 해준다.

 

초기 상태

 

이제 수열에서 2번째 값(20)부터 하나씩 확인해서 2번째 값이 직전의 값보다 크다면 DP 테이블에서 2번째 값을 업데이트 시켜준다. 이 때, 점화식을 활용하는데, 업데이트 전 DP 테이블의 2번째 값과 DP 테이블의 1번째 값에 1을 더한 값 중 최댓값을 업데이트 시켜준다. 점화식으로 나타내면 다음과 같다. $$DP[i] = max(DP[i], DP[j] + 1), \ if\ array[j] < array[i]\ (0 \le j <  i)$$

따라서 2번째 값에 대해 DP 테이블을 갱신해주면 다음과 같아진다.

 

 

다음은 3번째 값인 10 차례이다. 3번째 값인 10은 직전 값인 (두번째 값) 20보다 작고 20의 직전 값(첫번째 값)인 10과 같기 때문에 해당 점화식으로 처리하지 않고 무시하고 DP테이블을 갱신하지 않는다. 눈치가 빠르신 분들은 3번째 값을 처리할 때 2번째 값을 처리할 때보다 점화식 조건 절차를 한 번 더 했다는 것을 눈치챌 것이다. 결국 수열의 인덱스가 늘어날 수록 확인하는 절차는 선형적으로 증가한다. 예를 들어 수열의 10번째 값을 확인한다고 하면 1~9번째 값까지 총 9번을 대소비교하면서 조건에 만족하면 점화식 처리를 해야 한다.

 

따라서 위와 같은 과정을 반복해서 수열의 마지막 원소 인덱스 위치까지 확인 절차를 걸치면 아래와 같이 DP 테이블이 최종 갱신된다.

 

최종 DP 테이블

 

최종 DP 테이블에서 가장 원소가 큰 값 즉, 빨간색으로 된 4라는 값이 바로 가장 긴 증가하는 부분 수열 길이를 의미하게 된다.

3. LIS 알고리즘 Python 으로 구현하기

참고로 아래 알고리즘을 활용해서 풀 수 있는 문제도 있으니 해당 문제를 풀어보는 것도 좋을 듯 하다.

 

n = int(input())  # 수열의 길이
array = list(map(int, input().split()))  # 주어진 수열

# DP 테이블 1로 초기화
dp = [1] * n

for i in range(1, n):
    for j in range(0, i):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)

# 가장 긴 증가하는 부분 수열의 길이값
result = max(dp)
print(result)