파이썬으로 배열의 역전(Inversion) 개수를 계산하는 방법

이 글에서는 배열의 역전(inversion) 개수를 계산하는 문제와 그 해결 방법에 대해 알아보겠습니다.

문제 정의

주어진 리스트에서 필요한 역전의 개수를 세어 그 결과를 출력해야 합니다.

여기서 역전 개수(inversion count)란 배열을 오름차순으로 정렬하기 위해 필요한 교환 단계의 수를 의미합니다. 즉, 배열 내 두 원소의 순서가 정렬된 상태와 반대일 때마다 하나의 역전이 발생하며, 이를 모두 세면 됩니다.

알고리즘 구현

가장 직관적인 방법은 중첩 반복문을 사용하여 배열의 모든 원소 쌍을 비교하는 것입니다. 앞선 인덱스의 값이 뒤의 인덱스 값보다 크다면 역전이 존재하는 것이므로 카운트를 1씩 증가시킵니다.

예제 코드

# 역전 개수 계산 함수
def InvCount(arr, n):
    inv_count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if (arr[i] > arr[j]):
                inv_count += 1
    return inv_count

# 실행 코드
arr = [1, 5, 3, 8, 7]
n = len(arr)
print("Total number of inversions are:", InvCount(arr, n))

실행 결과

Total number of inversions are: 2

동작 원리 분석

위 예제에서 배열 [1, 5, 3, 8, 7]에는 두 개의 역전이 존재합니다.

• (5, 3): 5가 3보다 앞에 있지만 더 큰 값입니다.
• (8, 7): 8이 7보다 앞에 있지만 더 큰 값입니다.

모든 변수는 지역 범위(local scope) 내에서 선언되며, 각 반복 단계에서 참조됩니다. 시간 복잡도는 두 개의 중첩 반복문을 사용하므로 O(n²)입니다. 배열의 크기가 매우 클 경우에는 병합 정렬(merge sort) 기반의 O(n log n) 알고리즘을 사용하는 것이 효율적입니다.

결론

이 글에서는 파이썬을 활용하여 배열의 역전 개수를 계산하는 프로그램을 작성하는 방법을 살펴보았습니다. 브루트 포스 방식은 구현이 간단하지만 성능상 한계가 있으므로, 입력 크기에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.