DSA Interview Prep · 강의

수정된 병합 정렬로 역전쌍 세기

Q: DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.

Q: “수정된 병합 정렬로 역전쌍 세기” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

병합 단계에서 분할을 가로지르는 역전쌍을 세어 배열의 역전쌍 수를 구합니다. 역전쌍은 a[i] > a[j]이고 i < j인 쌍입니다.

수정된 병합 정렬로 역전쌍 세기은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

역전이란 무엇인가

배열의 역전은 (i, j)에 대해 i < j이지만 a[i] > a[j]인 인덱스 쌍입니다. 즉, 더 큰 원소가 더 작은 원소보다 앞에 나타나는 경우입니다. 예를 들어 [3, 1, 2]에서는 역전이 (3,1)과 (3,2)이므로 역전 수는 2입니다. 정렬된 배열의 역전 수는 0입니다. n개 원소로 이루어진 역순 정렬 배열의 역전 수는 n(n-1)/2입니다. 역전 수를 세면 배열이 정렬 상태에서 얼마나 벗어나 있는지 측정할 수 있습니다.

arr = [3, 1, 2]
# Inversions: pairs (i,j) where i<j and arr[i]>arr[j]
inversions = []
for i in range(len(arr)):
    for j in range(i+1, len(arr)):
        if arr[i] > arr[j]:
            inversions.append((arr[i], arr[j]))
print('Inversions in', arr, ':', inversions)
print('Count:', len(inversions))  # 2

# Maximum inversions in n-element array:
import math
n = 5
print(f'Max inversions for n={n}: {n*(n-1)//2}')  # 10 for [5,4,3,2,1]

단순한 O(n²) 접근법

완전 탐색 접근법은 i < j인 모든 쌍 (i, j)을 확인하고 a[i] > a[j]인 쌍을 셉니다. 시간 복잡도는 O(n²), 공간 복잡도는 O(1)입니다. n = 10⁵이면 5 × 10⁹번 비교해야 하므로 너무 느립니다. 수정된 병합 정렬을 사용하는 분할 정복 접근법은 이를 O(n log n)에 해결합니다. 핵심 통찰은 병합 정렬의 병합 단계에서 분할을 가로지르는 역전을 효율적으로 셀 수 있다는 것입니다.

def count_inversions_brute(arr):
    n = len(arr)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                count += 1
    return count

print(count_inversions_brute([3, 1, 2]))   # 2
print(count_inversions_brute([5, 4, 3, 2, 1]))  # 10
print(count_inversions_brute([1, 2, 3, 4, 5]))  # 0
print(count_inversions_brute([2, 4, 1, 3, 5]))  # 3

병합 정렬의 핵심 통찰

정렬된 두 절반 L과 R을 병합할 때, R[j]이 L[i]보다 작기 때문에 L[i] 대신 R[j]을 선택한다면 남아 있는 모든 원소는 R[j]보다 큽니다. L이 정렬되어 있기 때문입니다. 따라서 오른쪽 절반에서 원소를 가져올 때마다 len(L) - i개의 양쪽 절반 역전을 셉니다. 이 계산은 별도의 비용 없이 일반적인 병합 과정에서 수행됩니다.

# During merge of [1, 3, 5] and [2, 4, 6]:
# Compare L[0]=1 vs R[0]=2: take L[0]=1, no inversions
# Compare L[1]=3 vs R[0]=2: take R[0]=2, inversions += len(L)-1 = 2 (3>2, 5>2)
# Compare L[1]=3 vs R[1]=4: take L[1]=3, no inversions
# Compare L[2]=5 vs R[1]=4: take R[1]=4, inversions += len(L)-2 = 1 (5>4)
# Compare L[2]=5 vs R[2]=6: take L[2]=5, no inversions
# Take R[2]=6
# Total cross-inversions = 2 + 1 = 3
print('Cross-inversions identified during merge: 3')

수정된 병합 정렬 구현

병합 정렬이 정렬된 배열과 역전 수를 모두 반환하도록 수정합니다. 전체 역전 수 = 왼쪽 절반의 역전 수 + 오른쪽 절반의 역전 수 + 병합 중 발견한 양쪽 절반 역전 수입니다. 기저 사례에서는 (원소 하나, 역전 0개)를 반환합니다. 병합 함수는 병합하면서 역전을 셉니다. 전체 시간 복잡도는 O(n log n)입니다.

def count_inversions(arr):
    def merge_sort_count(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left,  left_count  = merge_sort_count(arr[:mid])
        right, right_count = merge_sort_count(arr[mid:])
        merged, cross_count = merge_count(left, right)
        return merged, left_count + right_count + cross_count
    
    def merge_count(left, right):
        result, count = [], 0
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i]); i += 1
            else:
                result.append(right[j]); j += 1
                count += len(left) - i  # all remaining in left are inversions
        result += left[i:] + right[j:]
        return result, count
    
    _, total = merge_sort_count(arr)
    return total

print(count_inversions([3, 1, 2]))        # 2
print(count_inversions([5, 4, 3, 2, 1])) # 10
print(count_inversions([2, 4, 1, 3, 5])) # 3

알고리즘 추적

[2, 4, 1, 3]을 추적해 봅니다. [2, 4]와 [1, 3]으로 분할합니다. 왼쪽 하위 정렬: [2, 4] → 정렬 결과 [2,4], 역전 0개. 오른쪽 하위 정렬: [1, 3] → 정렬 결과 [1,3], 역전 0개. [2,4]와 [1,3]을 병합합니다. 1을 선택합니다(2>1 및 4>1이므로 개수에 2를 더합니다). 2를 선택합니다(개수 변화 없음). 3을 선택합니다(4>3이므로 개수에 1을 더합니다). 그런 다음 4를 선택합니다. 양쪽 절반 역전 수 = 3입니다. 전체 = 0+0+3 = 3입니다. 검증하면 쌍 (2,1), (4,1), (4,3) = 역전 3개입니다. ✓

def count_with_trace(arr):
    def ms(arr, depth=0):
        indent = '  ' * depth
        if len(arr) <= 1: return arr, 0
        mid = len(arr) // 2
        L, lc = ms(arr[:mid], depth+1)
        R, rc = ms(arr[mid:], depth+1)
        merged, cc = merge_c(L, R)
        print(f'{indent}merge({L},{R}) → cross={cc}')
        return merged, lc + rc + cc
    
    def merge_c(L, R):
        res, c, i, j = [], 0, 0, 0
        while i < len(L) and j < len(R):
            if L[i] <= R[j]: res.append(L[i]); i += 1
            else: res.append(R[j]); j += 1; c += len(L) - i
        return res + L[i:] + R[j:], c
    
    _, total = ms(arr)
    return total

print('Total inversions:', count_with_trace([2, 4, 1, 3]))

양쪽 절반 역전이 정확히 포착되는 이유

정확성은 다음과 같습니다. i < j인 모든 역전 쌍 (a[i], a[j])은 정확히 세 범주 중 하나에 속합니다. (1) 왼쪽 절반에 모두 있음 — 재귀적인 왼쪽 호출에서 셉니다. (2) 오른쪽 절반에 모두 있음 — 재귀적인 오른쪽 호출에서 셉니다. (3) 왼쪽 절반의 원소가 오른쪽 절반의 원소보다 큼 — 병합 중 양쪽 절반 역전으로 셉니다. 이 범주들은 서로 배타적이며 모든 경우를 포함하므로, 어떤 역전도 중복해서 세거나 놓치지 않습니다. 이러한 분할 논증은 분할 정복 정확성 증명의 표준 방법입니다.

# Verification: compare with brute force on random arrays
import random

def count_brute(arr):
    n = len(arr)
    return sum(1 for i in range(n) for j in range(i+1,n) if arr[i]>arr[j])

def count_dc(arr):
    def ms(a):
        if len(a)<=1: return a, 0
        m=len(a)//2
        L,lc=ms(a[:m]); R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr)[1]

for _ in range(100):
    arr = random.choices(range(20), k=random.randint(1,10))
    assert count_dc(arr[:]) == count_brute(arr), 'MISMATCH!'
print('All 100 random tests passed!')

역전 수의 응용

역전 수는 정렬 상태를 측정합니다. 응용 사례는 다음과 같습니다. (1) 순위 상관관계: 순위가 매겨진 두 목록 사이의 켄달 타우 거리는 역전 수입니다. (2) 삽입 정렬의 효율성: 삽입 정렬은 역전 수와 정확히 같은 횟수만큼 교환합니다. (3) 버블 정렬 분석: 버블 정렬을 한 번 수행할 때마다 역전 수가 줄어들며, 필요한 수행 횟수는 역전 수와 같습니다. (4) 퍼즐의 풀이 가능성: 8퍼즐이나 15퍼즐은 역전 수의 홀짝성이 특정 조건을 만족할 때 그리고 그때만 풀 수 있습니다.

# Kendall tau: number of inversions between two rankings
# Useful for comparing search result rankings or recommendation systems

def kendall_tau(rank1, rank2):
    '''Count inversions where rank1 and rank2 disagree on relative order.'''
    # Map rank2 positions to create a comparison sequence
    pos = {v: i for i, v in enumerate(rank2)}
    # Convert rank1 to position-in-rank2 ordering
    arr = [pos[v] for v in rank1]
    return count_inversions(arr)

def count_inversions(arr):
    def ms(a):
        if len(a)<=1: return a,0
        m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr[:])[1]

print(kendall_tau([1,2,3],[3,1,2]))  # measures disagreement

역전 쌍

역전 쌍 (LeetCode 493)은 (i, j)에 대해 i < j이고 nums[i] > 2 × nums[j]인 쌍을 셉니다. 일반적인 역전 수에서는 nums[i] > nums[j]를 사용합니다. 여기서는 기준이 2 × nums[j]로 바뀝니다. 병합 정렬을 수정하여 병합하기 전에 분할을 가로지르는 쌍을 셉니다(왼쪽 절반에 조건을 만족하는 원소가 남아 있는 동안 두 포인터로 셉니다). 그런 다음 평소처럼 병합합니다. 전체 시간 복잡도는 O(n log n)입니다.

def reverse_pairs(nums):
    def merge_sort_count(arr):
        if len(arr) <= 1: return arr, 0
        mid = len(arr) // 2
        L, lc = merge_sort_count(arr[:mid])
        R, rc = merge_sort_count(arr[mid:])
        # Count cross pairs: L[i] > 2*R[j]
        j = 0
        cross = 0
        for l_val in L:
            while j < len(R) and l_val > 2 * R[j]:
                j += 1
            cross += j
        # Normal merge (separate from count)
        merged = []
        i = jj = 0
        while i < len(L) and jj < len(R):
            if L[i] <= R[jj]: merged.append(L[i]); i += 1
            else: merged.append(R[jj]); jj += 1
        merged += L[i:] + R[jj:]
        return merged, lc + rc + cross
    
    return merge_sort_count(nums)[1]

print(reverse_pairs([1, 3, 2, 3, 1]))  # 2
print(reverse_pairs([2, 4, 3, 5, 1])) # 3

전역 역전 개수와 지역 역전

전역 및 지역 역전 (LeetCode 775): 0..n-1의 순열이 주어졌을 때, 전역 역전(모든 i<j이고 a[i]>a[j]인 쌍)의 개수가 지역 역전(인접한 쌍)의 개수와 같은지 판별합니다. 핵심 통찰은 모든 지역 역전이 전역 역전이기도 하다는 것이므로 전역 역전 ≥ 지역 역전입니다. 두 개수가 같은 경우는 인접하지 않은 역전이 없을 때뿐이며, 이는 어떤 원소도 정렬된 인덱스에서 1보다 멀리 떨어져 있지 않다는 뜻입니다. 따라서 모든 i에 대해 abs(a[i] - i) ≤ 1을 확인하는 문제로 줄어듭니다.

def is_ideal_permutation(A):
    '''Global inversions == local inversions
    iff no element is more than 1 position from its sorted index.'''
    return all(abs(a - i) <= 1 for i, a in enumerate(A))

print(is_ideal_permutation([1, 0, 2]))  # True
print(is_ideal_permutation([1, 2, 0]))  # False (A[0]=1 is far from 2, A[2]=0 is far)

# Verification with inversion counts
print(count_inversions([1, 0, 2]))  # 1 (global)
local1 = sum(1 for i in range(len([1,0,2])-1) if [1,0,2][i]>[1,0,2][i+1])
print('local:', local1)  # 1 (equal)

def count_inversions(arr):
    def ms(a):
        if len(a)<=1: return a,0
        m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr[:])[1]

역전 개수 복잡도 요약

요약하면 다음과 같습니다. 완전 탐색으로 역전 개수를 세면 O(n²)입니다. 수정된 병합 정렬은 병합 단계에서 분할을 가로지르는 역전을 세어 O(n log n)을 달성합니다. 추가 비용은 비교마다 O(1)입니다(len(left) - i를 더함). 따라서 전체 추가 비용은 병합 정렬의 각 단계마다 O(n)으로, 표준 병합 정렬과 같습니다. 보조 배열에 필요한 공간은 O(n)입니다. 이는 분할 정복을 사용해 선형로그 시간에 순서 통계량을 세는 대표적인 예입니다.

import time, random

def time_method(func, arr):
    start = time.time()
    result = func(arr[:])
    return result, time.time() - start

def count_brute(arr):
    return sum(1 for i in range(len(arr)) for j in range(i+1,len(arr)) if arr[i]>arr[j])

def count_dc(arr):
    def ms(a):
        if len(a)<=1: return a,0
        m=len(a)//2;L,lc=ms(a[:m]);R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr[:])[1]

arr = random.sample(range(1000), 1000)
r1, t1 = time_method(count_brute, arr)
r2, t2 = time_method(count_dc, arr)
print(f'Brute: {r1} in {t1:.4f}s')
print(f'D&C:   {r2} in {t2:.4f}s')
print(f'Speedup: {t1/t2:.1f}x')

빠른 확인

이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.

단원 복습

이 단원에서는 다음을 배웠습니다. 역전은 배열이 얼마나 정렬되지 않았는지를 나타내며, 완전 탐색의 복잡도는 O(n²), 분할 정복의 복잡도는 O(n log n)입니다. 또한 수정된 병합 정렬은 오른쪽 원소가 왼쪽 원소보다 먼저 선택될 때마다 len(left)-i를 더해 두 절반을 가로지르는 역전을 셉니다. 그리고 정확성은 분할에 기반합니다. 왼쪽 내부 역전, 오른쪽 내부 역전, 두 부분을 가로지르는 역전은 서로 겹치지 않으며, 함께 모든 역전을 포함합니다. 다음에는 다수 원소를 찾는 Boyer-Moore 투표 알고리즘을 살펴봅니다.

자주 묻는 질문