D-4: 투 포인터·슬라이딩 윈도우 — O(n²)로 훑던 구간을 O(n)으로

안녕하세요, 여러분의 알고리즘 길잡이 홍순구 튜터입니다. 지난 시간엔 정렬된 배열을 절반씩 버려 O(log n)에 값을 찾는 이진 탐색을 손으로 짰죠. "정렬은 다음 알고리즘의 발판"이라고 했던 말, 기억나시나요? 오늘 그 발판 위에 두 번째 무기를 올립니다.

코딩테스트에서 가장 자주 만나는 벽이 "되긴 되는데 시간 초과"입니다. 특히 "배열 안에서 두 수를 고르거나, 연속한 구간을 훑는" 문제에서 초보자는 거의 반사적으로 이중 반복문을 씁니다. 그런데 이중 반복문은 O(n²)라, 입력이 10만만 돼도 100억 번 연산이라 1초를 훌쩍 넘겨요. 오늘 배우는 세 무기 — 투 포인터, 슬라이딩 윈도우, 누적합 — 는 바로 이 O(n²)를 O(n)으로 끌어내리는 도구들입니다.

 오늘의 여정 — O(n²)로 훑던 구간을 O(n)으로 끌어내리는 세 무기

   투 포인터        두 손가락으로 배열을 훑는다
     │  ├─ 마주 보기 (양 끝 → 안쪽)      두 수의 합 · 세 수의 합
     │  └─ 같은 방향 (나란히 →)          제자리 중복 제거
     ▼
   슬라이딩 윈도우   구간(창문)을 미끄러뜨린다
     │  ├─ 고정 길이 (크기 k 고정)        길이 k 최대 부분합
     │  └─ 가변 길이 (늘였다 줄인다)       최소 길이 · 최장 부분 문자열
     ▼
   누적합           미리 더해 두고 빼서 쓴다
        ├─ 구간 합 O(1)                   prefix[j] - prefix[i]
        └─ 해시와 만나면                   합이 K인 구간 세기

💡 오늘 수업의 핵심 — "두 포인터와 창문, 그리고 미리 더해 둔 합으로, 이중 반복문 O(n²)를 O(n)으로 누른다"

🎯 학습 목표

• 정렬된 배열의 양 끝에서 조여 오는 마주 보는 투 포인터와, 같은 방향으로 나아가는 slow/fast 투 포인터로 구간 문제를 O(n)에 푼다.
• 구간을 미끄러뜨리는 슬라이딩 윈도우를 고정 길이와 가변 길이 두 형태로 구현한다.
• 미리 더해 두는 누적합(prefix sum)으로 구간 합을 O(1)에 구하고, 해시와 결합해 합이 K인 구간을 O(n)에 센다.

Step 1: "양 끝에서 조여 온다" (마주 보는 투 포인터)

가장 유명한 코딩테스트 문제 하나로 시작하죠. "정렬된 정수 배열에서 두 수를 더해 target이 되는 짝을 찾아라." 처음 떠오르는 풀이는 대개 이렇습니다. 모든 두 수의 짝을 다 만들어 보는 거예요.

# 초보자의 첫 풀이 — 모든 짝을 다 만들어 본다
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        if arr[i] + arr[j] == target:
            return (i, j)

정답은 맞습니다. 그런데 반복문이 두 겹이죠. 짝의 개수가 약 n²/2개라 O(n²)입니다. n이 10만이면 50억 번, "1초 ≈ 1억 연산" 잣대로 50초입니다. 시간 초과예요.

여기서 결정적인 힌트가 "정렬돼 있다"는 조건입니다. 정렬된 배열이라면, 두 손가락을 양 끝에 하나씩 두고 안쪽으로 조여 올 수 있어요.

 two_sum_sorted([2, 7, 11, 15], 9)   — 양 끝에서 조여 온다

   index:  0    1    2    3
   값:     2    7    11   15
           lo             hi     2 + 15 = 17 > 9  → 너무 크다, hi를 왼쪽으로
           lo        hi          2 + 11 = 13 > 9  → 아직 크다, hi를 왼쪽으로
           lo   hi               2 +  7 =  9      → 찾았다! (0, 1)

원리는 이렇습니다. 두 끝 값의 합이 target보다 크면, 합을 줄여야 하니 큰 쪽(hi)을 안으로 당깁니다. 합이 target보다 작으면, 합을 키워야 하니 작은 쪽(lo)을 안으로 밀어요. 정렬돼 있으니 이 판단이 항상 옳습니다. 한 번 비교에 lo나 hi가 한 칸씩 확실히 좁혀지니, 최대 n번이면 끝나 O(n)입니다.

# algorithms/two_pointers.py
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        total = arr[lo] + arr[hi]
        if total == target:
            return (lo, hi)
        elif total < target:
            lo += 1
        else:
            hi -= 1
    return None

투 포인터의 힘이 이겁니다. 이진 탐색이 "정렬돼 있으니 절반을 통째로 버린다"였다면, 투 포인터는 "정렬돼 있으니 한쪽 끝을 안심하고 당긴다"예요. 두 기법 모두 정렬이라는 발판 위에서만 성립합니다.

💡 한 줄 정리

정렬된 배열이면 양 끝에 둔 두 포인터를 합의 크기에 따라 안으로 조여, 이중 반복문 O(n²)로 풀던 두 수의 합을 O(n)에 푼다.

Step 2: "정렬이 발판이다" (정렬 + 투 포인터)

지난 시간에 "정렬은 투 포인터의 발판이기도 하다"고 예고했죠. 그 말을 정면으로 회수할 차례입니다. 이번엔 두 수가 아니라 세 수의 합이 0이 되는 조합을 모두 찾아봅시다(유명한 3Sum 문제예요).

세 수를 다 뒤지면 반복문이 세 겹, O(n³)입니다. n이 1000이면 10억 번이라 벌써 아슬아슬해요. 어떻게 줄일까요? 발상은 이렇습니다. 세 수 중 하나를 고정하면, 남은 문제는 "나머지 두 수의 합이 (고정한 수의 부호를 뒤집은 값)이 되는 짝 찾기"입니다. 그건 바로 Step 1에서 푼 두 수의 합이죠!

그런데 두 수의 합을 O(n)에 풀려면 배열이 정렬돼 있어야 합니다. 그래서 맨 앞에서 한 번 정렬(O(n log n))해 두면, 고정한 수의 오른쪽 구간을 마주 보는 투 포인터로 훑을 수 있어요.

 three_sum — 한 수를 고정하고, 나머지 둘을 양 끝에서 조인다

   정렬 후:  -4   -1   -1    0    1    2
             고정  lo ──────────────→ hi        고정 = -1 일 때
                   목표: 나머지 두 수의 합 = +1
                   -1 + 2 = 1  → 찾았다: [-1, -1, 2]
                   0  + 1 = 1  → 찾았다: [-1,  0, 1]

여기서 까다로운 건 중복 제거입니다. 정렬해 두면 같은 값이 이웃하니, 고정한 수와 두 포인터 모두 "직전과 같은 값이면 건너뛴다"로 중복 조합을 걸러낼 수 있어요.

# algorithms/two_pointers.py
def three_sum(nums):
    nums = sorted(nums)
    n = len(nums)
    result = []
    for i in range(n - 2):
        if nums[i] > 0:                       # 가장 작은 수가 이미 양수면 합이 0일 수 없다
            break
        if i > 0 and nums[i] == nums[i - 1]:  # 고정 수 중복 건너뛰기
            continue
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                result.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:   # 두 포인터 중복 건너뛰기
                    lo += 1
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1
    return result

빅오를 정직하게 짚고 갑시다. 바깥 반복문(고정 수)이 O(n)이고, 그 안에서 투 포인터가 O(n)이라 곱하면 O(n²)입니다. 정렬 비용 O(n log n)은 여기 묻히고요. 삼중 반복문 O(n³)를 O(n²)로 내린 거지, O(n)까지 내린 게 아니에요.

여기서 중요한 감각 하나. 투 포인터가 항상 O(n)인 건 아닙니다. 투 포인터는 "한 번 훑기를 O(n)에 한다"는 도구일 뿐이고, 그 훑기를 몇 번 반복하느냐에 따라 전체 복잡도가 정해집니다. Step 1처럼 한 번만 훑으면 O(n), 여기처럼 고정 수마다 훑으면 O(n²)예요.

💡 한 줄 정리

세 수의 합은 한 수를 고정하고 나머지 둘을 마주 보는 투 포인터로 훑어 O(n³)를 O(n²)로 내리며, 이때 정렬이 투 포인터의 발판이자 중복 제거의 근거가 된다.

Step 3: "두 손가락이 같은 쪽으로" (slow/fast 투 포인터)

지금까지 두 포인터는 양 끝에서 마주 봤습니다. 투 포인터엔 또 하나의 형태가 있어요. 두 포인터가 같은 방향으로, 다른 속도로 나아가는 방식입니다. 연결 리스트를 배울 때 사이클을 잡던 "빠른 포인터와 느린 포인터"를 잠깐 언급했었죠? 그 사고를 배열에서 정식으로 봅니다.

문제는 이겁니다. "정렬된 배열에서 중복을 제거하되, 새 배열을 만들지 말고 제자리에서 처리하고 남은 길이를 반환하라." 정렬돼 있으니 같은 값은 서로 이웃해 있어요. 두 포인터 slow와 fast를 이렇게 씁니다.

• slow: 유일한 값들이 채워진 마지막 위치
• fast: 배열을 훑어 나가는 위치

fast가 slow와 다른 값을 만나면, 그건 새로 발견한 유일값이니 slow를 한 칸 늘려 그 값을 옮겨 적습니다. 같은 값이면 그냥 지나쳐요.

 remove_duplicates([0, 0, 1, 1, 1, 2, 2, 3, 3, 4])

   시작:   0  0  1  1  1  2  2  3  3  4
          slow
             fast →                          fast가 slow와 같으면 지나침
                                             다르면 slow++ 후 그 값을 덮어씀
   결과:  [0][1][2][3][4] 1  2  3  3  4       앞쪽 5칸에 유일값이 모임
          └──── 반환값 5 ────┘                arr[:5] = [0, 1, 2, 3, 4]

# algorithms/two_pointers.py
def remove_duplicates(arr):
    if not arr:
        return 0
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1

배열을 딱 한 번 훑으니 O(n) 시간입니다. 그리고 새 배열을 만들지 않고 앞쪽 칸을 덮어쓰니 추가 공간은 O(1)이에요. 만약 새 리스트에 유일값을 담았다면 공간이 O(n)이 됩니다. "제자리에서 처리(in-place)"가 공간을 아끼는 핵심이죠.

이 같은 방향 투 포인터가 중요한 이유가 하나 더 있습니다. 두 포인터가 앞으로만 가고 되돌아오지 않는다는 점, 이게 바로 다음에 배울 슬라이딩 윈도우의 뿌리예요. 창문의 왼쪽과 오른쪽 경계가 곧 두 포인터이고, 둘 다 오른쪽으로만 움직입니다.

💡 한 줄 정리

같은 방향 투 포인터는 slow(채운 끝)와 fast(탐색)를 나란히 오른쪽으로 굴려, 정렬 배열의 중복을 O(n) 시간·O(1) 공간에 제자리 제거하며, 이것이 슬라이딩 윈도우의 뿌리다.

Step 4: "창문을 한 칸씩 민다" (슬라이딩 윈도우 ① 고정 길이)

이제 슬라이딩 윈도우로 넘어갑니다. 지난 시간 예고에서 "창문을 미끄러뜨리듯 구간을 훑는다"고 했던 그 기법이에요. 먼저 창문 크기가 고정된 경우부터 봅시다.

문제는 이렇습니다. "배열에서 연속한 k개의 합 중 최댓값을 구하라." 순진하게 풀면 각 시작 위치마다 k개를 더합니다.

# 순진한 풀이 — 매 구간마다 k개를 새로 더한다
best = max(sum(arr[i:i+k]) for i in range(len(arr) - k + 1))

구간이 약 n개이고 매번 k개를 더하니 O(n·k)입니다. n과 k가 둘 다 크면 시간 초과예요. 낭비가 보이시나요? 창문이 한 칸 오른쪽으로 밀릴 때, 겹치는 k-1개는 이미 더한 값인데 매번 처음부터 다시 더하고 있어요.

슬라이딩 윈도우는 이 겹침을 활용합니다. 창문이 한 칸 밀리면, 빠져나간 값 하나를 빼고 새로 들어온 값 하나를 더하면 끝이에요. 두 번의 연산, O(1)로 다음 창문의 합이 나옵니다.

 max_sum_window([1, 4, 2, 10, 2, 3, 1, 0, 20], k=4)

   [1  4  2 10] 2  3  1  0 20     합 17   (첫 창문 = 앞 4개를 한 번만 더한다)
    1[4  2 10  2]3  1  0 20       합 18 = 17 + 2 - 1     들어온 2, 나간 1
    1  4[2 10  2  3]1  0 20       합 17 = 18 + 3 - 4
    ...
    1  4  2 10  2[3  1  0 20]     합 24 = 6 + 20 - 2     ← 최댓값
                  └ 한 칸 밀 때마다 '들어온 값 - 나간 값'만 갱신 (O(1))

# patterns/sliding_window.py
def max_sum_window(arr, k):
    n = len(arr)
    if k <= 0 or k > n:
        return 0
    window = sum(arr[:k])
    best = window
    for i in range(k, n):
        window += arr[i] - arr[i - k]        # 들어온 값 더하고 나간 값 뺀다 (O(1))
        if window > best:
            best = window
    return best

두 트랙을 짚어 둘게요. 파이썬에서 sum(arr[i:i+k])는 짧고 편합니다. 하지만 슬라이싱은 매번 k개를 다시 더하니 O(k)예요. 창문이 많으면 그 편함이 O(n·k)로 돌아옵니다. 그래서 "빼고 더하는" 갱신을 익혀 두는 거예요. 한 번 첫 창문을 만들 때만 sum을 쓰고, 이후엔 O(1)로 굴립니다.

💡 한 줄 정리

고정 길이 슬라이딩 윈도우는 창문이 한 칸 밀릴 때 나간 값을 빼고 들어온 값만 더해 O(1)로 갱신하니, 매 구간 새로 더하는 O(n·k)를 O(n)으로 내린다.

Step 5: "창문을 늘였다 줄인다" (슬라이딩 윈도우 ② 가변 길이)

고정 창문은 크기 k가 정해져 있었죠. 그런데 "조건을 만족하는 가장 짧은(또는 가장 긴) 구간"을 찾으라면, 창문 크기가 미리 정해지지 않습니다. 이럴 땐 창문을 상황에 따라 늘였다 줄여요. 이게 가변 길이 슬라이딩 윈도우입니다.

첫 문제. "양수 배열에서 합이 target 이상이 되는 가장 짧은 연속 구간의 길이를 구하라." 오른쪽 경계 right를 밀며 창문을 넓히다가, 창문 합이 target 이상이 되는 순간 왼쪽 경계 left를 조여 "조건을 유지하는 최소 길이"를 노립니다.

 min_len_subarray([2, 3, 1, 2, 4, 3], target=7)

   [2 3 1 2]         합 8 ≥ 7  → 길이 4 기록, 왼쪽을 조인다
      [3 1 2]        합 6 < 7  → 오른쪽을 넓힌다
      [3 1 2 4]      합 10 ≥ 7 → 왼쪽을 조인다
        [1 2 4]      합 7 ≥ 7  → 길이 3 기록, 더 조인다
          [2 4]      합 6 < 7  → 오른쪽을 넓힌다
          [2 4 3]    합 9 ≥ 7  → 왼쪽을 조인다
            [4 3]    합 7 ≥ 7  → 길이 2 기록 ← 최소

# patterns/sliding_window.py
def min_len_subarray(arr, target):
    n = len(arr)
    left = 0
    window = 0
    best = n + 1
    for right in range(n):
        window += arr[right]                 # 오른쪽으로 창문을 넓힌다
        while window >= target:              # 조건을 만족하면 왼쪽을 조여 최소 길이를 노린다
            best = min(best, right - left + 1)
            window -= arr[left]
            left += 1
    return best if best <= n else 0

안쪽에 while이 있어서 "이거 이중 반복문 아닌가? O(n²)?" 싶을 수 있어요. 그런데 자세히 보면 left와 right는 각자 오른쪽으로만 가고 절대 되돌아오지 않습니다. 각 원소는 창문에 딱 한 번 들어오고(right가 지날 때) 딱 한 번 나갈(left가 지날 때) 뿐이에요. 그래서 두 포인터가 움직이는 총 횟수가 2n을 넘지 않아 O(n)입니다. Step 3의 "같은 방향, 되돌아오지 않는다"가 여기서 O(n)을 보장해요.

두 번째 문제도 봅시다. "중복 문자가 없는 가장 긴 부분 문자열의 길이"예요. 여기선 창문 안에 어떤 문자가 있는지를 지난 시간의 이웃, 해시(dict)로 기억합니다. 각 문자를 마지막으로 본 위치를 저장해 두고, 창문 안에서 이미 본 문자를 다시 만나면 왼쪽 경계를 그 다음으로 점프시켜요.

# patterns/sliding_window.py
def longest_unique(s):
    last = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1              # 중복을 만나면 창문 왼쪽을 그 다음으로 점프
        last[ch] = right
        best = max(best, right - left + 1)
    return best

last[ch] >= left라는 조건이 함정을 막는 핵심입니다. 이미 창문 밖으로 밀려난 옛 중복은 무시해야 창문을 헛되이 줄이지 않아요. 예를 들어 "abba"에서 마지막 a를 만날 때, 맨 앞의 a는 이미 창문 밖이라 점프하지 않습니다. 이 조건이 없으면 답이 틀어져요.

💡 한 줄 정리

가변 길이 슬라이딩 윈도우는 오른쪽으로 창문을 넓히다 조건을 넘으면 왼쪽을 조이며, 두 포인터가 되돌아오지 않아 이중 while처럼 보여도 O(n)이다.

Step 6: "미리 더해 두면 구간 합이 공짜" (누적합)

투 포인터와 슬라이딩 윈도우는 창문을 "연속으로 밀며" 구간을 훑었죠. 그런데 "임의의 구간 합을 여러 번, 제각각 물어보는" 상황은 어떨까요? "3번부터 7번까지 합", "1번부터 5번까지 합"처럼요. 매번 그 구간을 훑으면 질의 하나에 O(구간 길이)라, 질의가 많으면 느려집니다.

지난 시간 예고에서 "미리 더해 두고 빼서 쓰는 누적합"이라고 했죠. 발상은 단순해요. "앞에서부터 i개를 더한 값"을 미리 전부 계산해 배열로 쌓아 둡니다. 그러면 어떤 구간의 합이든 뺄셈 한 번으로 나와요.

 prefix_sum([1, 2, 3, 4]) = [0, 1, 3, 6, 10]

   arr:          1    2    3    4
   prefix:  0    1    3    6    10       prefix[i] = 앞에서 i개의 합
            │                   │
         0개 합               4개 합

   구간 arr[1:3] 의 합 = prefix[3] - prefix[1] = 6 - 1 = 5   (2 + 3)
                        └ 앞 3개 합에서 앞 1개 합을 빼면 가운데만 남는다

# algorithms/two_pointers.py
def prefix_sum(arr):
    prefix = [0]
    for x in arr:
        prefix.append(prefix[-1] + x)
    return prefix


def range_sum(prefix, i, j):
    return prefix[j] - prefix[i]

prefix[j] - prefix[i]가 왜 arr[i:j]의 합인지 그림으로 보면 명확해요. prefix[j]는 앞에서 j개의 합, prefix[i]는 앞에서 i개의 합이니, 둘을 빼면 i번부터 j-1번까지, 즉 가운데 구간만 남습니다. 맨 앞에 0을 하나 덧대(prefix[0] = 0) 두는 이유가 여기 있어요. "앞에서 0개를 더한 값"이 있어야 맨 앞부터 시작하는 구간도 뺄셈 하나로 깔끔하게 표현됩니다.

빅오를 나눠 봅시다. 누적합 배열을 만드는 준비가 O(n)입니다. 하지만 한 번 만들어 두면 이후 구간 합 질의는 전부 O(1)이에요. 질의가 Q번이면 전체가 O(n + Q)로, 매번 훑는 O(Q·n)과는 비교가 안 됩니다. 실전에선 itertools.accumulate가 같은 일을 하는데, 맨 앞 0만 직접 덧대 주면 돼요.

💡 한 줄 정리

누적합은 "앞에서 i개의 합"을 미리 O(n)에 쌓아 두고, 어떤 구간 합이든 prefix[j] - prefix[i] 뺄셈 한 번 O(1)로 답하니, 구간 합을 여러 번 물을 때 결정적으로 빠르다.

Step 7: "누적합과 해시가 만나면" (구간 합 K 세기 + 유형 분별)

오늘의 마지막이자, 세 무기를 종합하는 Step입니다. 문제는 이거예요. "합이 정확히 K인 연속 부분 배열이 몇 개인지 세라. 단, 배열엔 음수도 있다."

음수가 있다는 단서가 결정적입니다. Step 5에서 봤듯, 음수가 섞이면 슬라이딩 윈도우가 안 통해요. 창문을 넓혀도 합이 줄 수 있어 단조성이 깨지니까요. 그럼 어떻게 할까요? 누적합으로 다시 바라봅니다.

구간 arr[i:j]의 합은 prefix[j] - prefix[i]죠. "합이 K"라는 조건은 곧 prefix[j] - prefix[i] == K, 다시 쓰면 prefix[i] == prefix[j] - K입니다. 즉 각 위치 j에서, "앞선 누적합 중 prefix[j] - K와 같은 값이 몇 번 나왔나"만 세면 돼요. 그 개수를 O(1)에 물으려면? 지난 시간의 이웃, 해시(dict)입니다. 지금까지 본 누적합의 빈도를 dict에 쌓아 두면서 훑어요.

 count_subarrays_with_sum([1, 1, 1], k=2)

   x=1:  running=1   need 1-2=-1  없음(0)        seen={0:1, 1:1}
   x=1:  running=2   need 2-2= 0  seen[0]=1 → +1  seen={0:1, 1:1, 2:1}
   x=1:  running=3   need 3-2= 1  seen[1]=1 → +1  seen={0:1, 1:1, 2:1, 3:1}
                                            합계 2 = [1,1] 두 군데

# algorithms/two_pointers.py
from collections import defaultdict


def count_subarrays_with_sum(arr, k):
    seen = defaultdict(int)
    seen[0] = 1
    running = 0
    count = 0
    for x in arr:
        running += x
        count += seen[running - k]      # 합이 k인 구간의 왼쪽 끝 후보 수
        seen[running] += 1
    return count

seen[0] = 1로 시작하는 이유가 미묘해요. "앞에서부터 통째로" 더한 구간(즉 prefix 자체가 K인 경우)도 세야 하는데, 그러려면 "아무것도 안 더한 상태(prefix[0] = 0)"가 한 번 있었다고 쳐 줘야 합니다. 이 한 줄을 빼면 맨 앞부터 시작하는 구간을 놓쳐요. 빅오는 한 번 훑으니 O(n) 시간, dict에 누적합을 담으니 O(n) 공간입니다.

자, 오늘 배운 세 무기를 언제 꺼낼지 정리하죠. 코딩테스트에서 이 신호들이 보이면 반사적으로 손이 나가야 해요.

💡 한 줄 정리

음수가 섞여 슬라이딩 윈도우가 막히면, 구간 합을 prefix[j] - prefix[i]로 바꿔 "prefix[j] - K가 몇 번 나왔나"를 해시로 O(1)에 물어, 합이 K인 구간을 O(n)에 센다.

마무리

오늘은 정렬이라는 발판 위에, 지난 시간 이진 탐색에 이은 두 번째 무기 묶음을 올렸습니다. 이중 반복문 O(n²)로 훑던 구간 문제들을, 두 포인터와 창문과 미리 더한 합으로 O(n)까지 눌러 봤어요.

오늘 배운 핵심 세 가지

• 💡 하나 — 투 포인터는 두 손가락으로 배열을 훑는다. 정렬된 배열의 양 끝에서 조여 오면(마주 보기) 두 수의 합을 O(n)에, 같은 방향으로 나란히 가면(slow/fast) 제자리 중복 제거를 O(n)·O(1)에 푼다. 정렬이 그 발판이다.
• 💡 둘 — 슬라이딩 윈도우는 창문을 미끄러뜨린다. 고정 길이는 나간 값을 빼고 들어온 값만 더해 O(1)로 갱신하고, 가변 길이는 오른쪽으로 넓히다 조건을 넘으면 왼쪽을 조인다. 두 포인터가 되돌아오지 않아 O(n)이다.
• 💡 셋 — 누적합은 미리 더해 둔다. 앞에서 i개의 합을 쌓아 두면 구간 합이 뺄셈 한 번 O(1)이고, 해시와 만나면 음수가 섞인 배열에서도 합이 K인 구간을 O(n)에 센다.

이걸로 카테고리 D(정렬과 탐색)를 마칩니다. 돌아보면 한 줄기였어요. A-1에서 빅오라는 잣대를 쥐고, B와 C에서 자료구조를 익힌 뒤, D에서 그 위에 정렬(D-1·D-2)을 깔고, 정렬된 배열을 절반씩 버리는 이진 탐색(D-3)과 양 끝에서 조이는 투 포인터(D-4)를 올렸죠. "정렬은 이진 탐색과 투 포인터의 공통 발판"이라는 한마디가 카테고리 D 전체를 꿰뚫습니다.

다음 시간 예고

지금까지는 "영리하게 훑어" O(n)으로 눌렀습니다. 그런데 세상엔 영리한 지름길이 없어 "모든 경우를 다 뒤져야만" 하는 문제들이 있어요. 다음 시간(E-1)엔 그 완전탐색으로 들어갑니다. 완전탐색의 뼈대는 자기 자신을 부르는 재귀예요. 함수가 자기를 부르고 종료 조건에서 되돌아오는 그 호출 스택 그림, 커리큘럼 첫머리에서 봤던 그 그림을 정식으로 펼칩니다. 그리고 가망 없는 가지를 미리 쳐 내는 백트래킹으로, 다 뒤지되 헛일은 줄이는 법까지 나아가요. 오늘 O(n)의 우아함을 봤다면, 다음 시간엔 O(2ⁿ)·O(n!)의 세계와 그걸 다루는 법을 만납니다.

과제

오늘 배운 세 무기를 손에 붙이는 문제들입니다. 코드베이스 algorithms/two_pointers.py와 patterns/sliding_window.py의 함수를 가져다 쓰거나, 직접 짜서 풀어 보세요. 각 문제의 시간·공간 복잡도를 빅오로 함께 적는 걸 잊지 마세요.

[기초] 회문(팰린드롬) 검사하기

문자열 s가 앞으로 읽으나 뒤로 읽으나 같은지(회문인지) True/False로 반환하는 is_palindrome(s)를 마주 보는 투 포인터로 작성하세요. 예를 들어 is_palindrome("level")은 True, is_palindrome("hello")는 False, is_palindrome("")은 True입니다.

• 양 끝에 포인터를 두고 안쪽으로 조여 오는 Step 1의 형태 그대로입니다. 두 포인터가 가리키는 문자가 다르면 그 자리에서 회문이 아니에요.
• 뒤집은 문자열과 비교하는 s == s[::-1]도 답은 같지만 공간 O(n)을 씁니다. 투 포인터로 짜면 공간 O(1)인 이유를 한 줄로 설명하세요.

[응용] 합이 정확히 target인 연속 구간 찾기

양수로만 이루어진 배열 arr와 값 target이 주어질 때, 합이 정확히 target인 연속 부분 배열이 있으면 그 (시작 인덱스, 끝 인덱스)를, 없으면 None을 반환하는 subarray_sum_positive(arr, target)을 가변 슬라이딩 윈도우로 작성하세요. 끝 인덱스는 포함입니다. 예를 들어 arr = [1, 2, 3, 7, 5]에서 subarray_sum_positive(arr, 12)는 (1, 3)(2+3+7), subarray_sum_positive(arr, 100)은 None입니다.

• Step 5의 가변 창문을 응용합니다. 합이 target보다 작으면 오른쪽을 넓히고, 크면 왼쪽을 조이고, 정확히 같으면 찾은 거예요.
• 왜 이 문제는 양수 배열에서만 슬라이딩 윈도우가 성립하는지, Step 5·7의 단조성 이야기로 설명하세요.

[심화] 0과 1의 개수가 같은 최장 구간

0과 1로만 이루어진 배열 arr에서, 0의 개수와 1의 개수가 같은 가장 긴 연속 부분 배열의 길이를 반환하는 longest_equal_binary(arr)를 누적합과 해시로 작성하세요. 예를 들어 longest_equal_binary([0, 1, 0])은 2(앞의 [0, 1]), longest_equal_binary([0, 1, 1, 0, 1, 1, 1, 0])은 4입니다.

• 0을 -1로 바꿔서 생각해 보세요. 그러면 "0과 1의 개수가 같다"가 "그 구간의 합이 0"으로 바뀝니다. Step 7에서 본 "구간 합 = 누적합의 차"가 곧장 쓰여요.
• 누적합이 같은 두 위치 사이는 합이 0인 구간입니다. 각 누적합 값이 "처음 나온 위치"를 해시에 저장해 두면, 같은 값을 다시 만났을 때 그 사이 길이가 후보가 돼요. 왜 "처음 나온 위치"만 저장하면 최장이 보장되는지 생각해 보세요.

생각해볼 주제

1. 투 포인터는 왜 정렬을 발판으로 삼을까, 정렬이 없으면 무엇이 무너지나

마주 보는 투 포인터는 "합이 크면 오른쪽을 당기고, 작으면 왼쪽을 민다"는 판단으로 한쪽을 통째로 버립니다. 이 판단이 옳으려면 배열이 정렬돼 있어야 해요. 정렬을 지우면 이 버리기가 왜 성립하지 않는지, 그리고 이게 지난 시간 이진 탐색이 정렬을 전제하던 이유와 어떻게 같은 뿌리인지 이어서 생각해 보세요. "한쪽을 버려도 그 안에 답이 없다는 보장"이라는 표현이 힌트입니다.

2. 슬라이딩 윈도우가 통하는 문제와 안 통하는 문제의 경계는 어디일까

Step 5의 최소 길이 구간은 슬라이딩 윈도우로 풀렸지만(양수 배열), Step 7의 합이 K인 구간 세기는 누적합+해시로 풀었습니다(음수 포함). 무엇이 이 둘을 갈랐을까요? "창문을 넓히면 합이 반드시 커진다"는 단조성이 언제 성립하고 언제 깨지는지, 그리고 단조성이 깨진 문제를 만났을 때 창문 대신 무엇을 꺼내야 하는지 정리해 보세요. 이 경계를 아는 게 유형을 잘못 골라 헤매는 걸 막아 줍니다.

3. "미리 계산해 두기"의 트레이드오프 — 누적합은 언제 이득이고 언제 낭비일까

누적합은 O(n)을 들여 미리 배열을 만들어 두고, 이후 구간 합 질의를 O(1)에 답합니다. 그런데 구간 합을 딱 한 번만 물어볼 거라면 어떨까요? 미리 만드는 O(n)이 아까울 수 있어요. 질의 횟수를 기준으로 "미리 계산해 두는 전처리"가 언제 이득이고 언제 낭비인지 따져 보세요. 이건 지난 시간 "정렬 후 이진 탐색이 언제 이득인가"와 정확히 같은 결의 사고입니다. 전처리 비용을 몇 번의 질의로 나눠 갚는지가 판단의 핵심이에요.