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