백준 12015 - 가장 긴 증가하는 부분 수열 (LIS) 2

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

12015번: 가장 긴 증가하는 부분 수열 2

통상적인 접근으로 dp를 적용하면 시간초과에 빠진다. dp 풀이에서는 매 i마다 0<= j < i인 j를 모두 확인해 대략 1부터 N까지의 합만큼의 연산을 수행한다. ex) i = 3 -> j = 0,1,2 / i = 13 -> j = 0,1,2,...11,12

 

따라서 시간 복잡도가 O(N^2)에 해당하므로, 위 문제처럼 큰 입력이 들어오면 감당할 수가 없다. 이번에는 큰 수열을 처리하는 시간복잡도 O(N log N)의 풀이를 배워보자. (나도 배운거임. 참조 : https://rebro.kr/33)

단, 이번 풀이로는 LIS의 길이만 구할 수 있다. (실제 LIS와 다를 수 있음)

 

0.

풀이의 핵심은, '증가하는 부분 수열을 직접 만들기' 이다. 따라서 크기 N의 dp 배열 대신, 이번에는 비어있는 배열을 사용한다. 직접 만들 배열이니까 이름은 DIY라고 하자. 그리고 첫 번째 원소만 놓고 생각하면, 원소 하나만 있을 경우 이 원소는 무조건 LIS에 포함된다. 그러므로 반복문 시작 전 DIY에 첫 원소를 넣어둔다.

vector<int> DIY;
DIY.push_back(v[0]);

 

1.

{10, 30, 50, 40, 45} 배열을 처리해보자.

첫 원소 10은 무조건 DIY에 집어넣고, 다음 원소부터는 DIY의 맨 끝 원소와 비교한다. 30은 끝 원소 10보다 크다. 배열 끝에 추가하자. 끝 원소는 30이 된다. 50은 끝 원소 30보다 크다. 배열 끝에 추가하자. 끝 원소는 50이 된다. 여기까지는 쉽다.

for (int i = 1; i < N; i++) {
	int last = DIY[DIY.size() - 1];
    if (v[i] > last)
        DIY.push_back(v[i]);

2.

40을 처리할 차례이다.

 

LIS의 규칙만 가지고 배열 {10, 30, 50, 40}을 처리하면 만들 수 있는 배열은 {10, 30, 50}, {10, 30, 40} 두 가지이다. 하지만 {10, 30, 50}은 뒤의 원소 45를 추가하지 못하고, {10, 30, 40}은 추가할 수 있어 결과적으로 더 긴 LIS가 된다. 다시 말하면 DIY 안의 원소를 가능한 작게 유지해야 DIY의 길이가 더 길어진다. 일종의 그리디? 알고리즘으로 생각해도 될 것 같다.

 

i번째 원소가 1번의 if문에 해당하지 않을 경우, 즉 맨 끝 원소보다 작을 경우 DIY 배열 내에서 v[i]가 들어갈 수 있는  위치를 찾아 원래 있던 값을 v[i]로 대체한다. 이 위치란 v[i]보다 크거나 같은 원소가 나오는 첫 번째 인덱스이며, DIY 배열은 오름차순으로 정렬된 배열이므로 이분탐색, 또는 lower_bound를 사용해 이 위치를 O(log N)의 시간에 찾을 수 있다.

for (int i = 1; i < N; i++) {
	int last = DIY[DIY.size() - 1];
    if (v[i] > last)
        DIY.push_back(v[i]);
    else
    	//이분탐색으로 v[i] 위치 계산
        DIY[lower_bound(DIY.begin(), DIY.end(), v[i]) - DIY.begin()] = v[i];
}

위 규칙대로 배열을 마저 처리해보자.

40은 끝 원소 50보다 크지 않다. 40이 들어갈 수 있는 위치를 찾는다. DIY 배열 내에서 40보다 크거나 같은 첫 원소는 50이므로 50을 40으로 바꿔준다. 끝 원소는 40이 된다. 45는 40보다 크다. 45를 배열 끝에 추가한다.

결과 : {10, 30, 40, 45}

 

완성한 배열의 크기가 곧 LIS의 길이가 된다.

 

3.

이 방법으로 문제를 해결할 순 있지만, 이렇게 얻은 배열이 실제 LIS라는 보장은 없다. 동일한 길이만 보장할 뿐이다.

배열 {100, 200, 300, 1, 2}를 처리한 결과는 다음과 같다.

{100} -> {100, 200} -> {100, 200, 300} -> {1, 200, 300} (1보다 크거나 같은 첫 원소 100을 1로 교체) -> {1, 2, 300} (200을 2로 교체)

 

{1, 2, 300}은 실제 LIS인 {100, 200, 300}과 다르다. 다만 길이를 보장하는 이유는 위 알고리즘에서

- 맨 끝 원소보다 클 경우 뒤에 추가

- 작을 경우 내부에서 크거나 같은 첫 원소 교체

두 작업만 수행하기 때문, 즉 내부에서는 길이의 증가가 이뤄지지 않기 때문이다.

 

아니 그러면 교체도 맨 끝 값만 해주면 되지 않나요??? 안 된다. 그렇게 제출했을 때 틀렸다..

{100, 200, 300, 150, 160, 180} 배열을 처리해보면 알 수 있다. 맨 끝을 바꾸려면 내부 원소도 차근차근 바꿔줘야 한다.

 

4. 실제 배열 찾기 (좀 긺)

그럼 실제 LIS 배열은 어떻게 찾을까?

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

이 문제는 배열 길이와 더불어 실제 수열까지 답으로 요구한다... 욕심쟁이 녀석

 

이제 실제 수열을 구하기 위해 새로운 정보를 저장할 배열을 생성하자. 이름은 idx라고 하겠다. 이 배열은 크기 N을 갖고 시작한다. idx[i]에는 'i번 원소가 DIY에서 위치하는 인덱스 번호'가 저장된다. (여기서의 인덱스는 1-base, 즉 1부터 시작하는 인덱스로 하자)

 

앞전의 알고리즘에서 모든 원소는 그 크기에 상관없이 DIY에 포함되었다. 맨 끝 원소보다 클 경우 DIY 맨 끝에 추가되는 건 당연하며, 작더라도 버려지지 않고 포함 가능한 위치에 저장된다. 따라서 idx[i]에는 반드시 1~N의 값이 존재한다.

else
    DIY[lower_bound(DIY.begin(), DIY.end(), v[i]) - DIY.begin()] = v[i];
//v[i]는 반드시 어딘가에 저장됨!!

배열 {10, 30, 50, 40, 45}의 idx 값은 어떻게 될까? 직접 계산해보면 {1, 2, 3, 3, 4}이 될 것이다.

 

 

이제 1부터 LIS 길이까지의 자연수에 대해 idx에서 이와 일치하는 값 중 가장 뒤에 있는 값의 위치를 찾는다.

 

다시 방금의 idx 배열을 예시로 들면 1부터 4까지의 값중 가장 뒤에 위치한 값의 위치를 찾으면 된다. * 값이 아니라 위치만!! 결과는 다음과 같다. {1, 2, 3, 3, 4}

 

이제 원래 배열에서 해당 위치에 있는 원소값을 출력하면 된다.

 

코드 구현은 다음과 같다.

 

현재 찾는 값 T := LIS의 길이에서 시작한다.

배열을 끝에서부터 순회하며 idx[i] = T일 경우 v[i]를 답에 추가한다.

T를 찾았으면 이제 이보다 1 작은 값을 찾을 차례이다. T를 1 감소시킨다.

 

답을 출력하기 전, 끝에서부터 순회했으므로 원래 방향대로 출력하기 위해 답을 한번 뒤집어야 한다. 스택을 사용하면 편하다.

 

이게 답이 되는 이유는 대략 이렇다.

idx[i] = 10이고 v[i]가 실제 LIS에 포함된다면(최적해), idx[j] = 9이고 v[j]가 최적해인 j는 i의 뒤에 존재할 수 있을까? 불가능하다. 그리고 j보다 앞에 존재하는 k에 대해, idx[k]가 9일 때, v[j]도 최적해이고 v[k]도 최적해일 수 있을까? 귀류법으로 이게 가능하다고 하면 v[k]가 최적해이기 때문에 idx가 동일한, 즉 같은 위치에 존재하는 v[j]는 최적해가 될 수 없다. 이는 모순이므로 v[k]는 최적해일 수가 없다.

 

요컨대 현 위치의 원소 v[i]가 최적해라면, 다음 최적해는 idx[j] 값이 idx[i] - 1이며 i보다 앞에 위치한 j 중 가장 뒤에 있는 원소가 된다.