최적 선택

서로 다른 n개의 수가 주어졌을 때, 정렬하지 않고도 k번째로 작은 수를 출력할 수 있다. 이 문제는 선택 문제(selection problem)로 알려져 있으며 선형 시간에 해결할 수 있다. 선택 문제를 푸는 기존 알고리즘은 실용적으로 쓰기에는 너무 느리다고 주장하는 사람도 있다. 그래서 선택을 구성 요소로 사용하는 알고리즘을 만나면 선택을 빠른 정렬 절차로 마음대로 바꿔도 된다는 추측이 나왔다. 하지만 이 추측은 참이 아닌 것으로 보인다.

Bob은 위 추측이 타당한지 알아보려 하지만, 시행착오를 많이 거쳐야 하는 복잡한 문제라는 것을 깨닫는다. 몇 번 실패한 끝에 그는 먼저 선택을 구현하는 최선의 알고리즘을 찾는 데 집중하기로 한다. 즉, 가장 적은 횟수의 비교로 선택을 구현하는 알고리즘을 찾는 것이다. 입력으로 주어지는 n개의 수는 모두 서로 다르다고 가정한다. n = 3, k = 1일 때 선택 문제를 해결하는 최적 알고리즘은 다음과 같다.

double selection(double a[3], int k = 1){
    if(a[0] < a[1]){
        if(a[0] < a[2]){
            return a[0];
        } else{
            return a[2];
        }
    } else{
        if(a[1] < a[2]){
            return a[1];
        } else{
            return a[2];
        }
    }
}

가능한 모든 (a[0], a[1], a[2])에 대해 위 선택 함수는 비교를 최대 2번 사용한다. 실제로 두 입력 수 사이의 상대 순서를 비교로만 알아낼 수 있다면, 즉 비교 기반 알고리즘이라면 2번이 최선이다. 따라서 (n, k) = (3, 1)일 때 선택 함수의 복잡도는 2이다. 이제 Bob은 더 일반적인 문제를 생각한다. 선택 함수를 호출하기 전에 입력의 일부 쌍에 대한 비교 결과를 이미 알고 있는 경우이다. 선택 함수의 복잡도는, 일관성을 유지하는 모든 가능한 입력 배열에 대해 최적의 비교 기반 알고리즘이 요구하는 최악의 비교 횟수로 정의한다. 즉, Bob은 n, k, 그리고 n개 입력 수 사이의 일부 상대 순서가 주어졌을 때 선택 함수의 복잡도가 얼마인지 알고 싶어 한다.

첫째 줄에 세 정수 n, k, ℓ가 주어진다. 이어서 ℓ개의 줄이 주어진다. 다음 ℓ개 줄 각각에는 두 정수 x와 y가 [0, n − 1] 범위로 주어지며, 이는 선택 함수를 호출하기 전에 a[x]와 a[y]의 상대 순서가 a[x] < a[y]임을 알고 있음을 뜻한다.

n, k, 그리고 주어진 ℓ개 쌍의 상대 순서가 주어졌을 때 선택 함수의 복잡도를 출력한다.

• 1 ≤ n ≤ 8.
• 1 ≤ k ≤ n.
• 0 ≤ ℓ ≤ n.
• 주어진 ℓ개 쌍의 상대 순서는 일관성을 유지한다.