탐색 기법O(n)

슬라이딩 윈도우

창을 오른쪽으로 넓히고, 조건을 어기면 왼쪽을 줄여요. 구간 문제를 O(n)에 풀어요.

이럴 때 써요

"합이 S 이상인 가장 짧은 구간" 처럼 조건을 만족하는 연속 구간을 찾을 때
"중복 없는 가장 긴 부분문자열" 처럼 이어진 구간의 최대·최소 길이를 물을 때
모든 구간을 두 겹 반복으로 보면 O(n²)인데 더 빠르게 해야 할 때
정렬된 배열에서 두 수의 합이 target이 되는 짝을 찾을 때 (양끝 투 포인터)

개념

연속 구간 문제를 매번 처음부터 다시 세면 O(n²)이에요. 슬라이딩 윈도우는 left와 right 두 포인터로 창(window) 하나를 잡고, 이 창을 통째로 옮겨 다녀요. 조건을 만족하는 동안 right를 오른쪽으로 넓히고, 조건을 어기면 left를 오른쪽으로 좁혀요. 둘 다 같은 방향으로만 가서 각 칸을 많아야 두 번(들어올 때, 나갈 때) 보니 O(n)이에요.핵심은 창의 상태를 통째로 다시 계산하지 않고 조금씩 고치는 거예요. right가 한 칸 넓어지면 그 값을 상태에 더하고(합에 +, 빈도표에 +1), left가 한 칸 좁아지면 나가는 값을 상태에서 빼요(합에 -, 빈도표에 -1). 이 더하고 빼는 게 짝이 맞아야 창의 합이나 문자 개수가 항상 정확해요.

"합이 7 이상인 최소 길이 구간, [2, 3, 1, 2, 4, 3]" — left/right/합
값:  2  3  1  2  4  3
칸:  0  1  2  3  4  5
right=0  합=2                         <7  넓혀요
right=1  합=5                         <7  넓혀요
right=2  합=6                         <7  넓혀요
right=3  합=8  >=7  길이 4 (0..3)  →  left 줄여요: 합=6, left=1
right=4  합=10 >=7  길이 4 (1..4)  →  left 줄여: 합=7 길이3(2..4), 합=6 left=3
right=5  합=9  >=7  길이 3 (3..5)  →  left 줄여: 합=7 길이2(4..5), 합=3 left=5
→ 가장 짧은 길이는 2 (구간 [4, 3])

정렬된 배열에서 "두 수의 합 = target"을 찾는 양끝 투 포인터도 사촌이에요. 여긴 left를 맨 앞, right를 맨 뒤에 두고 서로 마주 보게 좁혀요. 합이 크면 right--, 작으면 left++ 하면서 창을 줄여 가는데, 방향만 다를 뿐 "두 포인터로 후보를 훑는다"는 아이디어는 같아요.

패턴 코드

합이 S 이상인 최소 길이 구간right로 넓히며 합을 더하고, 합이 S 이상이면 while 안에서 길이를 갱신하면서 left를 좁혀 최소 길이를 찾아요.

javascript
Copy code
function minSubArrayLen(s, nums) {
  let left = 0;
  let sum = 0;
  let best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= s) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

중복 없는 최장 부분문자열각 문자가 마지막에 나온 칸을 기억해요. 창 안에서 같은 문자를 또 만나면 left를 그 다음 칸으로 점프시켜 중복을 지워요.

javascript
Copy code
function longestUnique(str) {
  const last = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < str.length; right++) {
    const ch = str[right];
    if (last.has(ch) && last.get(ch) >= left) {
      left = last.get(ch) + 1;
    }
    last.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

이 유형으로 풀어보기

← 파라메트릭 서치 — 결정 문제로 바꾸기 DFS·BFS 완전탐색 →