LIS (Longgest Increaseing Subsequence)에 대해 이것 저것 정리

글을 쓰게 된 이유

이번 글은 친구의 "이 문제 LIS로 풀어야 하는 거 아니야??"에서 시작되었습니다.

 

해당 문제를 보니까 2년 전에 풀이한 문제이더라고요... (그리고 LIS가 무슨 뜻인지도 까먹고 있었습니다.)

 

 

문제랑은 상관이 없는 알고리즘이었으나, LIS(가장 긴 부분 수열 구하기) 알고리즘을 다시 공부하면서 기존에 알고 있었던 dynamic programming 방식(O(N^2))과 이를 시간 복잡도 측면에서 이분 탐색을 가미해 개선한 방식(O(NlogN))을 정리해보려 합니다.

---

LIS가 대체 무엇인가??

먼저 LIS에 대해서 간단히 정리해야 될 것 같습니다.

 

LIS는 Longgest Increasing Subsequence의 약자로, 가장 긴 증가하는 부분 수열을 의미합니다.

 

간단하게, 어떤 수열이 주어졌고 몇 개의 수를 골라 부분 수열을 만들 때, 오름 차순의 형태를 유지하는 가장 긴 부분 수열을 뜻한다고 정리할 수 있을 것 같습니다.

이런 수열이 있다고 해봅시다

위와 같은 수열이 있다고 했을 때, LIS는 다음과 같이 선택 가능합니다.

LIS 하나의 예시

LIS 중 하나의 예시입니다.

예시 중 하나인 이유는 (2, 3, 5, 8) 또한 위 케이스에서 LIS가 될 수 있기 때문이죠

 

 

그럼 이제 간단히 정리를 마쳤으니, LIS의 길이를 구할 수 있는 알고리즘을 알아보겠습니다.

---

다이내믹 프로그램 (Dynamic Programming, 동적 계획법) 활용법

이 방식은 아주 간단한 방식으로 O(N^2)의 시간 복잡도로 해결 가능한 모든 LIS 구하기에 쉽게 활용 가능합니다.

 

다이내믹 프로그래밍, 동적 계획법은 해결하고자 하는 큰 문제를 여러 개의 작은 문제로 나누고 그 결과를 합쳐 큰 문제의 결과를 도출해 내는 방식으로 문제를 해결하는 방법입니다.

 

LIS의 길이를 구하기 위해서도 동적 계획법 활용이 가능한데, 이는 현재 전체 배열을 작은 배열로 나누고 작은 배열의 LIS 길이를 이용해 전체 배열의 LIS 길이를 구하는 원리로 적용됩니다.

 

 

"백문이 불어일타!" 코드와 함께 원리를 정리해 보겠습니다.

 

// n은 전체 수열의 길이를 의미합니다.
for(int i = 1; i <= n; i++){
	// j를 이용해 배열의 첫 번째 원소 ~ i - 1번째 원소까지 탐색
	for(int j = 1; j < i; j++){
    	// dp[idx]: 0 ~ 'idx'번째 위치까지 가능한 LIS의 길이를 의미
        // dp 배열을 이용해 i에서 LIS의 길이를 갱신
    	if(arr[i] > arr[j] && dp[i] < dp[j] + 1){
        	dp[i] = dp[j] + 1;
        }
    }
}

위 코드는 전체 코드 중 dp 개념을 활용하는 일부이며, 주요 변수가 의미하는 바는 다음과 같습니다.

 

• i: 1 ~ n번째 원소를 탐색하는 index
• j: 1 ~ i - 1번째 원소를 탐색하는 index
• dp 배열: 각 index에 0 ~ 'index'번째 위치까지 가능한 LIS의 길이를 저장

 

코드를 보면, 더 이해가 쉽게 될 것 같습니다.

 

주석에 작성된 바와 같이 1 ~ i 원소가 구성하는 작은 배열의 LIS 길이를 1 ~ j 원소가 구성하는 작은 배열의 LIS 길이를 통해 구하고 있습니다. (여기서 DP가 활용)

 

이런 식으로 LIS의 길이를 구하는 방법이 가장 간단한 방법입니다.

 

 

하지만, 앞서 말했던 바와 같이 이 방식에는 단점이 있는데, 바로 시간 복잡도가 O(N^2)라는 점입니다.

---

Binary Search (이분 탐색)를 활용한 방법

이분 탐색을 이용하면, 전체 배열 중 원하는 위치를 O(logN)으로 탐색 가능하다는 점은 다들 알고 있으실 것 같습니다.

바로 이 원리를 활용해 LIS의 길이를 구할 수 있습니다.

 

다만, 접근 방식이 조금 다른데 이 방식은 LIS 배열을 만들면서 길이를 구한다고 이해하면 쉬울 것 같습니다. (만든 배열이 또 LIS는 아닙니다만..;;)

 

이 방법 또한 코드로 알아보겠습니다.

 

우선 이분 탐색은 다음과 같이 작성합니다.

특별할 것 없는 이분 탐색 코드입니다.

binarySearch 함수를 이용해 lis 배열에서 x보다 첫 번째로 큰 원소의 위치를 찾습니다. 

 

여기서 이분 탐색에 대해 깨달은 점은

 

처음에는 start = mid, end = mid - 1 방식으로 초기화를 했더니 무한 루프에 빠지는 문제를 발견했습니다.

이 문제는 mid 값을 계산할 때 실수 → 정수로 변환되는 과정에서 소수부를 버림으로 인해 start와 mid가 같은 값이 되어 발생하는 문제였습니다.

 

이를 통해 웬만하면, mid와 같은 값이 될 수 있는 start가 while 문의 조건을 어기도록 구현하는 것보다는 end를 갱신하는 방식이 좋지 않을까 생각하게 되었습니다.

 

추가로 이분 탐색의 반환 값은 start, end 중에서 로직을 만족하는 값으로 갱신된 녀석을 반환하는 방식으로 이해하고 있는데, 꽤나 적절한 것 같습니다. (아직까지는..?)

다음으로 lis(LIS) 배열을 갱신하는 로직입니다.

lis 배열 갱신 방식

먼저 배열의 다음 원소가 lis 배열에 담긴 마지막 원소보다 크다면, 그냥 넣어줍니다. 

 

하지만, 그렇지 않은 경우에는 lis 배열의 원소 중 현재 원소가 들어갈 적절한 위치를 이분 탐색을 통해 찾아 넣어주는데, 이 부분의 이유를 정리할 필요가 있습니다.

 

이는 바로 큰 원소만 뒤에 추가한다고 LIS가 되지 않기 때문이죠..

이에 더해서 같은 위치에 값을 넣는다고 하더라도 이왕이면, 작은 값이 들어가는 케이스가 전체 배열의 LIS를 구하는 데 도움이 되기 때문이라고 할 수 있을 것 같습니다.

LIS 예시를 다시 봅시다.

아까 그림 예시에서 (2, 3, 5, 8)이 아닌 (2, 3, 5, 7)을 LIS로 택한 것도 이러한 이유 때문입니다.

 

뒤에 어떤 원소가 올지 모르지만, 만약 8이라는 원소가 등장한다면 2, 3, 5, 8 뒤에서 LIS가 될 수 없는 반면, 2, 3, 5, 7이라면 가능하겠죠??

 

이는 가운데 어떤 원소가 들어가도 이후에 새로운 케이스의 LIS를 구하는데 있어서도 최대한 작은 값을 위치시키는 것이 유리하다는 점으로 확장해서 생각 가능합니다.

 

 

당연히 이에 따라서 최종 lis 배열이 진짜 LIS를 의미하지는 않지만, LIS의 길이를 구하는데 있어서는 문제가 없습니다.

 

이 방식으로 다음 문제를 해결할 수 있습니다. (입력 배열의 크기가 40,000에 이르러서 O(N^2) 으로는 해결 불가)

https://www.acmicpc.net/problem/2352

2352번: 반도체 설계

https://www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

이 문제는 dp로도 해결 가능합니다.

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

---

참고한 글

https://chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘