투포인터, 슬라이딩 윈도우, 파라메트릭 서치 구분

세 기법은 모두 포인터가 움직여서 비슷해 보이지만 전제가 다릅니다. 투포인터는 순서 관계, 슬라이딩 윈도우는 연속 구간 상태, 파라메트릭 서치는 단조 판정이 핵심입니다. 전제를 확인하지 않고 기법만 적용하면 코드가 돌아가도 정답이 틀릴 수 있습니다.

여기서는 구현 디테일보다 문제 신호를 읽는 기준에 집중합니다. 입력 조건을 우선 분기하면 풀이 시간이 크게 줄고 디버깅도 쉬워집니다. 세 기법의 선택 흐름을 같은 문제 해석 프레임으로 정리합니다.

핵심 패턴 맵

세 기법은 포인터를 움직인다는 공통점만 있고, 성립 조건은 다릅니다. 문제를 읽을 때 정렬 전제, 연속 구간 전제, 단조 판정 전제를 우선 체크해 두세요.

투포인터는 두 인덱스의 상대 이동으로 탐색 공간을 줄이는 기법입니다. 보통 정렬된 배열이나 순서성이 보장된 자료에서 조건을 만족하는 쌍/구간을 선형에 가깝게 찾습니다. 정렬 배열 두 수의 합에서 합이 작으면 왼쪽 포인터를 오른쪽으로 옮기는 규칙이 대표 예시입니다.

슬라이딩 윈도우는 연속 구간의 상태를 유지하면서 경계를 이동하는 기법입니다. 합, 빈도, 길이 같은 구간 통계를 증분 갱신해 left/right를 조절하며 최적 조건을 찾습니다. 양수 배열 최소 길이 부분합 문제에서 합이 목표 이상이면 left를 줄여 더 짧은 구간을 탐색합니다.

파라메트릭 서치는 정답 그 자체가 아니라 정답 후보 값의 가능성을 이분 탐색하는 방식입니다. ok(x) 같은 단조 판정 함수가 있을 때 최소 feasible 값 또는 최대 feasible 값을 찾을 수 있습니다. 이 속도로 제한 시간 내 처리가 가능한가? 판정이 단조라면 최소 속도를 경계 탐색으로 계산할 수 있습니다.

포인터/윈도우 실전 장애와 연결하기

잘못된 기법을 선택하면 구현이 돌아가도 증명이 무너집니다. 예를 들어 음수가 섞인 배열에 양수 전용 윈도우를 적용하면 조건 축소가 단조하지 않아 오답이 발생합니다.

또한 파라메트릭 서치는 데이터 탐색이 아니라 후보 값의 가능성 탐색이라는 점을 이해해야 합니다. 이 차이를 놓치면 시간복잡도 계산이 틀어집니다.

윈도우 구간 테스트로 빠르게 재확인하기

학습 효율을 높이려면 오답 -> 디버깅 -> 교정 -> 검증 순서로 로그를 남기면서 진행하는 것이 가장 빠릅니다.

문제 신호를 보고 기법을 고르는 과정을 간단히 따라갑니다.

신호 A: 정렬 배열, 두 수 합
신호 B: 양수 배열, 최소 길이 부분배열
신호 C: 답이 속도 값, 가능/불가능 판정 가능

A는 투포인터로 좌우 포인터를 이동합니다.
B는 슬라이딩 윈도우로 조건을 만족할 때 왼쪽을 줄입니다.
C는 파라메트릭 서치로 최소 가능한 값을 찾습니다.
전제(정렬/양수/단조성)를 우선 확인해야 오답을 막을 수 있습니다.

투포인터·윈도우·파라메트릭 적용 관점

아래 표처럼 문제 신호를 읽으면 빠르게 분기할 수 있습니다.

정렬 배열에서 두 수/두 구간 관계: 투포인터
연속 부분배열의 합/빈도/길이 최적화: 슬라이딩 윈도우
답이 숫자 범위이고 판정 함수가 단조: 파라메트릭 서치

입력 전제(정렬, 양수, 단조성)를 우선 검증하는 습관이 중요합니다.

투포인터/윈도우: 투포인터(정렬 배열 두 수의 합)

문제 의도: 정렬 배열에서 두 포인터로 목표 합을 만족하는 쌍을 찾습니다.
입력 예시: arr=[1,2,3,4,6,8], target=10
출력 예시: 유효 인덱스/쌍 또는 존재 여부

main.cpp

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

pair<int, int> twoSumSorted(const vector<int>& nums, int target) {
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;

    while (lo < hi) {
        int s = nums[lo] + nums[hi];
        if (s == target) return {lo, hi};
        if (s < target) lo++;
        else hi--;
    }

    return {-1, -1}; // not found
}

int main() {
    vector<int> arr = {1, 2, 4, 7, 11, 15};
    auto ans = twoSumSorted(arr, 15);
    cout << "(" << ans.first << ", " << ans.second << ")\n";
    return 0;
}

Main.java

import java.util.Arrays;

public class Main {
    static int[] twoSumSorted(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;

        while (lo < hi) {
            int s = nums[lo] + nums[hi];
            if (s == target) return new int[]{lo, hi};
            if (s < target) lo++;
            else hi--;
        }

        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 7, 11, 15};
        System.out.println(Arrays.toString(twoSumSorted(arr, 15)));
    }
}

main.py

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return (lo, hi)
        if s < target:
            lo += 1
        else:
            hi -= 1

    return None

arr = [1, 2, 4, 7, 11, 15]
print(two_sum_sorted(arr, 15))
# 출력: (1, 4)  # 2 + 11

main.rs

fn two_sum_sorted(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    if nums.len() < 2 {
        return None;
    }

    let (mut lo, mut hi) = (0usize, nums.len() - 1);
    while lo < hi {
        let s = nums[lo] + nums[hi];
        if s == target {
            return Some((lo, hi));
        }
        if s < target {
            lo += 1;
        } else {
            hi -= 1;
        }
    }
    None
}

fn main() {
    let arr = vec![1, 2, 4, 7, 11, 15];
    println!("{:?}", two_sum_sorted(&arr, 15));
}

포인터 이동 선정 탐색 구간 조건 체크

투포인터는 두 인덱스의 상대 관계를 조절하는 방식입니다. 정렬 전제가 있어야 s < target일 때 왼쪽을 올리는 결정이 안전합니다. 정렬이 없다면 같은 규칙은 성립하지 않습니다.

평균 시간복잡도: O(N)
최악 시간복잡도: O(N)
공간복잡도: O(1)

투포인터/윈도우: 슬라이딩 윈도우(최소 길이 부분배열)

문제 의도: 조건을 만족하는 최소 길이 구간을 선형 시간에 찾습니다.
입력 예시: arr=[2,3,1,2,4,3], target=7
출력 예시: 2

main.cpp

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int minLenSubarrayAtLeast(int target, const vector<int>& nums) {
    int left = 0;
    int curSum = 0;
    int best = INT_MAX;

    for (int right = 0; right < static_cast<int>(nums.size()); ++right) {
        curSum += nums[right];

        while (curSum >= target) {
            best = min(best, right - left + 1);
            curSum -= nums[left];
            left++;
        }
    }

    return best == INT_MAX ? 0 : best;
}

int main() {
    vector<int> arr = {2, 3, 1, 2, 4, 3};
    cout << minLenSubarrayAtLeast(7, arr) << "\n";
    return 0;
}

Main.java

public class Main {
    static int minLenSubarrayAtLeast(int target, int[] nums) {
        int left = 0;
        int curSum = 0;
        int best = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {
            curSum += nums[right];
            while (curSum >= target) {
                best = Math.min(best, right - left + 1);
                curSum -= nums[left++];
            }
        }

        return best == Integer.MAX_VALUE ? 0 : best;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 2, 4, 3};
        System.out.println(minLenSubarrayAtLeast(7, arr));
    }
}

main.py

def min_len_subarray_at_least(target, nums):
    left = 0
    cur_sum = 0
    best = float('inf')

    right = 0
    while right < len(nums):
        cur_sum += nums[right]

        while cur_sum >= target:
            best = min(best, right - left + 1)
            cur_sum -= nums[left]
            left += 1

        right += 1

    return 0 if best == float('inf') else best

arr = [2, 3, 1, 2, 4, 3]
print(min_len_subarray_at_least(7, arr))
# 출력: 2

main.rs

fn min_len_subarray_at_least(target: i32, nums: &[i32]) -> usize {
    let mut left = 0usize;
    let mut right = 0usize;
    let mut cur_sum = 0i32;
    let mut best = usize::MAX;

    while right < nums.len() {
        cur_sum += nums[right];
        while cur_sum >= target {
            best = best.min(right - left + 1);
            cur_sum -= nums[left];
            left += 1;
        }
        right += 1;
    }

    if best == usize::MAX { 0 } else { best }
}

fn main() {
    let arr = vec![2, 3, 1, 2, 4, 3];
    println!("{}", min_len_subarray_at_least(7, &arr));
}

윈도우 축소/확장 포인터 이동 추적

윈도우는 구간 내부 상태를 유지하는 것이 핵심입니다. 이 예제는 모든 값이 양수라는 전제가 있어 while로 줄일 때 합이 단조 감소합니다. 음수가 섞이면 같은 전략은 깨집니다.

평균 시간복잡도: O(N)
최악 시간복잡도: O(N)
공간복잡도: O(1)

투포인터/윈도우: 파라메트릭 서치(최소 처리 속도)

문제 의도: 단조 판정 함수를 이용해 최소 가능한 속도를 이진 탐색합니다.
입력 예시: workloads=[3,6,7,11], hours=8
출력 예시: 최소 속도 값

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

bool canFinish(const vector<int>& workloads, int hours, int speed) {
    long long total = 0;
    for (int w : workloads) {
        total += (w + speed - 1) / speed;
    }
    return total <= hours;
}

int minSpeedToFinish(const vector<int>& workloads, int hours) {
    int lo = 1;
    int hi = *max_element(workloads.begin(), workloads.end());

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(workloads, hours, mid)) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}

int main() {
    vector<int> jobs = {3, 6, 7, 11};
    cout << minSpeedToFinish(jobs, 8) << "\n";
    return 0;
}

Main.java

public class Main {
    static int maxValue(int[] workloads) {
        int best = 1;
        for (int w : workloads) {
            if (w > best) {
                best = w;
            }
        }
        return best;
    }

    static int minSpeedToFinish(int[] workloads, int hours) {
        int lo = 1;
        int hi = maxValue(workloads);

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (can(workloads, hours, mid)) hi = mid;
            else lo = mid + 1;
        }

        return lo;
    }

    static boolean can(int[] workloads, int hours, int speed) {
        long total = 0;
        for (int w : workloads) total += (w + speed - 1) / speed;
        return total <= hours;
    }

    public static void main(String[] args) {
        int[] jobs = {3, 6, 7, 11};
        System.out.println(minSpeedToFinish(jobs, 8));
    }
}

main.py

def min_speed_to_finish(workloads, hours):
    def can(speed):
        total = 0
        for w in workloads:
            total += (w + speed - 1) // speed
        return total <= hours

    lo, hi = 1, max(workloads)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1

    return lo

jobs = [3, 6, 7, 11]
print(min_speed_to_finish(jobs, 8))
# 출력: 4

main.rs

fn can(workloads: &[i32], hours: i32, speed: i32) -> bool {
    let mut total: i64 = 0;
    for &w in workloads {
        total += ((w + speed - 1) / speed) as i64;
    }
    total <= hours as i64
}

fn min_speed_to_finish(workloads: &[i32], hours: i32) -> i32 {
    let mut lo = 1;
    let mut hi = 1;
    for &w in workloads {
        if w > hi {
            hi = w;
        }
    }

    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if can(workloads, hours, mid) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    lo
}

fn main() {
    let jobs = vec![3, 6, 7, 11];
    println!("{}", min_speed_to_finish(&jobs, 8));
}