반전 인덱스 (1) 썸네일형 리스트형 Inversion Counting을 펜윅 트리(BIT)로 풀기 정렬되지 않은 배열을 스왑 기반 정렬(버블, 선택, 삽입 등)로 정렬할 때, 총 스왑 횟수를 구하라. 이 문제는 Inversion Counting 또는 Inversion Index로 불리는 유명한 문제다. (인터넷에서는 Inversion Counting이라는 용어가 더 알려져 있으므로 게시글에서는 Inversion Counting이라 부른다.) 이 게시글에서는 Inversion Counting을 펜윅 트리(Binary Indexed Tree)로 푸는 방법을 소개한다. 어떻게 푸는가? 우리는 배열 A의 i번째 원소 A[i] 뒤에 A[i]보다 작은 원소가 몇 개 존재하는지 펜윅 트리로 저장할 것이다. 그 값을 val이라고 했을 때 i번째 인덱스 뒤에 A[i]보다 작은 원소가 없게 하기 위해 val번 만큼 s.. 이전 1 다음
