LeetCode 패턴: 두 포인터와 슬라이딩 윈도우 | 템플릿과 C++/Python

작성 0xmote · 2026년 5월 18일 · 60분 읽기 · 수정 2026년 10월 2일 중급 개념

이 글의 핵심

템플릿만 외우면 구현은 빨라지지만 왜 맞는지, 언제 깨지는지를 설명하지 못하면 음수가 섞인 배열 같은 변형 문제에서 막힙니다. 루프 불변식과 교환 논증으로 정확성을 확인하는 방법, 상각 분석, 문제 키워드로 기법을 떠올리는 요령을 C++·Python 코드와 함께 다룹니다.

들어가며

두 포인터와 슬라이딩 윈도우는 배열·문자열 문제에서 자주 등장하는 패턴입니다. 두 포인터는 “구간의 양 끝에서 안쪽으로” 또는 “같은 방향으로 전진”하는 방식으로 O(n) 탐색을 만들고, 슬라이딩 윈도우는 그중 연속 구간의 합·빈도 같은 상태를 유지하며 최적해를 찾는 기법입니다. 이 글에서는 패턴별 템플릿을 먼저 정리한 뒤 LeetCode 3 (Longest Substring Without Repeating Characters), 76 (Minimum Window Substring), 209 (Minimum Size Subarray Sum), 11 (Container With Most Water) 등의 대표 문제에 적용합니다. 같은 로직을 C++와 Python으로 함께 적었고, 각 템플릿이 왜 맞는지와 언제 깨지는지도 설명합니다.

개념 설명

두 포인터 (Two Pointers)

정의: 배열이나 문자열에서 두 개의 인덱스를 사용해 구간을 표현하며, 특정 조건을 만족하는 해를 찾는 기법입니다.

유형 1: 대칭형 (양 끝에서 안쪽으로)

# 정렬된 배열에서 합이 target인 쌍 찾기
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

유형 2: 동시 전진 (같은 방향)

# 중복 제거 (in-place)
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

슬라이딩 윈도우 (Sliding Window)

정의: 두 포인터의 특수한 형태로, 연속 구간(윈도우)을 유지하며 조건을 만족하는 최적해를 찾습니다.

유형 1: 고정 길이 윈도우

# 길이 k 구간의 최대 합
def max_sum_k(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

유형 2: 가변 길이 윈도우

# 합이 target 이상인 최소 길이 구간
def min_subarray_len(target, arr):
    left = 0
    window_sum = 0
    min_len = float('inf')
    
    for right in range(len(arr)):
        window_sum += arr[right]
        while window_sum >= target:
            min_len = min(min_len, right - left + 1)
            window_sum -= arr[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0

이론·복잡도·실무 인식

코딩 테스트용 템플릿만 외우면 구현은 빨라지지만, 왜 맞는지·언제 깨지는지를 말로 설명하지 못하면 면접·설계 리뷰에서 한 단계 밀립니다. 아래는 두 포인터·슬라이딩 윈도우를 증명·불변식·상각 분석·메모리·실무 매핑으로 묶어 정리한 내용입니다.

두 포인터 알고리즘의 정확성(올바름) 논증

두 포인터가 “모든 후보를 빠짐없이 보면서도 중복 탐색을 줄인다”는 주장을, 대표 유형별로 분리해 설명할 수 있어야 합니다.

정렬 배열 Two Sum(양 끝 포인터)
배열이 비감소 순이라면, 고정된 left에 대해 합은 right를 줄일수록 감소합니다. 따라서 arr[left] + arr[right] < target이면, 현재 right가 남은 구간에서 가장 큰 값을 가리키므로 left를 고정한 채로는 어떤 right를 골라도 target에 도달할 수 없습니다. 그래서 left를 증가시키는 쪽으로 탐색 공간을 줄여도 최적해를 놓치지 않습니다. 반대로 합이 target보다 크면 right를 감소시키는 것이 동일한 논리로 정당화됩니다. 이 논리는 단조성(monotonicity)에 기대며, 정렬이 깨지면 성립하지 않습니다.
물 채우기(Container With Most Water)
넓이는 min(h[l], h[r]) * (r - l)입니다. 더 낮은 막대를 안으로 옮기지 않고 높은 막대만 움직이면, 너비는 반드시 줄고 높이 상한은 여전히 낮은 쪽에 묶이므로 개선 가능성이 없습니다. 동률일 때 어느 쪽을 움직여도 “놓치는 최적해”는 없다는 점까지 짚으면 설명이 완결됩니다(동률 케이스는 구현에서 <=로 묶어도 됩니다).
같은 방향 두 포인터(예: 중복 제거)
slow는 유효한 접두의 끝, fast는 스캔 선입니다. 불변식은 “[0..slow]에는 arr[0..fast-1]의 서로 다른 값이 원래 순서대로 한 번씩 들어 있다”입니다. fast가 새 값을 만나면 slow를 한 칸 늘려 그 값을 기록하므로, 각 원소는 최대 한 번만 읽히고 쓰입니다.

결국 증명의 핵심은 탐색 공간을 잘라도 최적해가 남는 이유, 그리고 그 논리가 깨지는 조건(정렬이 깨짐, 음수가 섞인 합 등)을 함께 말하는 것입니다.

슬라이딩 윈도우: 불변식 유지와 복구 순서

슬라이딩 윈도우는 “두 포인터 + 구간 상태”입니다. 구현 실수의 대부분은 불변식의 정의와 right 확장 vs left 축소 순서가 흐릿해서 생깁니다.

불변식 템플릿
윈도우 [left, right]에 대해 목적 조건을 P(window)라 하면, 전형적인 가변 길이 루프는 다음 형태입니다.

right를 한 칸 확장하고 상태를 증분 갱신한다(O(1) 또는 로그).
P가 깨지면(또는 문제가 요구하는 “축소 타이밍”이 오면), left를 당겨 P를 다시 만족시킵니다.
문제 조건에 맞게 답 후보를 갱신한다(최소 길이·최대 길이·합 등).

LeetCode 3(중복 없는 최장 부분 문자열)에서는 P가 “윈도우 내 모든 문자 빈도 ≤ 1”입니다. right에서 문자를 추가해 P가 깨지면, 깨진 문자가 다시 만족할 때까지 left를 이동합니다. 이 순서가 보장하는 것은 항상 P를 만족하는 최대 [left, right] 입니다.

LeetCode 209(합 ≥ target인 최소 길이)에서는 “window_sum ≥ target인 동안 left를 당긴다”는 전략이 각 right에 대해 가능한 가장 짧은 유효 왼쪽 끝을 남깁니다. 반대로 조건을 거꾸로 쓰면(예: >와 ≥ 혼동) 불변식 자체가 바뀌어 다른 문제를 풀게 됩니다.

최소 윈도우(LeetCode 76)는 formed == required일 때 답 후보를 기록한 뒤 left를 당겨 “필요 충족을 유지하는 한 최대한 왼쪽으로” 줄이는 2단계가 핵심입니다. 여기서의 불변식은 “formed가 요구 충족 개수와 일치하는가”이며, left 이동 시 window와 formed를 동시에 되돌려야 합니다.

상각 분석: 왜 ‘이중 while’이 여전히 O(n)인가

겉보기에는 for right 안에 while left가 있어 O(n²)처럼 느껴집니다. 그러나 포인터 이동 횟수로 계산하면 대부분 선형입니다.

기본 논법
left와 right는 각각 0에서 n−1으로만 진행하며 감소하지 않습니다. 따라서 두 포인터의 총 이동 횟수는 각각 최대 n이고, 합은 O(n) 입니다. 내부 while의 반복 횟수를 “전체 알고리즘에 걸쳐 합산”하면, left가 한 칸 움직일 때마다 지불하는 비용으로 보는 상각 분석과도 맞물립니다.

주의할 예외
불변식 복구가 left만이 아니라 재계산·정렬·재스캔을 동반하면 상각이 깨집니다. 예를 들어 매번 윈도우 전체를 순회해 검증하면 구간 길이 합이 O(n²)이 됩니다. 윈도우 상태를 증분 유지할 수 있을 때만 O(n) 주장이 성립합니다.

Deque 기반 최대값(LeetCode 239)에서는 각 인덱스가 deque에 최대 한 번 push, 최대 한 번 pop된다는 불변식으로 전체 O(n)을 설명합니다. 이는 “윈도우 경계가 한 방향으로만 흐른다”는 두 포인터의 상각 논법과 같은 계열입니다.

메모리 접근 패턴과 상수 최적화

빅오가 같아도 캐시 친화성과 자료구조 접근 방식에 따라 실행 시간이 갈립니다.

순차 접근
슬라이딩 윈도우는 보통 배열·문자열을 한 번 순회하므로 공간 지역성이 좋습니다. 포인터 두 개가 앞으로만 움직이면 CPU는 인접 캐시라인을 재사용하기 쉽습니다.

해시맵 vs 고정 배열
알파벳·ASCII 범위가 한정되면 unordered_map/dict 대신 고정 길이 배열이 상수가 작습니다(해시·할당·포인터 따라가기 감소). 본문 고급 활용의 “크기 26/128 배열”이 이 이유입니다.

불필요한 객체 생성
Python에서 슬라이스 s[left:right+1]를 매번 만들면 O(윈도우 길이) 복사가 반복될 수 있습니다. 답이 인덱스·길이로 충분한 문제는 슬라이스 생성을 피하는 편이 안전합니다.

대량 데이터·멀티스레드
실무에서는 배열 원소가 커다란 구조체일 때 거짓 공유(false sharing) 이나 캐시 라인 경합이 병목이 될 수 있습니다. 코테 수준에서는 드물지만, 윈도우 상태를 스레드 간에 공유하는 설계라면 패딩·분리 저장 같은 주제가 함께 나옵니다.

프로덕션에서의 패턴 인식(문제를 코드로 매핑하기)

LeetCode 문장을 넘어, 운영 시스템에서는 같은 수학 구조가 다른 이름으로 등장합니다. 아래 신호가 보이면 “두 포인터·슬라이딩 윈도우 계열”을 의심할 수 있습니다.

신호(요구사항 언어)	추상화	자주 쓰는 자료구조
최근 T초·T분 안의 요청 수, 에러 수	시간축 가변/고정 윈도우	`deque` + 타임스탬프, 원형 버퍼
최대 K회까지 허용, 초과 시 차단	빈도·조건을 유지하는 가변 윈도우	카운터 맵, 비트셋, 고정 배열
롤링 합·롤링 평균·이동 평균	고정 길이 윈도우	누적합 차분, 고정 k 합 갱신
대역폭·레이트 리밋(슬라이딩 윈도우 카운터)	만료 이벤트를 앞에서 제거	큐/데크; 토큰 버킷은 구현은 다르지만 “만료된 사용량 제거” 는 동일
스트림에서 중복 없는 최장 구간	순서 유지 집합/맵 + 좌측 축소	해시맵 + 포인터

안티패턴
윈도우를 옮길 때마다 구간 전체를 다시 순회해 조건을 검사하면, 문제가 커질수록 O(n²) 이상으로 터집니다. 운영 코드에서도 “집계 테이블을 매 요청마다 풀스캔”하는 형태와 같습니다. 상태를 증분 유지할 수 있는지가 첫 설계 질문이 됩니다.

관측 가능성
프로덕션에서는 left/right 대신 시작 타임스탬프·커서·오프셋 이름을 쓰는 경우가 많습니다. 로그로 디버깅할 때는 “윈도우 경계가 단조 증가하는가?”, “만료 제거가 상각 O(1)인가?”를 확인하면, LeetCode에서 연습한 불변식 점검이 그대로 이어집니다.

패턴 인식 가이드

문제 지문에서 “연속 구간”, “부분 배열/부분 문자열”, “최근 T초/최대 K번” 같은 표현이 나오면 슬라이딩 윈도우 후보입니다. 반면 “정렬된 배열에서 합·차·물 채우기”처럼 양 끝의 단조성이 보이면 대칭형 두 포인터를 먼저 떠올립니다. “in-place 병합/제거/파티션”은 같은 방향 두 포인터(느리다/빠르다)가 자연스럽습니다.

키워드 → 의심할 기법

지문 신호	우선 의심	보조 자료구조·주의
연속 구간, 최소/최대 길이, 합/곱/빈도 조건	가변 길이 윈도우	카운터·누적값 증분 갱신
길이 k, k개 평균/합/최대	고정 길이 윈도우	합 차분, deque(최댓값)
부분 문자열이 t와 동일 빈도(아나그램)	고정 길이 + 빈도 비교	크기 26/128 배열
“최대 K번 바꿔서”, “0을 최대 k개 뒤집어”	가변 윈도우 + 예산	위반 시 left 이동, 예산 복구
정렬됨 + 두 수/세 수의 합	대칭형 두 포인터	중복 스킵 루틴
음수 포함 부분합 ≥ target	두 포인터 부적합	누적합 + 단조 덱(LeetCode 862)
윈도우 최솟값/최댓값 매번	deque 단조 큐	인덱스 저장, 만료 pop

판단 순서

입력이 선형(배열·문자열 한 줄)인가? → 두 포인터 후보.
답이 “연속 구간”인가? → 윈도우. 고정 k인지 가변인지 먼저 구분합니다.
윈도우 상태를 O(1)로 유지할 수 있는가? (합, 빈도, 고유 개수, “필요 충족 개수”) → 유지 불가면 다른 알고리즘을 찾습니다.
포인터가 뒤로 가지 않는가? → 상각 O(n) 가능. left가 후퇴하면 전형적인 슬라이딩이 아니라 다른 모델일 수 있습니다.

두 포인터를 쓰면 안 되는 대표 신호

부분합에 음수가 섞여 “한쪽만 줄이면 합이 단조”가 깨지는 경우(예: 임의 부분합 ≥ target).
답이 연속이 아닌 부분수열이거나 재배열 후 매칭인 경우.
윈도우마다 정렬·전수 검사가 필요해 내부가 O(윈도우) 이상인 경우(상각 실패).

이때는 누적합 + 해시맵(합이 정확히 k인 구간 개수), 누적합 + 단조 덱(음수가 섞인 최소 길이 구간), DP 등으로 전환하는 것이 안전합니다.

정확성 증명 기법

앞선 이론 절에서 다룬 단조성·불변식·상각에 더해, 면접·코드 리뷰에서 통하는 서술 템플릿을 정리합니다.

루프 불변식(Invariant) 4줄 템플릿

각 루프 진입 시 다음을 만족한다고 말할 수 있으면 구현이 설명 가능해집니다.

정의: left, right가 의미하는 구간 [left, right]와 상태 변수(합, 카운터)의 의미.
초기화: 시작 시 불변식이 성립하는 이유.
유지: 한 번의 right++ 또는 left++가 상태를 어떻게 갱신하며 불변식을 복구하는지.
종료: 알고리즘이 멈출 때 답이 왜 최적/완전한지.

가변 길이 윈도우에서는 “right 확장 후, 조건 위반 시 left를 최소한으로 전진”이 흔한 유지 단계입니다.

교환 논증(Exchange Argument) — “왜 한쪽만 움직여도 되나”

대칭형 두 포인터(물 채우기, 정렬 Two Sum)는 “최적해를 포함하는 탐색 순서가 있다”는 논리로 설명합니다. 한 단계에서 버리는 후보가 어떤 최적해보다 나을 수 없음을 짧게 보이면, 탐욕적 이동이 안전합니다.

단조성이 깨지면 증명도 깨진다

정렬·비음수 합처럼 한 방향으로만 조정해도 목적 함수가 단조일 때만 “한쪽 포인터만 옮기기” 증명이 성립합니다. 전제를 문제 끝에 한 줄이라도 쓰면 실수가 줄어듭니다.

반례(counterexample)로 설계 검증

증명 대신 작은 입력으로 다음을 빠르게 확인합니다.

left/right 경계: 길이 0·1, 전부 동일, 전부 불가.
고정 윈도우: k = n, k = 1.
가변 윈도우: 조건이 “≥”인지 “>”인지 바꿔 보면 불변식이 어떻게 바뀌는지 드러납니다.

상각이 성립하는 추가 전제

내부 while이 O(n)이라도, 각 인덱스가 덱·맵에서 상수 번 이상 처리된다는 식으로 총 작업량을 bound해야 합니다. “윈도우 전체 재검사”가 끼면 같은 형태의 이중 루프라도 전체 복잡도는 O(n²)일 수 있습니다.

실전 구현

패턴 1: 가변 길이 윈도우 - 중복 없는 가장 긴 부분 문자열

문제: LeetCode 3 - Longest Substring Without Repeating Characters 입력: s = "abcabcbb"
출력: 3 (답: “abc”) 아이디어:

right 포인터로 문자를 추가하며 빈도 카운트
중복 발생 시 left를 이동하며 중복 제거
매 단계마다 최대 길이 갱신

C++ 구현

#include <string>
#include <unordered_map>
#include <algorithm>
class Solution {
public:
    int lengthOfLongestSubstring(const std::string& s) {
        std::unordered_map<char, int> cnt;
        int left = 0, ans = 0;
        
        for (int right = 0; right < (int)s.size(); ++right) {
            cnt[s[right]]++;
            
            while (cnt[s[right]] > 1) {
                cnt[s[left]]--;
                if (cnt[s[left]] == 0) {
                    cnt.erase(s[left]);
                }
                left++;
            }
            
            ans = std::max(ans, right - left + 1);
        }
        
        return ans;
    }
};

Python 구현

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cnt = {}
        left = 0
        ans = 0
        
        for right, ch in enumerate(s):
            cnt[ch] = cnt.get(ch, 0) + 1
            
            while cnt[ch] > 1:
                cnt[s[left]] -= 1
                if cnt[s[left]] == 0:
                    del cnt[s[left]]
                left += 1
            
            ans = max(ans, right - left + 1)
        
        return ans

시간 복잡도: O(n) — left와 right 모두 최대 n번 이동
공간 복잡도: O(min(n, m)) — m은 문자 집합 크기

패턴 2: 최소 윈도우 - Minimum Window Substring

문제: LeetCode 76 - Minimum Window Substring 입력: s = "ADOBECODEBANC", t = "ABC"
출력: "BANC" 아이디어:

t의 문자 빈도를 need에 저장
right로 확장하며 윈도우 빈도 갱신
모든 문자가 만족되면 left를 당기며 최소 길이 갱신

Python 구현

from collections import Counter
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        
        need = Counter(t)
        required = len(need)
        formed = 0
        window = {}
        
        left = 0
        best_len = float("inf")
        best = (0, 0)
        
        for right, c in enumerate(s):
            window[c] = window.get(c, 0) + 1
            
            if c in need and window[c] == need[c]:
                formed += 1
            
            while formed == required and left <= right:
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best = (left, right)
                
                lch = s[left]
                window[lch] -= 1
                if lch in need and window[lch] < need[lch]:
                    formed -= 1
                left += 1
        
        if best_len == float("inf"):
            return ""
        l, r = best
        return s[l : r + 1]

C++ 구현

#include <string>
#include <unordered_map>
#include <climits>
class Solution {
public:
    std::string minWindow(const std::string& s, const std::string& t) {
        if (s.empty() || t.empty()) return "";
        
        std::unordered_map<char, int> need, window;
        for (char c : t) need[c]++;
        
        int required = need.size();
        int formed = 0;
        int left = 0;
        int best_len = INT_MAX;
        int best_left = 0;
        
        for (int right = 0; right < (int)s.size(); ++right) {
            char c = s[right];
            window[c]++;
            
            if (need.count(c) && window[c] == need[c]) {
                formed++;
            }
            
            while (formed == required && left <= right) {
                if (right - left + 1 < best_len) {
                    best_len = right - left + 1;
                    best_left = left;
                }
                
                char lch = s[left];
                window[lch]--;
                if (need.count(lch) && window[lch] < need[lch]) {
                    formed--;
                }
                left++;
            }
        }
        
        return best_len == INT_MAX ? "" : s.substr(best_left, best_len);
    }
};

시간 복잡도: O(n + m) — n은 s 길이, m은 t 길이
공간 복잡도: O(m)

패턴 3: 합 조건 - Minimum Size Subarray Sum

문제: LeetCode 209 - Minimum Size Subarray Sum 입력: target = 7, nums = [2,3,1,2,4,3]
출력: 2 (답: [4,3]) 아이디어:

right로 확장하며 합 증가
합이 target 이상이면 left를 당기며 최소 길이 갱신

Python 구현

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        left = 0
        window_sum = 0
        min_len = float('inf')
        
        for right in range(len(nums)):
            window_sum += nums[right]
            
            while window_sum >= target:
                min_len = min(min_len, right - left + 1)
                window_sum -= nums[left]
                left += 1
        
        return min_len if min_len != float('inf') else 0

C++ 구현

#include <vector>
#include <algorithm>
#include <climits>
class Solution {
public:
    int minSubArrayLen(int target, const std::vector<int>& nums) {
        int left = 0;
        int window_sum = 0;
        int min_len = INT_MAX;
        
        for (int right = 0; right < (int)nums.size(); ++right) {
            window_sum += nums[right];
            
            while (window_sum >= target) {
                min_len = std::min(min_len, right - left + 1);
                window_sum -= nums[left];
                left++;
            }
        }
        
        return min_len == INT_MAX ? 0 : min_len;
    }
};

시간 복잡도: O(n)
공간 복잡도: O(1)

패턴 4: 대칭형 두 포인터 - Container With Most Water

문제: LeetCode 11 - Container With Most Water 입력: height = [1,8,6,2,5,4,8,3,7]
출력: 49 (인덱스 1과 8 사이) 아이디어:

양 끝에서 시작
현재 면적 계산: min(height[left], height[right]) * (right - left)
더 낮은 쪽 포인터를 안으로 이동

Python 구현

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0
        
        while left < right:
            width = right - left
            current_area = min(height[left], height[right]) * width
            max_area = max(max_area, current_area)
            
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return max_area

C++ 구현

#include <vector>
#include <algorithm>
class Solution {
public:
    int maxArea(const std::vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int max_area = 0;
        
        while (left < right) {
            int width = right - left;
            int current_area = std::min(height[left], height[right]) * width;
            max_area = std::max(max_area, current_area);
            
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return max_area;
    }
};

시간 복잡도: O(n)
공간 복잡도: O(1)

패턴 5: 고정 길이 윈도우 - Maximum Average Subarray

문제: LeetCode 643 - Maximum Average Subarray I 입력: nums = [1,12,-5,-6,50,3], k = 4
출력: 12.75 (답: [12,-5,-6,50]) 아이디어:

첫 k개 합 계산
윈도우를 한 칸씩 이동하며 합 갱신

Python 구현

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        window_sum = sum(nums[:k])
        max_sum = window_sum
        
        for i in range(k, len(nums)):
            window_sum += nums[i] - nums[i - k]
            max_sum = max(max_sum, window_sum)
        
        return max_sum / k

C++ 구현

#include <vector>
#include <algorithm>
#include <numeric>
class Solution {
public:
    double findMaxAverage(const std::vector<int>& nums, int k) {
        int window_sum = std::accumulate(nums.begin(), nums.begin() + k, 0);
        int max_sum = window_sum;
        
        for (int i = k; i < (int)nums.size(); ++i) {
            window_sum += nums[i] - nums[i - k];
            max_sum = std::max(max_sum, window_sum);
        }
        
        return static_cast<double>(max_sum) / k;
    }
};

시간 복잡도: O(n)
공간 복잡도: O(1)

패턴 6: 문자 빈도 - Permutation in String

문제: LeetCode 567 - Permutation in String 입력: s1 = "ab", s2 = "eidbaooo"
출력: true (s2에 “ba” 포함) 아이디어:

s1의 문자 빈도 저장
s2에서 길이 len(s1) 윈도우를 슬라이드하며 빈도 비교

Python 구현

from collections import Counter
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        
        need = Counter(s1)
        window = Counter(s2[:len(s1)])
        
        if window == need:
            return True
        
        for i in range(len(s1), len(s2)):
            window[s2[i]] += 1
            
            left_char = s2[i - len(s1)]
            window[left_char] -= 1
            if window[left_char] == 0:
                del window[left_char]
            
            if window == need:
                return True
        
        return False

C++ 구현

#include <string>
#include <unordered_map>
class Solution {
public:
    bool checkInclusion(const std::string& s1, const std::string& s2) {
        if (s1.size() > s2.size()) return false;
        
        std::unordered_map<char, int> need, window;
        for (char c : s1) need[c]++;
        
        for (int i = 0; i < (int)s1.size(); ++i) {
            window[s2[i]]++;
        }
        
        if (window == need) return true;
        
        for (int i = (int)s1.size(); i < (int)s2.size(); ++i) {
            window[s2[i]]++;
            
            char left_char = s2[i - s1.size()];
            window[left_char]--;
            if (window[left_char] == 0) {
                window.erase(left_char);
            }
            
            if (window == need) return true;
        }
        
        return false;
    }
};

시간 복잡도: O(n) — 윈도우 비교는 O(26) = O(1)
공간 복잡도: O(1) — 알파벳 26개

패턴 7: 최대 K개 고유 문자 - Longest Substring with At Most K Distinct

문제: s에서 최대 k개 고유 문자를 포함하는 가장 긴 부분 문자열 입력: s = "eceba", k = 2
출력: 3 (답: “ece”)

Python 구현

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        if k == 0:
            return 0
        
        window = {}
        left = 0
        max_len = 0
        
        for right, ch in enumerate(s):
            window[ch] = window.get(ch, 0) + 1
            
            while len(window) > k:
                left_char = s[left]
                window[left_char] -= 1
                if window[left_char] == 0:
                    del window[left_char]
                left += 1
            
            max_len = max(max_len, right - left + 1)
        
        return max_len

C++ 구현

#include <string>
#include <unordered_map>
#include <algorithm>
class Solution {
public:
    int lengthOfLongestSubstringKDistinct(const std::string& s, int k) {
        if (k == 0) return 0;
        
        std::unordered_map<char, int> window;
        int left = 0;
        int max_len = 0;
        
        for (int right = 0; right < (int)s.size(); ++right) {
            window[s[right]]++;
            
            while ((int)window.size() > k) {
                char left_char = s[left];
                window[left_char]--;
                if (window[left_char] == 0) {
                    window.erase(left_char);
                }
                left++;
            }
            
            max_len = std::max(max_len, right - left + 1);
        }
        
        return max_len;
    }
};

시간 복잡도: O(n)
공간 복잡도: O(k)

패턴 8: 세 수의 합이 0인 조합 — 3Sum

문제: LeetCode 15 - 3Sum
핵심: 배열을 정렬한 뒤, 고정 인덱스 i마다 left=i+1, right=n-1로 정렬 Two Sum을 수행합니다. 중복을 건너뛰려면 nums[i] == nums[i-1] 등으로 같은 값의 재탐색을 막습니다.

Python 구현

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        ans: list[list[int]] = []
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            target = -nums[i]
            left, right = i + 1, n - 1
            while left < right:
                s = nums[left] + nums[right]
                if s == target:
                    ans.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif s < target:
                    left += 1
                else:
                    right -= 1
        return ans

시간 복잡도: O(n²) (정렬 O(n log n) + 이중 루프 상각)
증명 포인트: i를 고정했을 때 나머지 구간이 정렬되어 있으므로 양 끝 포인터의 단조 논법이 그대로 적용됩니다.

패턴 9: 정렬된 두 배열 in-place 병합 — 끝에서 만나는 두 포인터

문제: LeetCode 88 - Merge Sorted Array
핵심: 앞에서부터 채우면 덮어쓰기가 발생하므로, nums1의 끝에서부터 큰 값을 채웁니다. p1, p2, write 세 포인터가 같은 패턴입니다.

Python 구현

class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        p1, p2, w = m - 1, n - 1, m + n - 1
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[w] = nums1[p1]
                p1 -= 1
            else:
                nums1[w] = nums2[p2]
                p2 -= 1
            w -= 1
        while p2 >= 0:
            nums1[w] = nums2[p2]
            p2 -= 1
            w -= 1

불변식: [w+1 .. m+n-1]은 이미 최종 병합의 꼬리이며, 매 단계 가장 큰 원소를 올바른 위치에 놓습니다.

패턴 10: 정렬 배열의 제곱 — 양 끝 비교

문제: LeetCode 977 - Squares of a Sorted Array
핵심: 음수 쪽과 양수 쪽 중 절댓값이 더 큰 쪽부터 결과 배열 끝에 채웁니다.

Python 구현

class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = [0] * n
        left, right = 0, n - 1
        for k in range(n - 1, -1, -1):
            if abs(nums[left]) > abs(nums[right]):
                v = nums[left]
                left += 1
            else:
                v = nums[right]
                right -= 1
            ans[k] = v * v
        return ans

패턴 11: 최대 k번 문자를 바꿔서 — 가변 윈도우 + “예산”

문제: LeetCode 424 - Longest Repeating Character Replacement
핵심: 길이 len 안에서 가장 많이 등장한 문자 수를 maxf라 하면, len - maxf <= k이면 k번 이내로 같은 문자로 맞출 수 있습니다. 조건이 깨지면 left를 당깁니다. 윈도우가 줄어들 때 최빈값이 바뀔 수 있으므로, 아래처럼 max(cnt)로 검증하는 형태가 구현상 안전합니다(알파벳 26개라 매번 max해도 O(n)).

Python 구현

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        cnt = [0] * 26
        left = 0
        best = 0
        for right, ch in enumerate(s):
            cnt[ord(ch) - ord("A")] += 1
            while right - left + 1 - max(cnt) > k:
                cnt[ord(s[left]) - ord("A")] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

시간 복잡도: O(26·n) = O(n). (참고: maxf를 단조 증가로 두는 O(n) 최적화도 있으나, 면접에서는 위 템플릿으로 불변식을 설명하는 편이 낫습니다.)

패턴 12: 최대 두 종류 과일 — 고유 2개 이하 가장 긴 윈도우

문제: LeetCode 904 - Fruit Into Baskets
핵심: 위 패턴 7(최대 K개 고유 문자)과 동일하게 len(window) > 2일 때까지 left를 축소합니다.

Python 구현

class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        from collections import Counter
        window = Counter()
        left = 0
        best = 0
        for right, x in enumerate(fruits):
            window[x] += 1
            while len(window) > 2:
                window[fruits[left]] -= 1
                if window[fruits[left]] == 0:
                    del window[fruits[left]]
                left += 1
            best = max(best, right - left + 1)
        return best

패턴 13: 곱이 k 미만인 부분 배열 개수

문제: LeetCode 713 - Subarray Product Less Than K
핵심: 원소가 양수일 때만 성립합니다. right를 고정하면 조건을 만족하는 left의 구간이 접두 형태라, right마다 right-left+1을 더합니다.

Python 구현

class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        if k <= 1:
            return 0
        prod = 1
        left = 0
        ans = 0
        for right, x in enumerate(nums):
            prod *= x
            while prod >= k:
                prod //= nums[left]
                left += 1
            ans += right - left + 1
        return ans

전제: nums[i] > 0. 0이나 음수가 있으면 곱의 단조성이 깨져 다른 접근이 필요합니다.

패턴 14: s의 아나그램 시작 인덱스 — 고정 길이 + 빈도

문제: LeetCode 438 - Find All Anagrams in a String
핵심: len(p) 윈도우를 밀며 알파벳 빈도가 동일한지 확인합니다. 567번과 같이 전체 Counter 동일 비교 대신 match 카운터로 최적화할 수 있습니다.

Python 구현

class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        if len(p) > len(s):
            return []
        need = [0] * 26
        cur = [0] * 26
        for c in p:
            need[ord(c) - ord("a")] += 1
        k = len(p)
        out: list[int] = []
        for i, c in enumerate(s):
            cur[ord(c) - ord("a")] += 1
            if i >= k:
                cur[ord(s[i - k]) - ord("a")] -= 1
            if i >= k - 1 and cur == need:
                out.append(i - k + 1)
        return out

cur == need는 길이 26이라 O(1)에 가깝습니다. 더 긴 알파벳 집합이면 일치하는 문자 종류 수를 세는 방식으로 바꿉니다.

고급 활용

배열 최적화 (문자 집합이 한정된 경우)

문자 빈도를 추적할 때 해시맵 대신 고정 길이 배열을 씁니다. 소문자 알파벳만 나오면 크기 26, ASCII 전체라면 아래처럼 크기 128이면 충분합니다.

Python 구현

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cnt = [0] * 128  # ASCII
        left = 0
        ans = 0
        
        for right, ch in enumerate(s):
            cnt[ord(ch)] += 1
            
            while cnt[ord(ch)] > 1:
                cnt[ord(s[left])] -= 1
                left += 1
            
            ans = max(ans, right - left + 1)
        
        return ans

해시맵도 평균 O(1)이지만, 배열은 해시 계산과 충돌 처리가 없어 최악에도 O(1)이고 상수도 작습니다. 다만 입력이 유니코드 전체라면 배열 크기가 커지므로 해시맵이 낫습니다.

Deque를 활용한 최대/최소 추적

윈도우가 한 칸 움직일 때마다 윈도우 내 최댓값을 상각 O(1)에 구하는 방법입니다. 문제: LeetCode 239 - Sliding Window Maximum

Python 구현

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        dq = deque()
        result = []
        
        for i, num in enumerate(nums):
            while dq and nums[dq[-1]] < num:
                dq.pop()
            dq.append(i)
            
            if dq[0] <= i - k:
                dq.popleft()
            
            if i >= k - 1:
                result.append(nums[dq[0]])
        
        return result

시간 복잡도: O(n) — 각 원소가 deque에 최대 1번 삽입/삭제
공간 복잡도: O(k)

다중 조건 윈도우

조건이 여러 개여도 각 조건의 상태를 증분으로 유지할 수 있으면 같은 템플릿이 통합니다. 아래는 “모음 최소 a개, 자음 최소 b개를 동시에 포함하는 가장 짧은 구간”을 구합니다. “최소 개수” 조건은 구간이 넓어질수록 만족하기 쉬워지므로, 만족하는 동안 left를 당기며 최솟값을 기록합니다. (같은 조건으로 가장 긴 구간을 구하면 답이 항상 전체 문자열이 되어 윈도우가 필요 없습니다.)

def shortest_with_vowel_consonant(s: str, min_vowels: int, min_consonants: int) -> int:
    vowels = set('aeiouAEIOU')
    left = 0
    vowel_cnt = 0
    consonant_cnt = 0
    min_len = float('inf')
    
    for right, ch in enumerate(s):
        if ch in vowels:
            vowel_cnt += 1
        elif ch.isalpha():
            consonant_cnt += 1
        
        while vowel_cnt >= min_vowels and consonant_cnt >= min_consonants:
            min_len = min(min_len, right - left + 1)
            
            left_char = s[left]
            if left_char in vowels:
                vowel_cnt -= 1
            elif left_char.isalpha():
                consonant_cnt -= 1
            left += 1
    
    return min_len if min_len != float('inf') else 0

성능과 비교

시간 복잡도 비교

접근 방식	시간 복잡도	공간 복잡도	비고
브루트포스 (이중 for)	O(n²)	O(1)	모든 구간 확인
두 포인터	O(n)	O(1)	정렬 필요 시 O(n log n)
슬라이딩 윈도우 + 해시맵	O(n)	O(k)	k는 고유 문자 수
슬라이딩 윈도우 + 배열	O(n)	O(1)	알파벳 한정
Deque 윈도우	O(n)	O(k)	최대/최소 추적

입력이 커질 때 차이가 벌어지는 이유

길이가 100만인 문자열이라면 브루트포스는 시작점과 끝점 쌍을 모두 보므로 비교 횟수가 n²에 비례해 사실상 제한 시간 안에 끝나지 않습니다. 슬라이딩 윈도우는 left와 right가 각각 한 방향으로만 최대 n번 움직이므로 전체 작업이 n에 비례합니다. 같은 O(n)이라도 알파벳 범위가 정해져 있으면 해시맵보다 고정 길이 배열이 빠른데, 해시 계산·버킷 탐색·노드 할당이 없고 26~128칸짜리 배열이 캐시에 통째로 올라가기 때문입니다. 실제 차이는 언어와 입력 분포에 따라 다르니, 제출 전에 최악 입력(모두 다른 문자, 모두 같은 문자)으로 직접 시간을 재 보는 것이 좋습니다.

실무 사례

사례 1: 로그 스트림 - 최근 k분 윈도우 합

실시간 로그에서 최근 5분간 에러 개수를 추적합니다.

Python 구현

from collections import deque
from datetime import datetime, timedelta
class ErrorCounter:
    def __init__(self, window_minutes: int = 5):
        self.window = deque()
        self.window_minutes = window_minutes
    
    def add_error(self, timestamp: datetime):
        self.window.append(timestamp)
        cutoff = timestamp - timedelta(minutes=self.window_minutes)
        
        while self.window and self.window[0] < cutoff:
            self.window.popleft()
    
    def get_count(self) -> int:
        return len(self.window)
# 사용 예시
counter = ErrorCounter(window_minutes=5)
logs = [
    (datetime(2026, 3, 31, 10, 0), "error"),
    (datetime(2026, 3, 31, 10, 2), "error"),
    (datetime(2026, 3, 31, 10, 6), "error"),  # 첫 에러는 윈도우 밖
    (datetime(2026, 3, 31, 10, 7), "error"),
]
for ts, level in logs:
    if level == "error":
        counter.add_error(ts)
        print(f"{ts}: 최근 5분 에러 {counter.get_count()}개")
# 출력:
# 2026-03-31 10:00:00: 최근 5분 에러 1개
# 2026-03-31 10:02:00: 최근 5분 에러 2개
# 2026-03-31 10:06:00: 최근 5분 에러 2개 (10:00 제외)
# 2026-03-31 10:07:00: 최근 5분 에러 3개

시간 복잡도: 각 add_error는 amortized O(1)

사례 2: 네트워크 트래픽 - 대역폭 제한

최근 1초간 전송량이 한도를 넘으면 요청을 거부합니다. 윈도우 안의 합을 매번 sum()으로 다시 계산하면 요청마다 O(윈도우 크기)가 들어 앞에서 말한 안티패턴이 되므로, 합계를 current에 증분으로 유지합니다.

Python 구현

from collections import deque
import time
class BandwidthLimiter:
    def __init__(self, max_bytes: int = 10 * 1024 * 1024, window_sec: float = 1.0):
        self.max_bytes = max_bytes
        self.window_sec = window_sec
        self.requests = deque()  # (timestamp, bytes)
        self.current = 0
    
    def can_send(self, size_bytes: int) -> bool:
        now = time.time()
        cutoff = now - self.window_sec
        
        while self.requests and self.requests[0][0] < cutoff:
            _, old_size = self.requests.popleft()
            self.current -= old_size

        if self.current + size_bytes <= self.max_bytes:
            self.requests.append((now, size_bytes))
            self.current += size_bytes
            return True
        return False
# 사용 예시
limiter = BandwidthLimiter(max_bytes=1000)
requests = [
    (100, "Request 1"),
    (200, "Request 2"),
    (300, "Request 3"),
    (500, "Request 4"),  # 거부됨 (100+200+300+500 > 1000)
]
for size, name in requests:
    if limiter.can_send(size):
        print(f"{name} ({size}B): 허용")
    else:
        print(f"{name} ({size}B): 거부 (대역폭 초과)")

사례 3: 문자열 검색 - Rabin-Karp 알고리즘

고정 길이 윈도우의 해시를 O(1)에 갱신하는 롤링 해시로 패턴 문자열을 찾습니다.

Python 구현

class RabinKarp:
    def __init__(self, base: int = 256, mod: int = 10**9 + 7):
        self.base = base
        self.mod = mod
    
    def search(self, text: str, pattern: str) -> list[int]:
        n, m = len(text), len(pattern)
        if m > n:
            return []
        
        pattern_hash = 0
        window_hash = 0
        base_power = pow(self.base, m - 1, self.mod)
        
        for i in range(m):
            pattern_hash = (pattern_hash * self.base + ord(pattern[i])) % self.mod
            window_hash = (window_hash * self.base + ord(text[i])) % self.mod
        
        result = []
        
        for i in range(n - m + 1):
            if window_hash == pattern_hash:
                if text[i:i + m] == pattern:
                    result.append(i)
            
            if i < n - m:
                window_hash = (window_hash - ord(text[i]) * base_power) % self.mod
                window_hash = (window_hash * self.base + ord(text[i + m])) % self.mod
                window_hash = (window_hash + self.mod) % self.mod
        
        return result
# 사용 예시
rk = RabinKarp()
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
indices = rk.search(text, pattern)
print(f"패턴 발견 위치: {indices}")  # [10]

시간 복잡도: 평균 O(n + m), 최악 O(nm) (해시 충돌)

사례 4: 슬라이딩 윈도우 레이트 리밋(의사코드)

API 게이트웨이에서 “최근 60초 동안 사용자별 요청이 100회 초과 시 429”를 구현할 때, 타임스탬프 큐가 곧 right로 들어오는 이벤트, left로 만료되는 이벤트입니다. 요청마다 타임스탬프를 저장하므로 메모리가 한도(max_requests)에 비례합니다. 메모리를 더 줄이려면 고정 구간별 카운트 두 개를 가중 평균하는 근사 방식(sliding window counter)을 쓰기도 합니다.

from collections import deque

class SlidingWindowRateLimiter:
    def __init__(self, window_sec: float, max_requests: int):
        self.window_sec = window_sec
        self.max_requests = max_requests
        self.events: deque[float] = deque()

    def allow(self, now: float) -> bool:
        cutoff = now - self.window_sec
        while self.events and self.events[0] < cutoff:
            self.events.popleft()
        if len(self.events) < self.max_requests:
            self.events.append(now)
            return True
        return False

left를 당기며 불변식 “윈도우 안 요청 수 ≤ max”를 복구하는 과정은 가변 윈도우와 동일합니다. 토큰 버킷·누출 버킷은 연속 유체 모델이라 구현은 다르지만, “만료분 제거”라는 관점은 공통입니다.

사례 5: 스트림 집계 — 윈도우 경계를 커서로

Flink 같은 스트림 처리 엔진은 left 대신 워터마크(이벤트 시간이 어디까지 진행됐는지 나타내는 값)를 사용합니다. 워터마크가 window_end를 넘으면 그 윈도우를 확정하고 결과를 내보냅니다. 포인터가 시간 순으로만 전진한다는 점에서 슬라이딩 윈도우와 같은 수학 구조입니다.

트러블슈팅

문제 1: while 조건을 헷갈린다

증상:

# 잘못된 예
for right in range(len(arr)):
    window_sum += arr[right]
    while window_sum > target:  # 조건 반대
        # ...

해결:

# 불변식 명시
# 불변식: window_sum >= target일 때 최소 길이 갱신
for right in range(len(arr)):
    window_sum += arr[right]
    
    # 조건 만족 시 left를 당기며 최소 길이 갱신
    while window_sum >= target:
        min_len = min(min_len, right - left + 1)
        window_sum -= arr[left]
        left += 1

불변식을 주석으로 한 줄 적어 두면 >와 >=를 혼동하는 실수를 줄일 수 있습니다.

문제 2: 오프바이원 (Off-by-One)

증상:

# 길이 계산 실수
length = right - left  # 잘못됨

해결:

# [left, right] 구간 길이
length = right - left + 1
# 테스트 케이스
# left=0, right=0 → 길이 1 (맞음)
# left=0, right=2 → 길이 3 (맞음)

문제 3: 시간 초과 (TLE)

증상: 윈도우 내부에서 무거운 연산 반복

# 잘못된 예
for right in range(len(arr)):
    # 매번 윈도우 전체를 순회 → O(n²)
    if is_valid(arr[left:right+1]):
        ans = max(ans, right - left + 1)

해결: 증분 갱신

# 올바른 예
for right in range(len(arr)):
    # O(1) 갱신
    window_state.add(arr[right])
    
    while not window_state.is_valid():
        window_state.remove(arr[left])
        left += 1
    
    ans = max(ans, right - left + 1)

문제 4: 음수 처리

증상: 합이 target 이상인 최소 길이 (음수 포함)

# 두 포인터로 불가능
# 예: nums = [2, -1, 2], target = 3
# left를 당겨도 합이 증가할 수 있음

해결: 음수가 있으면 왼쪽을 당길 때 합이 줄어든다는 전제가 깨집니다. 이 문제는 누적합 배열 위에서 단조 증가 덱을 유지하는 방식(LeetCode 862 Shortest Subarray with Sum at Least K)으로 O(n)에 풉니다. 누적합이 단조가 아니므로 단순 이분 탐색은 그대로 쓸 수 없습니다.

패턴 선택 요약

문제 유형	패턴	예시
정렬 배열에서 합 찾기	대칭형 두 포인터	Two Sum II
중복 제거 (in-place)	동시 전진 두 포인터	Remove Duplicates
고정 길이 구간 최대/평균	고정 윈도우	Maximum Average Subarray
조건 만족 최소/최대 길이	가변 윈도우	Minimum Window Substring
윈도우 내 최대/최소 추적	Deque 윈도우	Sliding Window Maximum
세 수 합 0·병합·제곱 배열	대칭/역방향 두 포인터	3Sum, Merge Sorted Array, Squares
k번 치환·곱·아나그램 슬라이드	가변/고정 + 카운터	424, 713, 438

다음 단계

시간 복잡도 최적화: 시간 복잡도 체크리스트
BFS/DFS 비교: BFS와 DFS 비교
최적화 사례: 알고리즘 최적화 사례 시간 초과가 난다면 내부 연산이 O(1)인지 먼저 확인하세요. 두 포인터는 각 포인터가 선형 이동할 때만 O(n)이 보장됩니다.