LIS로 알아보는 역추적 기법

귀엽다

개요

 

참고 문제: BOJ 11053, BOJ 12015, BOJ 14003, BOJ2568

LIS 개념: https://eckrin.tistory.com/30

 

O(N^2)의 LIS 풀이: https://www.acmicpc.net/source/37212239
O(NlogN)의 LIS 풀이: https://www.acmicpc.net/source/75537735

 

for(int i=0; i<N; i++) //오른쪽에 위치한 수들에 대하여
    for(int j=0; j<N; j++) 
        if(arr[i]<arr[j]) //조건에 맞을경우 캐시에 저장
            dp[j] = max(dp[j], dp[i]+1);

 

 반복문만을 사용하는 LIS의 경우, O(N^2)의 시간복잡도를 가진다. 여기서 12015번 문제의 경우는 N이 백만으로, O(N^2)의 시간복잡도를 가지는 일반적인 LIS를 사용하면 무조건 TL이 날 것을 예상할 수 있다.

 

int end = 0;
for(int i=0; i<N; i++) { // 배열 각각의 원소에 대하여
    if(end==0) { // 초기화
        dp[end] = arr[i];
        continue;
    }
    if(arr[i]>dp[end-1]) { // dp 최대길이 갱신
        dp[end] = arr[i];
        end++;
    } else {
        int curIdx = binarySearch(0, end, arr[i]); // 내부로 들어갈 경우 0~end범위 이진탐색
        dp[curIdx] = arr[i];
    }
}

 

https://loosie.tistory.com/376

 

그래서 위와 같이 binary search를 사용하면 O(N^2)인 LIS의 시간복잡도를 O(NlogN)으로 줄일 수 있다. 간단하게 요약하면, arr값을 하나하나 읽어가며 dp배열(위 그림에서는 memo)의 어느 위치에 들어가야 할지를 정하는 것이다. 

 

 12015번은 LIS의 길이만을 구하라고 하기 때문에 배열에 0~end 범위내에서 이진탐색하거나, 배열에 추가하여 end범위를 늘리는 선택을 반복하여 답을 구할 수 있다. 그런데 14003번은 LIS의 길이와 함께 LIS를 만족하는 배열을 출력하라는 추가조건이 있는데, 이럴 때 사용할 수 있는 방법이 역추적이다.

 

 

역추적 알아보기

 

 binary search를 이용한 LIS에서 arr배열을 탐색해나가면서 dp배열의 어느 위치에 들어가야 할지를 정하고(맨 끝일 경우 dp배열의 맨 마지막에, 중간일 경우 이진탐색을 사용하여 위치를 찾는다), 그 과정에서 dp배열은 계속 갱신되기 때문에 반복문이 끝나면 dp배열은 LIS를 만족시키는 배열과는 모양이 달라질 확률이 높다.

 

트래킹을 위한 방법은 해당 인덱스가 어떤 dp인덱스에 저장되었는지를 저장하는 배열(아래 index 배열)만 하나 만들어주면 된다. 예를 들자면, arr을 순회하면서 dp값을 저장할 때 arr[i]가 dp[j]에 저장되었다면 index[i]에는 j값을 넣어주면 된다.

 

arr = {1,5,6,2,3,4} 라고 하자. i=2까지 들어왔을때는 아래와 같은 모양을 띌 것이다.

 

i	0	1	2	3	4	5
arr	1	5	6	2	3	4
dp	1	5	6
index	0	1	2

 

i=3일때는 dp[1]에 있는 값이 덧씌워지고, index[3]에는 1(저장된 dp의 index값)이 들어간다.

i	0	1	2	3	4	5
arr	1	5	6	2	3	4
dp	1	2	6
index	0	1	2	1

 

i=4일때는 dp[2]의 값이 덧씌워지고, index[4]에는 2가 들어간다.

i	0	1	2	3	4	5
arr	1	5	6	2	3	4
dp	1	2	3
index	0	1	2	1	2

 

i=5일때는 dp[3]에 새로운 값이 들어가고, index[5]에는 3이 들어간다.

i	0	1	2	3	4	5
arr	1	5	6	2	3	4
dp	1	2	3	4
index	0	1	2	1	2	3

 

최종적인 배열의 형태는 위와 같다. 

 

이제 LIS의 길이는 end값(4)이 되고, index에서 LIS가 만들어질 때의 배열 형태를 추출하면 되는데, 그 방법은 오른쪽부터 end-1부터 시작하며 처음 나오는 값을 출력하는 것이다.

 

3이 처음 나오는 위치는 i=5이므로 arr[5]를 출력하고, 2가 처음 나오는 위치는 i=4이므로 arr[4], 1이 처음나오는 위치는 i=3이므로 arr[3], 0이 처음나오는 위치는 i=0이므로 arr[0]을 출력하면 된다. 이때 나는 index를 i=0부터 스택에 넣고 하나씩 빼내면서 처음 나오는지 여부를 확인해나갔다.

 

(end = 4)

n (0<=n<end)	0	1	2	3
n이 처음 나오는 위치	0	3	4	5
arr[n이 처음 나오는 위치]	1	2	3	4

 

1 2 3 4가 답이 된다.

 

 

이유?

 

 왜 오른쪽부터 처음 나오는 값의 인덱스 i를 찾아 arr[i]를 호출하는건지 궁금할 수도 있는데, 정확히 말하면 처음 나오는 값의 인덱스를 무조건 호출하기 때문이 아니라, end-1부터 시작하여 오른쪽부터 하나씩 줄여가며 인덱스를 호출하기 때문에 그렇다.

 

(end=3)

i	0	1	2	3
arr	1	5	7	6
dp	1	6	7
index	0	1	2	1

 

이 케이스를 보자. 현재 dp값은 1 6 7로, 주어진 arr의 LIS가 아니다. 하지만 end-1부터 오른쪽부터 탐색하면

 

end-1 (2)가 처음 나오는 인덱스 : 2

end-2 (1)이 처음 나오는 인덱스: 1

end-3 (0)이 처음 나오는 인덱스: 0

 

로, 해당 인덱스들의 arr값을 출력하면 정답 (1 5 7)이 된다.

 

end-1은 반드시 LIS의 가장 오른쪽 값이기 때문에, 그로부터 왼쪽에 위치한 end-2값은 반드시 end-1보다 작게 되는 것이다. 다시 말해서 end-1부터 시작하여 1개씩 감소하는 (end-1, end-2, ... ,0) 어떤 순서도 LIS가 된다.