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

nemo·2025년 8월 17일

Java algorithm

▶️ 인사말

안녕하세요!! nemo입니다!!🐢

바로 들어가시죠!

▶️ 개요

백준 2631번: 줄세우기

얼마 전에 풀었던 문제입니다

문제를 요약하자면 뒤섞여 있는 줄을 다시 번호 순서대로 되돌려야 하는데 이동 횟수를 최소로 하여 원래 줄로 만들라는 문제 입니다

처음엔 백트래킹으로 문제를 접근 했는데 백트래킹은 N의 크키가 최대 200이라 경우의수가 너무 많아질 것이라 포기했습니다

문제의 핵심은 움직일 필요가 없는 친구들을 찾아 전체에서 움직일 필요 없는 친구를 뺀 나머지만 움직이면 된다 입니다

수가 나열 되어 있을 때 이미 오름 차순으로 정렬되어있는 친구들은 더 이상 움직일 필요 없고 나머지 친구들만 자신들의 위치로 가면 이동 횟수를 구할 수 있습니다

말이 어렵네요....
아무튼 이미 오름 차순으로 정렬 되어있는 친구들의 가장 긴 증가 수열을 차는 알고리즘 LIS를 써야 하는데 오랜만이라 다 까먹어서 다시 정리해보려고 합니다!!

▶️ LIS(Longest Increasing subsequence)

LIS(Longest Increasing Subsequence)는 주어진 수열에서 오름차순으로 증가하는 부분 수열 중 가장 긴 길이를 구하는 문제입니다.

수가 나열이 되어있을 때 최장 증가 수열은

[1, 3, 5]이고 길이는 3입니다

이 알고리즘은 DP, 이분 탐색 두가지 방법으로 구현할 수 있습니다

🟢 DP (O(N²))

dp[i] = i번째 원소를 마지막으로 하는 LIS의 길이

현재 보고 있는 수 보다 작으면서 최장 증가 수열의 길이를 알고있으면 그 길이에 +1한게 현재 최장 증가 수열의 길이입니다

1 -> [1]
4 -> [1, 4]
3 -> [1, 3]
5 -> [1, 3, 5]
2 -> [1, 3, 5]

코드로 표현하면 다음과 같습니다

for (int i = 0; i < n; i++) {
	dp[i] = 1;
    for (int j = 0; j < i; j++) {
    	if (arr[j] < arr[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
	answer = Math.max(answer, dp[i]);
}

🟢 이분 탐색 (O(N log N))

실제 LIS를 구하는 게 아니라, LIS의 길이만 효율적으로 구하는 방법입니다
새로운 배열 list를 만들고

현재 수가 list의 마지막 원소보다 크면 그냥 추가
아니라면, list에서 현재 수가 들어갈 자리를 이분 탐색으로 찾아서 교체

그림으로 표현하면 다음과 같습니다

-- 1 --

현재 수 추가

-- 4 --

4는 배열의 마지막 수 1보다 크기 때문에 그냥 추가

-- 3 --

3은 배열의 마지막 수 4보다 작기 때문에 들어갈 자리를 찾아 교체

-- 5 --

5는 배열의 마지막 수 3보다 크기 때문에 그냥 추가

-- 2 --

2는 마지막 수 보다 작기 때문에 위치를 찾고 교체

코드로 나타내면 다음과 같다


public static int binarySearch(int start, int end, int element){
	while(start < end){
    	int mid = (start + end) / 2;
        if(element > dp.get(mid)) start = mid + 1;
        else end = mid;
    }
    return end;
}
    
public static void LIS() {
	ArrayList<Integer> lis = new ArrayList<>();
	for(int i = 0; i < N; i++){
    	if(!lis.isEmpty() && nums[i] <= lis.get(dp.size() - 1)){
        int pos = binarySearch(0, lis.size()-1, nums[i]);
        lis.set(pos, nums[i]);
        continue;
    	}
        lis.add(nums[i]);
	}

System.out.println(lis.size());

}

이 방법은 LIS의 길이는 빠르게 구할 수 있지만 실제 LIS는 알 수 가 없습니다
이를 위해 추가 구현이 필요합니다

🟢 이분 탐색 수열 복원

실제 수열 복원을 위해, 각 단계에서 선택된 원소의 원본 인덱스와 이전 원소 인덱스(prev)를 추적합니다

int len = lis.size();
int cur = idxAtLen[len - 1];
int[] seq = new int[len];
for (int k = len - 1; k >= 0; k--) {
	seq[k] = nums[cur];
	cur = prev[cur];
}

▶️ 정리

방법	시간 복잡도	특징
DP (O(N²))	N²	구현이 쉽고 작은 입력에 적합
이분 탐색 (O(N log N))	N log N	큰 입력 처리 가능, 수열 복원은 추가 구현 필요

DP는 구현이 간단해서 빠르게 코드 작성이 가능 하지만 시간복잡도가 N²으로 꽤 크기 때문에 N이 크다면 쓰지 못하는 방식입니다

이분탐색은 시간 복잡도가 NlogN으로 빠르기 때분에 N이 큰 경우에 좋지만 수열을 복원하기위해서는 추가 구현이 필요하고 코드가 어렵다는 특징이 있습니다