[2026] LeetCode 패턴: 두 포인터와 슬라이딩 윈도우 | 템플릿과 C++/Python
![[2026] LeetCode 패턴: 두 포인터와 슬라이딩 윈도우 | 템플릿과 C++/Python](/og/s/algorithm-leetcode-two-pointers-sliding-window.webp)
이 글의 핵심
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으로 동일 로직을 옮겨 적는 연습을 합니다
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
목차
개념 설명
두 포인터 (Two Pointers)
정의: 배열이나 문자열에서 두 개의 인덱스를 사용해 구간을 표현하고, 특정 조건을 만족하는 해를 찾는 기법입니다.
유형 1: 대칭형 (양 끝에서 안쪽으로)
아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 정렬된 배열에서 합이 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: 동시 전진 (같은 방향)
아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 중복 제거 (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: 고정 길이 윈도우
아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
# 길이 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: 가변 길이 윈도우
아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 합이 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++ 구현
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 구현
다음은 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 구현
다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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++ 구현
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 구현
다음은 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++ 구현
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 구현
다음은 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++ 구현
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 구현
아래 코드는 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++ 구현
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 구현
다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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++ 구현
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 구현
다음은 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++ 구현
다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
#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 구현
다음은 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 구현
다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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) 다중 조건 윈도우
시나리오: 모음과 자음 개수 조건을 동시에 만족 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 구현
다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 구현
다음은 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 조건을 헷갈린다
증상: 아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
# 잘못된 예
for right in range(len(arr)):
window_sum += arr[right]
while window_sum > target: # 조건 반대
# ...해결: 아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 불변식 명시
# 불변식: 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 # 잘못됨해결: 아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
# [left, right] 구간 길이
length = right - left + 1
# 테스트 케이스
# left=0, right=0 → 길이 1 (맞음)
# left=0, right=2 → 길이 3 (맞음)문제 3: 시간 초과 (TLE)
증상: 윈도우 내부에서 무거운 연산 반복 아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
# 잘못된 예
for right in range(len(arr)):
# 매번 윈도우 전체를 순회 → O(n²)
if is_valid(arr[left:right+1]):
ans = max(ans, right - left + 1)해결: 증분 갱신 아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 올바른 예
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)이 보장됩니다.