수열 a(1), a(2), ..., a(n)
에서 정렬되지 않은 쌍이란 a(j) > a(k) (j < k) 를 말합니다. 모든 정렬되지 않은 쌍의 개수를 어떻게 빠르게 셀 수 있을까요.
각각의 a(k) 에 대해 a(1)~a(k-1) 을 모두 살펴보아서 자신보다 크면 세는 방법이 있습니다. 총 n*(n-1)/2 번의 비교가 이루어 지겠군요. 이 방법은 n 이 십만 정도로 커지면 너무 오래 걸립니다.
자신보다 앞의 결과를 저장한 후 사용하여 시간을 단축하기 위해 관계를 찾아봅니다.
d(k) 를 a(1)~a(k-1) 중 a(k) 보다 큰 것들의 개수라고 합시다. 물론 d(1)=0 입니다.
d(j, k) 를 a(j)~a(k-1) 중 a(k) 보다 큰 것들의 개수라고 합시다. d(k) = d(1, k) 가 되겠군요.
문제의 답은 d(1) + d(2) + ... + d(n) 이 되겠죠. 따라서 d(k)를 구하는 시간을 줄이는 것이 목표가 될 것입니다.
d(k) 에 대한 어떤 관계식을 생각해봅시다.
다음과 같은 것도 생각할 수 있겠죠.
만약 어떤 j (j < k) 에 대해 a(j)==a(k) 라면 d(k) = d(j) + d(j,k) 가 되겠죠. a(1)~a(j-1) 중 a(k) 보다 큰 것들의 개수는 d(j) 이니까요.
하지만 이는 만족스럽지 못합니다. 만약 수열 a 에 같은 수가 하나도 없다면 전혀 관계식을 써먹을 수 없기 때문이죠. 있다고 해도 k 와 j 가 아주 멀리 있다면 j를 찾기 위해 걸리는 시간이나 a(1)~a(k-1)을 모두 a(k)와 비교해 보는 시간이나 별로 다를 것이 없기 때문이기도 합니다.
그렇다면 어떤 j (j < k) 에 대해 a(j) > a(k) 일 때 d(k) 를 d(j)로 설명할 수 있다면 성공적이겠죠. 그러한 j 가 하나라도 있다면 관계식을 써먹을 수 있고 없다면 자동적으로 d(j) 는 0 이 되기 때문입니다. 더욱이 그러한 j는 꽤 많이 존재할텐데 왜냐면 무작위 수열일 경우에 자기보다 클 확률은 50프로이기 때문이죠. 따라서 그러한 j는 k와 아주 가까운데서 쉽게 찾을 수 있을겁니다.
식은 다음과 같겠죠.
d(k) = d(j, k) + d(j) + (a(1)~a(j) 중 a(k)보다 크고 a(j)보다 작은 것들의 개수)
이는 d(j) 가 a(1)~a(j) 중 a(j)보다 작은 것들의 개수는 세지 못했기 때문이죠.
식이 추잡하네요. 식이 우아해지지 못하면 보통 망하더군요.
음 다른 방법을 생각해봅시다.
d(k)를 찾고 정렬을 한다면 d(k+1)는 이진탐색을 통해 쉽게 찾을 수 있겠죠.
정렬에 걸리는 시간을 생각해봅시다. 항상 이미 정렬되어 있는 상태니까 새 원소를 제자리에 삽입하는 방법이 적당하겠죠.
정렬에 걸리는 시간을 다 합치면 그냥 길이 n짜리 수열을 삽입정렬하는 시간이기 때문에 최악의 경우 O(n^2)이 되겠네요. 에라이; 이진탐색에 걸리는 시간 세지도 않았는데 이미 느낌이 별로 좋지 않군요.
분명 우아한 솔루션이 존재할거 같은 느낌인데.... (자살)
글쓰기