[종만북] 문제: KLIS

게시 2024/12/26 업데이트 2025/03/06

By 정승우

10 분읽는 시간

문제

중복되는 $LIS$ (Longest Increasing subsequence) 중, 사전 순으로 정렬했을 때 중복되는 $k$번째의 $LIS$를 구하는 문제입니다.

문제 링크

서론

지금까지 DP를 이용하여 최댓값이나 최솟값을 구하는 문제를 풀어보았습니다.

하지만, 최댓값이나 최솟값이 아닌 k번째의 답을 계산하는건 어떨까요?

이럴 때에도 DP를 적용하여 풀 수 있습니다. 핵심 아이디어는 이렇습니다.

재귀함수를 통해 만들어지는 답들의 개수를 $M$, 구하려고 하는 답을 $k$번째 답이라 생각해 봅시다.

이 재귀함수에서

$M \leq k$이면, 재귀함수에 만들어지는 답들 중에 원하는 답이 없으므로, 이 재귀함수를 건너뜁니다. 건너뛰었다면, $k$를 $k-M$만큼 줄입니다.

$M > k$ 이면, 재귀함수에서 만들어지는 답들 중에 원하는 답이 있으니, 재귀호출을 이용해 값의 범위를 줄여 나갑니다.

알고리즘 구상

구현하기 위해 무엇이 필요한가

일단 $k$번째 답을 구하기도 전에 모든 답을 구해봅시다.

먼저, $LIS$를 구하는 알고리즘 부터 알아봅시다.

$LIS$를 구하는 알고리즘은 $LIS$의 최장 길이를 구하는 알고리즘과, 원소의 이전 원소의 $index$를 나타내는 $prev[1…n]$배열을 이용해 $traceback$을 구현할 수 있습니다.

하지만, 이 방식에는 문제점이 있습니다. 바로 값이 여러 개 존재할 경우 문제가 생긴다는 것입니다.

이 문제를 해결하기 위해 2차원 동적 배열을 이용해 각 원소의 이전 원소에 해당하는 것들을 모두 포함할 수 있습니다.

$prev[1…n]$배열이여도 풀 순 있지만, 구현하기 쉽게 각 원소의 다음 원소를 가리키는 $next$배열을 만들 것입니다.

하지만, 이 $next[1…n][1…i]$배열만으로는 아직 구현을 할 수 없습니다.

따라서 $index$가 $i$부터 끝까지 $LIS$의 개수를 나타내는 $count[1…n]$배열을 만들어서, $k$번째 $LIS$를 구할 것입니다.

작동 순서

$DP$를 이용해서 최장 $LIS$의 길이를 모든 $index$에서 구합니다.
$next$배열을 구합니다.
재귀를 이용해서 $LIS$의 개수를 나타내는 $count$배열을 구합니다.
$LIS$의 시작 $index$들을 $source$배열에 담습니다.
$source$배열에서 시작 $index$를 찾습니다.
얻은 시작 $index$에서 $next$배열을 이용해 $traceback$을 구현합니다.

알고리즘 구현

오버플로우가 문제야

원소의 수 $n(1<n \leq 500)$와 $k$($int$ 범위)가 주어졌고, $count$배열에 $LIS$의 개수를 전부 구하기로 했습니다.

만약 LIS의 최대의 개수는 몇 개일까요? 최악의 경우는 $2, 1, 4, 3, 6, 5, …$ 형태의 수열입니다. 이 때 나올 수 있는 최댓값은 $2^{n/2}$개입니다.

long long에서 표현할 수 있는 가장 큰 수는 $2^{63} - 1$입니다.

이는 $2^{250} > 2^{63}-1$ 으로 한참 못미치죠.. 대책이 필요합니다.

위와 같은 문제를 해결하기 위해, $k$보다 큰 어떤 수를 이용해서 오버플로우를 회피하는 코드를 작성합니다.

$k + 1$을 이용해서, count[i]가 $k+1$보다 커지려고 하면, 그냥 $k+1$로 숫자를 정해버립니다. 이는 오버플로우의 Saturation 처리 방식이죠!

아래 코드는 <functional>클래스를 이용해서 구현한 코드입니다.

  
vector<long long> cacheCnt(n+1, -1);
function<long long(int)> paths_count = [&](int cur) -> long long {
    if (cacheCnt[cur] != -1) {
        return cacheCnt[cur];
    }
    // 마지막 노드(DP[cur] == maxLen)면 경로 1개
    if (DP[cur] == maxLen) {
        cacheCnt[cur] = 1;
        return 1;
    }
    long long sumCnt = 0;
    for (int nx : next[cur]) {
        long long tmp = paths_count(nx);  // 오버플로우 처리
        if (sumCnt + tmp >= k + 1) {
            sumCnt = k + 1;
            break;
        } else {
            sumCnt += tmp;
        }
    }
    cacheCnt[cur] = sumCnt;
    return sumCnt; 
};

정렬이 필요한가?

교과서에서는 pair<int, int> 배열에 (arr[index], index)를 저장해서 첫 번째 원소(다음 원소의 값)을 기준으로 오름차순 정렬하는 방법을 제시합니다.

하지만, 정렬을 사용하지 않고 오름차순 정렬을 구할 수 있습니다.

$next$배열은, 사실상 $LIS$의 $DAG(Directed Acyclic Graph)$라고 볼 수 있습니다.

$Graph$의 어떤 $Vertex$의 $edge$가 여러 $Vertex$들을 가리킨다고 해봅시다.

그러면, index가 클수록 index의 값(arr[index])은 작아야 합니다.

왜 이럴까요? 증명은 귀류법으로 가능합니다. index가 커도 arr[index]또한 큰 Vertex가 존재한다고 가정하면, LIS가 새로 만들어 질수 있겠죠, 이는 모순입니다.

정리하면, index를 내림차순 정렬한다면, arr[index]또한 오름차순 정렬이 가능하겠죠!

아래의 코드는 index를 기준으로 내림차순으로 반복문을 실행해 arr[index]기준으로 정렬된 효과를 줍니다.

  
vector<vector<int>> next(n + 1);
for (int i = 1; i <= n; i++) {
    for (int j = n; j >= i + 1; j--) {
        if (arr[j] > arr[i] && DP[j] == DP[i] + 1) {
            next[i].push_back(j);
        }
    }
}

source또한 위와 같이 가능합니다!

  
vector<int> source;
for (int i = n; i >= 1; i--) {
    if (DP[i] == 1) {
        source.push_back(i);
    }
}

최종 코드

최종 코드를 확인하고 싶으면 여기에서 확인하세요!

알고리즘 개선방안

어떻게 0ms가 나온거지

위와 같이 구현하면 작동시간은 8ms가 나오나, 다른 방식을 이용하여 구현한 사람은 0ms가 나왔습니다.

차이점으로 저는 구현을 편하게 하기 위해서 $next$배열을 만들어 구현하였는데,

이 분은 $prev$배열을 통해 구현하였고. vector 사용 없이 오직 array로 만으로 구현하였습니다.

이렇게 하면 값을 정리하기 힘드므로, 이런 식으로 struct를 만들어서 값들을 관리하는 모습입니다.

  
struct LDS {
	int len;
	int cnt;
	int prev[MAX];
	int prevCnt;

	void clear() {
		len = 0;
		cnt = 0;
		prevCnt = 0;
	}

	void push(int i) {
		prev[prevCnt++] = i;
	}
};

이 분의 최종 코드는 여기에서 볼 수 있습니다!

개선 가능한 부분

현재 코드는 $O(n^2)$시간이 걸리나, 세그먼트 트리나 펜윅 트리를 활용하면 $O(n\cdot logn)$시간 안에 구현 가능합니다.

알고리즘, 종만북

알고리즘 종만북