투 포인터 / 슬라이딩 윈도우
투 포인터와 슬라이딩 윈도우는 둘 다 배열을 이중 반복문 없이 한 번만 훑어서(O(n)) 답을 찾는 기법입니다. 무작정 모든 경우를 확인하면(O(n²)) 느려지는 문제를, 포인터 두 개의 위치 관계만으로 훨씬 빠르게 풀 수 있습니다.
핵심 개념
투 포인터
정렬된 배열의 양 끝에서 포인터 두 개가 서로를 향해 이동합니다. 합이 목표보다 작으면 왼쪽을, 크면 오른쪽을 움직여 원하는 조건에 맞춰갑니다.
핵심 개념
슬라이딩 윈도우
배열 위를 이동하는 "창(window)"을 유지합니다. 오른쪽 끝을 늘려 조건을 만족시키고, 만족하는 동안 왼쪽 끝을 줄여 더 나은 답(더 짧은 구간 등)을 찾습니다.
핵심 개념
왜 정렬이 필요한가 (투 포인터)
배열이 정렬되어 있어야 "합이 작으면 왼쪽을 옮긴다"는 판단이 성립합니다. 정렬되어 있지 않다면 이 판단 자체가 의미를 잃습니다 — "정렬이 필요한 이유" 탭에서 실제로 답을 놓치는 모습을 확인할 수 있습니다.
핵심 개념
왜 O(n)인가
두 기법 모두 각 포인터가 배열을 한 번씩만 훑고, 각자 한 방향으로만 움직이며 뒤로 가지 않습니다. 그래서 전체 이동 횟수가 최대 2n(또는 n)번으로 제한됩니다.
핵심 개념
언제 투 포인터, 언제 슬라이딩 윈도우
"정렬된 배열에서 두 값의 관계"를 다루면 투 포인터, "연속된 구간(부분 배열/부분 문자열)의 합이나 길이"를 다루면 슬라이딩 윈도우인 경우가 많습니다.
핵심 개념
완전탐색과의 차이
모든 쌍이나 모든 구간을 다 확인하면 O(n²)이 걸립니다. 두 포인터가 "필요 없는 경우의 수"를 아예 건너뛰어 버려서, 확인하는 횟수 자체를 줄이는 것이 핵심입니다.
어떤 문제에 쓰나
투 포인터는 정렬된 배열에서 합이 목표인 두 수를 찾는 문제처럼 '두 위치의 관계'를 다루는 문제에, 슬라이딩 윈도우는 연속 구간의 합이나 길이를 다루는 문제에 쓰입니다. 공통점은 한 번 지나간 위치를 다시 보지 않아서 전체 이동 횟수가 입력 크기에 비례한다는 점입니다.
숫자로 확인하기
자주 하는 오해
면접에서 이렇게 물어요
면접 질문
정렬된 배열에서 합이 target인 두 수를 O(n)에 찾으려면 어떻게 하나요?
양 끝에 포인터를 두고 합이 target보다 작으면 왼쪽을, 크면 오른쪽을 안쪽으로 옮깁니다. 정렬되어 있어서 옮긴 쪽 값은 더 이상 답에 쓰일 수 없으므로 되돌아갈 필요가 없습니다.
면접 질문
중복 문자가 없는 가장 긴 부분 문자열의 길이는 어떻게 구하나요?
슬라이딩 윈도우로 오른쪽을 늘리며 문자를 넣고, 중복이 생기면 중복이 사라질 때까지 왼쪽을 줄입니다. 각 포인터가 문자열을 한 번씩만 지나므로 O(n)입니다.
면접 질문
3Sum 문제의 시간 복잡도는 얼마인가요?
배열을 정렬(O(n log n))한 뒤 원소 하나를 고정하고 나머지 구간에서 투 포인터로 합을 찾으면 O(n²)입니다. 모든 세 쌍을 확인하는 O(n³)보다 줄어듭니다.
면접 질문
연결 리스트에 순환이 있는지 어떻게 알 수 있나요?
한 칸씩 가는 느린 포인터와 두 칸씩 가는 빠른 포인터를 두고, 둘이 만나면 순환이 있습니다. 순환이 없으면 빠른 포인터가 끝(null)에 먼저 도달합니다. 같은 방향으로 움직이는 투 포인터의 한 예입니다.
실제 시스템에서는
함께 보면 좋은 토픽
참고 자료
Java — 투 포인터 (정렬 배열에서 두 수의 합)
/* ── 양 끝에서 시작해 서로를 향해 좁혀 들어감 ──────────────── */ public int[] twoSumSorted(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left < right) { int sum = arr[left] + arr[right]; if (sum == target) { return new int[]{left, right}; // 발견 } else if (sum < target) { left++; // 더 큰 값이 필요 → 왼쪽을 오른쪽으로 } else { right--; // 더 작은 값이 필요 → 오른쪽을 왼쪽으로 } } return new int[]{-1, -1}; // 못 찾음 }
left와 right는 각자 최대 배열 길이만큼만 움직이고 절대 서로를 지나치거나 되돌아가지 않으므로, while문 전체 반복 횟수는 O(n)입니다.
모든 (i, j) 쌍을 확인하는 이중 반복문(O(n²))과 달리, "정렬되어 있다"는 사실 하나로 절반 이상의 쌍을 아예 확인하지 않고 건너뜁니다.
Java — 슬라이딩 윈도우 (합이 target 이상인 최소 길이 구간)
/* ── 오른쪽으로 늘리고, 조건을 만족하면 왼쪽부터 줄여봄 ────── */ public int minSubArrayLen(int[] arr, int target) { int left = 0, sum = 0, minLen = Integer.MAX_VALUE; for (int right = 0; right < arr.length; right++) { sum += arr[right]; // 오른쪽으로 창을 늘림 while (sum >= target) { // 조건을 만족하는 동안 계속 줄여봄 minLen = Math.min(minLen, right - left + 1); sum -= arr[left]; left++; // 왼쪽을 줄임 } } return minLen == Integer.MAX_VALUE ? 0 : minLen; }
right는 바깥 for문에서 n번, left는 안쪽 while문에서 전체 실행에 걸쳐 최대 n번만 움직입니다 — 겹쳐 있는 반복문처럼 보여도 합치면 O(n) + O(n) = O(n)입니다.
while문 안에서 조건을 만족하는 "동안 계속" 줄이는 것이 핵심입니다 — 한 번만 줄이고 멈추면 더 짧은 구간을 놓칠 수 있습니다.
Java — 슬라이딩 윈도우 (크기 고정, 최대 합)
/* ── 창 크기가 항상 k로 고정된 경우 ────────────────────────── */ public int maxSumFixedWindow(int[] arr, int k) { int windowSum = 0; for (int i = 0; i < k; i++) windowSum += arr[i]; // 첫 창의 합을 미리 계산 int maxSum = windowSum; for (int right = k; right < arr.length; right++) { windowSum += arr[right] - arr[right - k]; // 새로 들어온 값 더하고, 빠진 값 빼기 maxSum = Math.max(maxSum, windowSum); } return maxSum; }
크기가 고정된 창은 매번 k개를 다시 더하지 않고, arr[right] - arr[right - k]처럼 "새로 들어온 값만 더하고 빠진 값만 빼는" 방식으로 O(1)에 갱신합니다.
이렇게 하면 전체 시간복잡도가 O(n·k)가 아니라 O(n)이 됩니다 — 이 시각화의 가변 크기 윈도우와 함께, 슬라이딩 윈도우의 두 가지 대표 유형(고정 크기 / 가변 크기)을 이룹니다.
Q1
정렬된 배열에서 두 수의 합을 찾는 투 포인터 기법의 동작은?
Q2
슬라이딩 윈도우(Sliding Window)가 최소 길이 부분배열 문제에 쓰이는 방식은?
Q3
투 포인터 기법이 정렬되지 않은 배열에서 그대로 적용되지 않는 이유는?