3587jjh   7년 전

데이터를 잘 처리해서 나온 2 0 3 1 4 라는 배열이 있으면,

여기서 두개를 선택해서 a > b 인 (a, b)의 개수를 구하는 문제임을 알았습니다. (2,0) / (2, 1) / (3, 1) 로 총 3개인데, 이걸 n^2 보다 빠르게 구하는 방법이 있을까요?

doju   7년 전

inversion(https://en.wikipedia.org/wiki/...)의 갯수는 O(n log n)만에 셀 수 있고, 보통 merge sort나 binary indexed tree(fenwick tree)를 사용해서 구현합니다.

https://www.quora.com/How-can-...

3587jjh   7년 전

감사합니다

댓글을 작성하려면 로그인해야 합니다.