연습 문제

직접 만든 연습 문제 네 개를 풀이 방향, Python 풀이와 함께 소개합니다. 풀이를 보기 전에 먼저 입력을 어떻게 나눌지, 경계를 넘어 전달해야 할 정보가 무엇인지 생각해 봅니다.

문제 1: 의견이 갈린 심사위원

두 심사위원이 같은 참가자 n명에게 각각 1등부터 꼴등까지 순위를 매겼습니다. 두 심사위원이 서로 반대 순서로 매긴 참가자 쌍의 수를 구합니다. n은 200,000까지이므로 모든 쌍을 확인하면 너무 느립니다.

풀이 방향: 심사위원 A의 순서대로 참가자에게 번호를 매기고, 심사위원 B의 목록을 그 번호로 바꿉니다. 두 사람의 순서가 다른 쌍은 바꾼 목록의 역순 쌍과 정확히 일치하므로, 역순 쌍 세기로 O(n log n)에 답을 구합니다.

def disagreements(judge_a, judge_b):
    rank = {name: i for i, name in enumerate(judge_a)}
    seq = [rank[name] for name in judge_b]

    def sort_count(xs):
        if len(xs) <= 1:
            return xs, 0
        mid = len(xs) // 2
        left, x = sort_count(xs[:mid])
        right, y = sort_count(xs[mid:])
        merged, i, j, cross = [], 0, 0, 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
                cross += len(left) - i
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged, x + y + cross

    return sort_count(seq)[1]

print(disagreements(["ann", "bo", "cy", "di"], ["bo", "ann", "di", "cy"]))  # 2

문제 2: 아주 긴 계단 오르기

계단 n칸을 한 번에 1칸이나 2칸씩 오릅니다. 꼭대기까지 오르는 방법의 수를 1_000_000_007로 나눈 나머지를 구합니다. n은 10^18까지 커질 수 있습니다.

풀이 방향: ways(n) = ways(n - 1) + ways(n - 2), ways(0) = ways(1) = 1이므로 ways(n)은 피보나치 수 F(n + 1)입니다. 10^18번 도는 반복문은 불가능하지만, 한 단계를 행렬로 쓸 수 있습니다. [[1, 1], [1, 0]]^n = [[F(n+1), F(n)], [F(n), F(n-1)]]이므로 빠른 거듭제곱으로 행렬을 n제곱하면 행렬 곱셈 O(log n)번으로 끝납니다.

MOD = 1_000_000_007

def mat_mult(x, y):
    return [[(x[i][0] * y[0][j] + x[i][1] * y[1][j]) % MOD for j in range(2)]
            for i in range(2)]

def mat_pow(m, e):
    if e == 0:
        return [[1, 0], [0, 1]]
    half = mat_pow(m, e // 2)
    result = mat_mult(half, half)
    return mat_mult(result, m) if e % 2 else result

def stairs(n):
    return mat_pow([[1, 1], [1, 0]], n)[0][0]

print([stairs(n) for n in range(6)])  # [1, 1, 2, 3, 5, 8]
print(stairs(10**18))

문제 3: k번째로 느린 요청

로그에 요청 n개의 응답 시간이 있습니다(같은 값이 많이 반복됩니다). 로그 전체를 정렬하지 않고 k번째로 큰 응답 시간을 구합니다(k = 1이 가장 느린 요청).

풀이 방향: 오름차순 위치 n - k에 대해 퀵셀렉트를 합니다. 같은 값이 많으므로 작은 값, 같은 값, 큰 값의 세 갈래로 나눕니다. 그렇지 않으면 같은 값으로 가득한 로그에서 매 단계 원소가 하나씩만 줄어듭니다.

import random

def kth_largest(values, k):
    target = len(values) - k            # 오름차순 기준 0부터 센 위치
    items = list(values)
    while True:
        pivot = random.choice(items)
        less = [v for v in items if v < pivot]
        equal = [v for v in items if v == pivot]
        greater = [v for v in items if v > pivot]
        if target < len(less):
            items = less
        elif target < len(less) + len(equal):
            return pivot
        else:
            target -= len(less) + len(equal)
            items = greater

times = [120, 85, 300, 85, 95, 300, 40]
print(kth_largest(times, 1), kth_largest(times, 3))  # 300 120

매 단계 평균적으로 일정한 비율의 원소만 남으므로 전체 작업량의 기댓값은 O(n)입니다.

문제 4: 가장 좋은 연속 거래일

하루 단위 손익(음수 포함)이 주어질 때, 비어 있지 않은 연속 구간의 합 중 최댓값을 구합니다.

풀이 방향: 가장 좋은 구간은 왼쪽 절반 안에 있거나, 오른쪽 절반 안에 있거나, 가운데를 가로지릅니다. 가로지르는 경우는 왼쪽 절반의 가장 좋은 접미사와 오른쪽 절반의 가장 좋은 접두사를 더한 값이며, 가운데에서 바깥쪽으로 훑어 O(n)에 구합니다. 따라서 T(n) = 2T(n/2) + O(n) = O(n log n)입니다. 카데인 알고리즘으로는 O(n)에 풀 수 있지만, 분할 정복 풀이는 세그먼트 트리의 바탕이 되는 패턴입니다.

def max_run(a):
    def solve(lo, hi):                  # 닫힌 구간, 비어 있지 않음
        if lo == hi:
            return a[lo]
        mid = (lo + hi) // 2
        best_side = max(solve(lo, mid), solve(mid + 1, hi))
        total, best_left = 0, float("-inf")
        for i in range(mid, lo - 1, -1):
            total += a[i]
            best_left = max(best_left, total)
        total, best_right = 0, float("-inf")
        for i in range(mid + 1, hi + 1):
            total += a[i]
            best_right = max(best_right, total)
        return max(best_side, best_left + best_right)
    return solve(0, len(a) - 1)

print(max_run([3, -4, 5, -1, 2, -6, 4]))  # 6  (5 - 1 + 2)
print(max_run([-3, -1, -2]))              # -1

정리

• 문제 1은 두 순위의 비교를 역순 쌍 세기로 바꿉니다.
• 문제 2는 빠른 거듭제곱을 수 대신 행렬에 적용합니다.
• 문제 3은 같은 값이 퀵셀렉트를 느리게 만들지 않도록 세 갈래로 분할합니다.
• 문제 4는 많은 분할 정복 풀이에 공통인 "가운데를 가로지르는 경우"를 보여 줍니다.