LeetCode 패턴: 두 포인터와 슬라이딩 윈도우 | 템플릿과 C++/Python
이 글의 핵심
LeetCode 두 포인터·슬라이딩 윈도우 패턴, 고정·가변 윈도우 템플릿, 패턴 인식 체크리스트·증명 기법(불변식·교환 논증)·추가 예제(3Sum, 치환 k회, 곱·아나그램 등)·실무 매핑까지 C++/Python 예제와 함께 정리합니다.
들어가며
LeetCode 두 포인터 슬라이딩 윈도우는 배열·문자열 문제에서 가장 자주 등장하는 패턴입니다. 두 포인터는 “구간의 양 끝” 또는 “같은 방향으로 전진”으로 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에 옮겨 적어 면접·시험에서 바로 꺼내 쓸 수 있게 했습니다.
이 글을 읽으면
- 두 포인터(대칭·동시 전진)와 슬라이딩 윈도우의 경계를 구분합니다
- 고정 길이 vs 가변 길이 윈도우 템플릿을 바로 꺼내 씁니다
- 지문 키워드로 패턴을 고르는 패턴 인식 가이드와 증명 기법을 적용합니다
- 정확성 논증·불변식·상각 분석·캐시 관점까지 연결해 설명할 수 있습니다
- C++와 Python으로 동일 로직을 옮겨 적는 연습을 합니다
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
개념 설명
두 포인터 (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이론·복잡도·실무 인식
코딩 테스트용 템플릿만 외우면 구현은 빨라지지만, 왜 맞는지·언제 깨지는지를 말로 설명하지 못하면 면접·설계 리뷰에서 한 단계 밀립니다. 아래는 두 포인터·슬라이딩 윈도우를 증명·불변식·상각 분석·메모리·실무 매핑으로 묶어 정리한 내용입니다.
두 포인터 알고리즘의 정확성(올바름) 논증
두 포인터가 “모든 후보를 빠짐없이 보면서도 중복 탐색을 줄인다”는 주장을, 대표 유형별로 분리해 설명할 수 있어야 합니다.
1) 정렬 배열 Two Sum(양 끝 포인터)
배열이 비감소 순이라면, 고정된 left에 대해 합은 right를 줄일수록 감소합니다. 따라서 arr[left] + arr[right] < target이면 left를 고정한 채 더 작은 합을 만들 수 있는 인덱스 쌍은 존재하지 않습니다. 그래서 left를 증가시키는 쪽으로 탐색 공간을 줄여도 최적해를 놓치지 않습니다. 반대로 합이 target보다 크면 right를 감소시키는 것이 동일한 논리로 정당화됩니다. 이 논리는 단조성(monotonicity)에 기대며, 정렬이 깨지면 성립하지 않습니다.
2) 물 채우기(Container With Most Water)
넓이는 min(h[l], h[r]) * (r - l)입니다. 더 낮은 막대를 안쪽으로 옮기지 않고 높은 막대만 움직이면, 너비는 반드시 줄고 높이 상한은 여전히 낮은 쪽에 묶이므로 개선 가능성이 없습니다. 동률일 때 어느 쪽을 움직여도 “놓치는 최적해”는 없다는 점까지 짚으면 설명이 완결됩니다(동률 케이스는 구현에서 <=로 묶어도 됩니다).
3) 같은 방향 두 포인터(예: 중복 제거)
slow는 유효한 접두의 끝, fast는 스캔 선입니다. 불변식은 “[0..slow]는 이미 목적 조건을 만족하는 최소 길이 접두”입니다. fast가 전진하며 위반을 발견하면 slow를 조정해 접두를 복구하므로, 각 원소는 상수 번만 기록됩니다.
요약하면, 증명의 핵심은 (i) 탐색 공간을 잘라도 최적해가 남는 이유와 (ii) 잘못 잘라면 반례가 되는 조건(정렬 깨짐, 음수 합 등) 입니다.
슬라이딩 윈도우: 불변식 유지와 복구 순서
슬라이딩 윈도우는 “두 포인터 + 구간 상태”입니다. 구현 실수의 대부분은 불변식의 정의와 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 | 두 포인터 부적합 가능 | 누적합 + 이분 탐색·세그트리 등 |
| 윈도우 최솟값/최댓값 매번 | deque 단조 큐 | 인덱스 저장, 만료 pop |
의사결정 체크리스트(짧게)
- 입력이 선형(배열·문자열 한 줄)인가? → 두 포인터 후보.
- 답이 “연속 구간”인가? → 윈도우. 고정 k인지 가변인지 먼저 구분합니다.
- 윈도우 상태를 O(1)로 유지할 수 있는가? (합, 빈도, 고유 개수, “필요 충족 개수”) → 유지 불가면 다른 알고리즘을 찾습니다.
- 포인터가 뒤로 가지 않는가? → 상각 O(n) 가능. left가 후퇴하면 전형적인 슬라이딩이 아니라 다른 모델일 수 있습니다.
두 포인터를 쓰면 안 되는 대표 신호
- 부분합에 음수가 섞여 “한쪽만 줄이면 합이 단조”가 깨지는 경우(예: 임의 부분합 ≥ target).
- 답이 연속이 아닌 부분수열이거나 재배열 후 매칭인 경우.
- 윈도우마다 정렬·전수 검사가 필요해 내부가 O(윈도우) 이상인 경우(상각 실패).
이때는 누적합 + 해시맵, 이분 탐색, DP, 세그먼트 트리 등으로 전환하는 것이 안전합니다.
정확성 증명 기법
앞선 이론 절에서 다룬 단조성·불변식·상각에 더해, 면접·코드 리뷰에서 통하는 서술 템플릿을 정리합니다.
1) 루프 불변식(Invariant) 4줄 템플릿
각 루프 진입 시 다음을 만족한다고 말할 수 있으면 구현이 설명 가능해집니다.
- 정의:
left,right가 의미하는 구간[left, right]와 상태 변수(합, 카운터)의 의미. - 초기화: 시작 시 불변식이 성립하는 이유.
- 유지: 한 번의
right++또는left++가 상태를 어떻게 갱신하며 불변식을 복구하는지. - 종료: 알고리즘이 멈출 때 답이 왜 최적/완전한지.
가변 길이 윈도우에서는 “right 확장 후, 조건 위반 시 left를 최소한으로 전진”이 흔한 유지 단계입니다.
2) 교환 논증(Exchange Argument) — “왜 한쪽만 움직여도 되나”
대칭형 두 포인터(물 채우기, 정렬 Two Sum)는 “최적해를 포함하는 탐색 순서가 있다”는 논리로 설명합니다. 한 단계에서 버리는 후보가 어떤 최적해보다 나을 수 없음을 짧게 보이면, 탐욕적 이동이 안전합니다.
3) 단조성이 깨지면 증명도 깨진다
정렬·비음수 합처럼 한 방향으로만 조정해도 목적 함수가 단조일 때만 “한쪽 포인터만 옮기기” 증명이 성립합니다. 전제를 문제 끝에 한 줄이라도 쓰면 실수가 줄어듭니다.
4) 반례(counterexample)로 설계 검증
증명 대신 작은 입력으로 다음을 빠르게 확인합니다.
left/right경계: 길이 0·1, 전부 동일, 전부 불가.- 고정 윈도우:
k = n,k = 1. - 가변 윈도우: 조건이 “≥”인지 “>”인지 바꿔 보면 불변식이 어떻게 바뀌는지 드러납니다.
5) 상각이 성립하는 추가 전제
내부 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 0C++ 구현
#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_areaC++ 구현
#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 / kC++ 구현
#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 FalseC++ 구현
#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_lenC++ 구현
#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)에 가깝습니다. 더 긴 알파벳 집합이면 일치하는 문자 종류 수를 세는 방식으로 바꿉니다.
고급 활용
1) 배열 최적화 (소문자 알파벳 한정)
시나리오: 문자 빈도를 추적할 때 해시맵 대신 크기 26 배열 사용
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) 보장)
- 메모리 효율적
2) 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)
3) 다중 조건 윈도우
시나리오: 모음과 자음 개수 조건을 동시에 만족
def longest_with_vowel_consonant(s: str, min_vowels: int, min_consonants: int) -> int:
vowels = set('aeiouAEIOU')
left = 0
vowel_cnt = 0
consonant_cnt = 0
max_len = 0
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:
max_len = max(max_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 max_len성능과 비교
시간 복잡도 비교
| 접근 방식 | 시간 복잡도 | 공간 복잡도 | 비고 |
|---|---|---|---|
| 브루트포스 (이중 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) | 최대/최소 추적 |
벤치마크 예시
테스트: s = "abcabcbb" (길이 100만)
| 방법 | 실행 시간 | 메모리 |
|---|---|---|
| 브루트포스 | 45s | 1MB |
| 슬라이딩 윈도우 (해시맵) | 120ms | 5MB |
| 슬라이딩 윈도우 (배열) | 80ms | 1MB |
| 결론: 슬라이딩 윈도우로 375배 개선 |
실무 사례
사례 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초간 전송량이 10MB 초과 시 요청 거부
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)
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:
self.requests.popleft()
current_usage = sum(size for _, size in self.requests)
if current_usage + size_bytes <= self.max_bytes:
self.requests.append((now, 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 알고리즘
시나리오: 패턴 문자열을 텍스트에서 찾기 (해시 활용)
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로 만료되는 이벤트입니다. 메모리를 줄이려면 카운트만 유지하고 경계에서 빼지만, 감사를 위해 (ts, id)를 남기기도 합니다.
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 FalseLeetCode와의 대응: left를 당기며 불변식 “윈도우 안 요청 수 ≤ max”를 복구하는 과정은 가변 윈도우와 동일합니다. 토큰 버킷·누출 버킷은 연속 유체 모델이라 구현은 다르지만, “만료분 제거”라는 관점은 공통입니다.
사례 5: 스트림 집계 — 윈도우 경계를 커서로
Kafka·Flink 등에서 윈도우 시작 오프셋을 커밋하면, 재처리 시에도 동일한 경계를 재현할 수 있습니다. 코드에서는 left 대신 watermark(이벤트 시간) 가 window_end를 넘길 때만 상태를 flush하는 식으로 표현합니다. 포인터가 시간 순으로만 전진한다는 점에서 슬라이딩 윈도우와 같은 수학 구조입니다.
사례 6: 운영 체크리스트(프로덕션)
| 점검 항목 | 질문 | 패턴 연결 |
|---|---|---|
| 경계 단조성 | 타임스탬프가 역행하면 큐가 깨지지 않는가? | 포인터 후퇴 방지 |
| 만료 비용 | 매 요청마다 전체 스캔하는가? | 앞쪽 popleft 상각 |
| 동시성 | 같은 키에 락/샤딩이 있는가? | 단일 스레드 deque와 동일 논리 |
| 메모리 | 윈도우가 무한히 커지지 않는가? | 최악 길이 = 초당 이벤트 × window |
트러블슈팅
문제 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를 당겨도 합이 증가할 수 있음해결: 음수가 있으면 두 포인터 불가 → DP 또는 Prefix Sum + 이분 탐색
마무리
LeetCode 두 포인터 슬라이딩 윈도우는 템플릿을 외운 뒤 불변식만 문제마다 바꾸는 훈련이 효율적입니다. 이번에 보강한 패턴 인식 가이드·정확성 증명 기법은 “무슨 템플릿을 꺼낼지”와 “왜 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)이 보장됩니다.
심화 부록: 구현·운영 관점
이 부록은 앞선 본문에서 다룬 주제(「LeetCode 패턴: 두 포인터와 슬라이딩 윈도우 | 템플릿과 C++/Python」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.
내부 동작과 핵심 메커니즘
flowchart TD A[입력·요청·이벤트] --> B[파싱·검증·디코딩] B --> C[핵심 연산·상태 전이] C --> D[부작용: I/O·네트워크·동시성] D --> E[결과·관측·저장]
sequenceDiagram participant C as 클라이언트/호출자 participant B as 경계(런타임·게이트웨이·프로세스) participant D as 의존성(API·DB·큐·파일) C->>B: 요청/이벤트 B->>D: 조회·쓰기·RPC D-->>B: 지연·부분 실패·재시도 가능 B-->>C: 응답 또는 오류(코드·상관 ID)
- 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
- 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
- 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
- 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.
프로덕션 운영 패턴
| 영역 | 운영 관점 질문 |
|---|---|
| 관측성 | 요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가 |
| 안전성 | 입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가 |
| 신뢰성 | 재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가 |
| 성능 | 캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가 |
| 배포 | 롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가 |
| 용량 | 피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가 |
스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.
확장 예시: 엔드투엔드 미니 시나리오
앞선 본문 주제(「LeetCode 패턴: 두 포인터와 슬라이딩 윈도우 | 템플릿과 C++/Python」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.
- 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
- 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
- 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
- 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
- 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.
handle(request):
ctx = newCorrelationId()
validated = validateSchema(request)
authorize(validated, ctx)
result = domainCore(validated)
persistOrEmit(result, idempotentKey)
recordMetrics(ctx, latency, outcome)
return result문제 해결(Troubleshooting)
| 증상 | 가능 원인 | 조치 |
|---|---|---|
| 간헐적 실패 | 레이스, 타임아웃, 외부 의존성, DNS | 최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검 |
| 성능 저하 | N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스 | 프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거 |
| 메모리 증가 | 캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납 | 상한·TTL·힙/FD 스냅샷 비교 |
| 빌드·배포만 실패 | 환경 변수, 권한, 플랫폼 차이, lockfile | CI 로그와 로컬 diff, 런타임·이미지 버전 핀 |
| 설정 불일치 | 프로필·시크릿·기본값, 리전 | 스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화 |
| 데이터 불일치 | 비멱등 재시도, 부분 쓰기, 캐시 무효화 누락 | 멱등 키·아웃박스·트랜잭션 경계 재검토 |
권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.
배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. LeetCode 두 포인터·슬라이딩 윈도우 패턴의 차이, 고정·가변 윈도우 템플릿과 대표 문제 풀이를 C++와 Python으로 정리합니다. 실전 예제와 코드로 개념부터 활용까지 정리합니다. 알고리즘·LeetCode·… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- 슬라이딩 윈도우 | 부분 배열 최적화 기법 완벽 정리
- 코딩 테스트 완벽 대비 가이드 | 알고리즘부터 실전 팁까지
- 백트래킹 | 모든 경우의 수 탐색 알고리즘 완벽 정리
이 글에서 다루는 키워드 (관련 검색어)
알고리즘, LeetCode, 두 포인터, 슬라이딩 윈도우, 코딩 테스트, 패턴 등으로 검색하시면 이 글이 도움이 됩니다.