[알고리즘] 최장 증가 수열 - LIS (Longest Increasing Subsequence)

최장 증가수열(Longest Increasing Subsequence) 문제는 왼쪽에서 오른쪽으로 나열된 수열이 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지면서 가장 긴 부분 수열을 추출하는 문제이다.

이때 문제마다 점진적으로 커지는 기준이 같은 수도 포함시킬 수 있으니 문제를 잘 읽고 풀어야 한다.

 

풀이 방법

기본적으로 최장 증가수열 문제를 풀 수 있는 방법은 크게 Brute-force 방식과 DP 방식 두 가지로 나눌 수 있다.

하지만 Brute-force 방식은 부분집합 알고리즘을 이용하여 지수 시간 복잡도를 가지기 때문에 추천할만한 방법은 아니다. 그러면 DP 방식을 통해 최장 증가수열 문제를 푸는 방법에 대해서 알아보자.

 

Dynamic Programming

n개의 숫자열 : a₁, a₂, ..., aₙ

LIS(i) : a₁, a₂, ..., aᵢ₋₁, aᵢ 에서 최장 부분 수열의 길이 

숫자열에서 증가수열 관계인 aⱼ < aᵢ인 aⱼ 를 찾고 LIS[j]에 1을 증가시켜 최대인지 비교하고 넣어준다.

 

 

pseudo code

FOR i in 1 -> n:
	LIS[i] = 1
    FOR j in 1 -> i-1:
    	IF aⱼ < aᵢ AND LIS[i] < 1 + LIS[j]:
        	LIS[i] = 1 + LIS[j]

RETURN max LIS[]