코딩테스트 최적화 기법 (Optimization Techniques)

이중 반복문을 한 번의 순회로 — 투 포인터와 슬라이딩 윈도우

"모든 구간을 다 확인한다"는 발상은 O(n²)이다. 그런데 구간을 조금씩 옮길 때 이전 계산 결과를 재활용할 수 있다면 전체를 한 번 순회하는 것으로 끝난다.

슬라이딩 윈도우는 길이가 고정된 구간을 옮기는 경우다. 구간을 한 칸 밀 때 매번 전부 더할 필요 없이, 빠지는 값을 빼고 들어오는 값을 더하면 된다. 구간 길이가 얼마든 연산 두 번이다.

def max_window_sum(arr, k):
    """길이 k인 연속 구간의 최대 합."""
    window = sum(arr[:k])              # 첫 윈도우만 직접 더한다
    best = window

    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # 들어오는 값 더하고 빠지는 값 뺀다
        best = max(best, window)

    return best

투 포인터는 구간의 길이가 고정되지 않은 경우다. 조건에 따라 왼쪽이나 오른쪽 포인터를 옮기는데, 두 포인터가 모두 뒤로만 가므로 전체 이동 횟수가 2n을 넘지 않는다. 그래서 O(n)이다.

def two_sum_sorted(arr, target):
    """정렬된 배열에서 합이 target인 두 수를 찾는다."""
    l, r = 0, len(arr) - 1

    while l < r:
        s = arr[l] + arr[r]
        if s == target:
            return arr[l], arr[r]
        if s < target:
            l += 1                     # 합을 키워야 하니 왼쪽을 올린다
        else:
            r -= 1                     # 합을 줄여야 하니 오른쪽을 내린다

    return None


def min_length_subarray(arr, target):
    """합이 target 이상인 가장 짧은 연속 구간의 길이. 길이가 가변인 투 포인터."""
    l, total, best = 0, 0, float('inf')

    for r, x in enumerate(arr):
        total += x
        while total >= target:         # 조건을 만족하는 동안 왼쪽을 좁힌다
            best = min(best, r - l + 1)
            total -= arr[l]
            l += 1

    return best if best != float('inf') else 0

두 번째 예시의 while이 안쪽에 있어 O(n²)처럼 보이지만 아니다. l은 전체를 통틀어 최대 n번만 증가하므로 안쪽 반복의 총 실행 횟수도 n번이다. 이렇게 중첩 반복문의 총 실행 횟수를 따로 세는 감각이 투 포인터를 이해하는 열쇠다.

투 포인터를 쓰려면 조건이 단조적이어야 한다. "왼쪽을 옮기면 값이 반드시 줄고, 오른쪽을 옮기면 반드시 는다"는 성질이 없으면 포인터를 되돌려야 해서 성립하지 않는다. 음수가 섞인 배열에서 위 코드가 깨지는 이유가 이것이다.

반복문 안에서 하지 말아야 할 것들

# 매번 정렬한다
for q in queries:
    arr.sort()                # 루프 밖으로 빼면 한 번이면 된다

# 매번 len()을 부른다 (사소하지만 큰 루프에서는 쌓인다)
for i in range(len(arr)):
    for j in range(len(arr)):
        ...
n = len(arr)                  # 미리 꺼내둔다

# 매번 리스트를 새로 만든다
for x in data:
    temp = list(big_list)     # 복사가 O(n)

# 전역 변수를 반복 참조한다 — 지역 변수가 더 빠르다
def solve():
    local_fn = some_function  # 자주 부르는 함수는 지역에 묶어둔다
    for x in data:
        local_fn(x)

알아두면 좋은 표준 라이브러리

내장 함수와 라이브러리는 C로 구현되어 있어서, 같은 일을 하는 파이썬 반복문보다 훨씬 빠르다. sum(arr)이 직접 더하는 반복문보다 빠른 이유다. 직접 구현할 이유가 없다면 라이브러리를 쓴다.

자주 하는 실수

• 알고리즘이 틀렸는데 상수 최적화로 해결하려 한다. O(n²)을 아무리 다듬어도 n이 10만이면 통과하지 못한다. 시간 초과가 나면 먼저 복잡도가 맞는지 확인하고, 맞다면 그때 이 글의 기법들을 적용한다.
• 리스트에 in을 쓴다. 가장 흔한 숨은 O(n²)이다. 포함 확인이 목적이면 무조건 set이다.
• list.pop(0)을 쓴다. BFS에서 이것 하나로 시간 초과가 난다. deque를 쓴다.
• 반복문 안에서 문자열을 더한다. 출력이 많은 문제에서 특히 치명적이다.
• input()을 그대로 쓴다. 입력 줄이 많으면 sys.stdin.readline으로 바꾼다.
• 누적합 배열의 인덱스를 헷갈린다. 맨 앞에 0을 넣지 않으면 l = 0일 때 예외 처리가 필요해지고, 거기서 실수가 난다.
• 재귀 한도를 안 올린다. DFS나 DP 재귀에서 sys.setrecursionlimit(10**6)은 습관적으로 넣어두는 편이 좋다.

면접에서 이렇게 물어본다

• 파이썬에서 리스트와 셋의 포함 확인 복잡도가 다른 이유는 무엇인가.
• list.pop(0)이 O(n)인 이유와 대안을 설명해 보라.
• 반복문에서 문자열을 +=로 이어붙이면 왜 느린가.
• 누적합이 어떤 문제를 어떻게 개선하는지 설명해 보라.
• n의 크기를 보고 알고리즘을 고르는 기준을 말해 보라.
• 시간 초과가 났을 때 어떤 순서로 원인을 찾겠는가.