[TIL] 2026-06-30 — 슬라이딩 윈도우: 고정 크기 vs 가변 크기 (LeetCode 643·3)
오늘은 슬라이딩 윈도우 한 패턴을 두 변형으로 익혔다. 고정 크기(643 Maximum Average Subarray I) 와 가변 크기(3 Longest Substring Without Repeating Characters). 공통 본질은 “직전 윈도우 계산 결과를 재활용해 매 스텝 O(1)로 갱신 → 전체 O(n)”. 브루트포스의 O(n·k)·O(n²)를 선형으로 끌어내리는 것이 슬라이딩 윈도우의 핵심이라는 감을 굳혔다.
오늘 한 일 요약
슬라이딩 윈도우 2문제를 고정·가변 두 패턴으로 풀며 차이를 정리했다.
- LeetCode 643 Maximum Average Subarray I (Easy) — 길이 k 고정 윈도우. “평균 최대 = 합 최대”로 환원하고,
sum += nums[i] - nums[i-k]로 한 칸씩 밀어 O(n). - LeetCode 3 Longest Substring Without Repeating Characters (Medium) — 가변 윈도우.
last[c]로 문자의 마지막 등장 위치를 추적, 중복 발견 시left를 한 칸씩 줄이지 않고 중복 직후로 점프해 O(n).
1. Maximum Average Subarray I (LeetCode 643) — 고정 크기 윈도우
출처: https://leetcode.com/problems/maximum-average-subarray-i/
정수 배열 nums(n개)와 정수 k가 주어질 때, 길이가 정확히 k인 연속 부분배열 중 평균이 최대인 것의 평균값을 반환한다.
- 제약:
1 <= k <= n <= 10^5,-10^4 <= nums[i] <= 10^4 - 예시:
nums = [1,12,-5,-6,50,3], k = 4→(12-5-6+50)/4 = 51/4 = 12.75
접근 — 합 최대로 환원
길이가 k로 고정이므로 분모(k)가 일정하다. 따라서 “평균 최대”는 “합 최대”와 완전히 동치다. 합이 최대인 윈도우만 찾고 마지막에 한 번만 k로 나누면 된다.
매번 윈도우의 k개를 다시 더하면 O(n·k)다. 대신 윈도우를 한 칸 밀 때 새로 들어온 원소를 더하고 빠진 원소를 빼면(sum += nums[i] - nums[i-k]) 갱신이 O(1)이 되어 전체 O(n)이 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
double findMaxAverage(vector<int>& nums, int k)
{
int sum = 0;
for (int i = 0; i < k; ++i) sum += nums[i]; // 첫 윈도우 합
int best = sum;
for (int i = k; i < (int)nums.size(); ++i)
{
sum += nums[i] - nums[i - k]; // 한 칸 밀기: 더하고 빼기
best = max(best, sum);
}
return (double)best / k; // 마지막에 한 번만 실수 나눗셈
}
포인트
- 정수 합을 끝까지 유지하다가 마지막에만
(double)best / k로 실수 나눗셈 → 매 스텝 나누는 것보다 부동소수 오차가 적고 계산도 적다. best를 첫 윈도우 합으로 초기화해야 한다.0으로 두면 모든 원소가 음수일 때 오답이 난다.- 시간 O(n), 공간 O(1).
2. Longest Substring Without Repeating Characters (LeetCode 3) — 가변 크기 윈도우
출처: https://leetcode.com/problems/longest-substring-without-repeating-characters/
문자열 s에서 중복 문자가 없는 가장 긴 부분문자열(substring) 의 길이를 반환한다. substring은 연속이어야 한다(subsequence 아님).
- 제약:
0 <= s.length <= 5*10^4, 영문/숫자/기호/공백 구성 - 예시:
"abcabcbb"→ 3 ("abc"),"bbbbb"→ 1,"pwwkew"→ 3 ("wke";"pwke"는 비연속이라 오답)
접근 — 가변 윈도우 + 마지막 등장 위치 점프
[left, right] 구간을 “중복 없는 윈도우”로 유지하며 right를 끝까지 전진시킨다. last[c]에 문자 c가 마지막으로 나온 인덱스를 기록한다. right가 가리키는 문자 c가 이미 윈도우 안에 있으면(last[c] >= left), left를 last[c] + 1로 바로 점프시켜 중복을 윈도우 밖으로 밀어낸다.
핵심은 left를 한 칸씩 줄이지 않고 한 번에 점프시키는 것이다. 덕분에 left와 right 모두 단조 증가만 하므로 전체가 O(n)이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lengthOfLongestSubstring(string s)
{
vector<int> last(256, -1); // 아직 등장 안 한 문자는 -1
int best = 0, left = 0;
for (int right = 0; right < (int)s.size(); ++right)
{
unsigned char c = s[right];
if (last[c] >= left) // 윈도우 안에서 중복 발견
left = last[c] + 1; // 중복 직후로 left 점프
last[c] = right;
best = max(best, right - left + 1);
}
return best;
}
포인트
last[c] >= left조건이 관건이다.last[c]가 left보다 작으면 그 등장은 이미 윈도우 밖이므로 중복이 아니다. left를 뒤로 당기면 안 되니 반드시 현재 left와 비교한다.last를 256 크기 배열로 두어 영문/숫자/기호/공백을 모두 커버한다.unsigned char로 인덱싱해 음수 인덱스를 방지한다.- substring(연속) vs subsequence(비연속) 구분 주의 — 이 문제는 연속이라 윈도우로 풀린다.
- 시간 O(n), 공간 O(1)(고정 크기 256 배열).
두 패턴 비교
| 구분 | 고정 크기 (643) | 가변 크기 (3) |
|---|---|---|
| 윈도우 크기 | k로 고정 | 조건 만족하는 한 최대로 확장 |
right 전진 시 | left도 같이 한 칸 전진(크기 k 유지) | 조건이 깨질 때만 left 조정 |
left 이동 방식 | 항상 한 칸 | 중복 직후로 점프 |
| 갱신 식 | sum += nums[i] - nums[i-k] | if(last[c]>=left) left=last[c]+1 |
| 쓰는 문제 | “크기 k 구간의 합·평균 최대/최소” | “조건 만족하는 최대 구간 길이” |
| 답 추적 | 윈도우 합 best | 윈도우 길이 right-left+1의 max |
| 복잡도 | O(n) / O(1) | O(n) / O(1) |
- 고정 크기: 윈도우 크기가 정해져 있어 right가 전진하면 left도 함께 한 칸 전진해 k를 유지한다. 들어온 값과 빠진 값만 보정하면 끝.
- 가변 크기: 조건(중복 없음)이 깨질 때만 left를 조정한다. “조건을 만족하는 최대 윈도우”를 찾는 문제 부류에 쓰인다.
- 공통 본질: 직전 계산 결과를 재활용해 매 스텝 O(1)로 갱신 → 전체 O(n). 브루트포스 O(n²)/O(n·k)를 선형으로 끌어내리는 것이 슬라이딩 윈도우의 핵심이다.
오늘 배운 것 정리
- 고정 크기는 합 보정: 길이가 고정이면 평균 최대 = 합 최대. 매번 다시 더하지 말고
+새값 -뺀값으로 O(1) 갱신해 O(n). - 가변 크기는 left 점프: 중복이 윈도우 안에 있을 때 left를 한 칸씩 당기지 말고 중복 직후로 한 번에 점프 → left·right 모두 단조 증가 → O(n).
last[c] >= left비교가 핵심: 윈도우 밖의 옛 등장은 중복이 아니다. 전역 등장 여부가 아니라 현재 윈도우 기준으로 판단해야 한다.- 부동소수는 마지막에 한 번만: 정수 합을 유지하다 끝에서만 실수 나눗셈해 오차와 연산을 줄인다.
- substring vs subsequence: 연속이어야 윈도우가 성립한다. 비연속이면 다른 접근(예: DP)이 필요하다.