LeetCode 패턴: 두 포인터와 슬라이딩 윈도우 | 템플릿과 C++/Python
이 글의 핵심
LeetCode 두 포인터 슬라이딩 윈도우를 구분하고, 고정·가변 길이 윈도우 템플릿으로 대표 문제를 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으로 동일 로직을 옮겨 적는 연습을 합니다
목차
개념 설명
두 포인터 (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: 가변 길이 윈도우 - 중복 없는 가장 긴 부분 문자열
문제: 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)
고급 활용
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) (해시 충돌)
트러블슈팅
문제 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 두 포인터 슬라이딩 윈도우는 템플릿을 외운 뒤 불변식만 문제마다 바꾸는 훈련이 효율적입니다.
패턴 선택 가이드
| 문제 유형 | 패턴 | 예시 |
|---|---|---|
| 정렬 배열에서 합 찾기 | 대칭형 두 포인터 | Two Sum II |
| 중복 제거 (in-place) | 동시 전진 두 포인터 | Remove Duplicates |
| 고정 길이 구간 최대/평균 | 고정 윈도우 | Maximum Average Subarray |
| 조건 만족 최소/최대 길이 | 가변 윈도우 | Minimum Window Substring |
| 윈도우 내 최대/최소 추적 | Deque 윈도우 | Sliding Window Maximum |
다음 단계
- 시간 복잡도 최적화: 시간 복잡도 체크리스트
- BFS/DFS 비교: BFS와 DFS 비교
- 최적화 사례: 알고리즘 최적화 사례
시간 초과가 난다면 내부 연산이 O(1)인지 먼저 확인하세요. 두 포인터는 각 포인터가 선형 이동할 때만 O(n)이 보장됩니다.