[CS/알고리즘] 투 포인터 알고리즘

황제연·2025년 3월 26일

슬라이딩 윈도우 알고리즘 알고리즘 투 포인터

CS학습

목록 보기

25/193

🔍 투 포인터 (Two Pointer)

투 포인터는 배열이나 리스트 같은 자료구조에서
두 개의 포인터를 사용해 조건에 맞는 값을 찾아내는 알고리즘입니다

📌 투 포인터 동작방식

투 포인터는 보통 두 가지 방식을 사용합니다

✅ 양 끝에서 출발하는 방식

배열의 양 끝에서 시작해, 점점 가운데로 모여드는 방식입니다
주로 정렬된 배열에서 많이 사용합니다

✅ 같은 방향으로 출발하는 방식

투 포인터가 같은 방향으로 출발해, 조건에 따라 움직이는 방식입니다
조건에 맞는 부분 배열을 빠르게 찾는 방식으로, 슬라이딩 윈도우와 유사합니다

📌 투 포인터의 장점

시간복잡도를 개선할 수 있습니다 ( O(N^2) → O(N) )
고정된 크기를 유지하는 슬라이딩 윈도우와 달리,
투 포인터는 유동적으로 범위를 조절하기 때문에 메모리 사용 면에서 더 효율적입니다

📌 투 포인터의 단점

정렬이 필수적이라 추가 비용이 발생합니다

📌 슬라이딩 윈도우와 비교

비교	투 포인터	슬라이딩 윈도우
포인터 이동 방식	양방향 or 같은 방향	한 방향
구간 크기	가변적	고정적
주요 활용	두 수의 합 등	연속 구간 내 등

✅투 포인터가 적용된 문제

백준 2470번 두 용액 문제는 투 포인터의 첫번째 방식으로 해결할 수 있습니다
N의 크기가 10^5 이므로 단순 브루트포스로는 해결할 수 없습니다

해당 문제는 오름차순 정렬 후, 투 포인터 알고리즘으로 해결할 수 있습니다

Arrays.sort(arr);  
int left = 0;  
int right = n-1;  
int ansL = 0;  
int ansR = 0;  
int ans = Integer.MAX_VALUE;  
  
while(left < right){  
    int sum = arr[left] + arr[right];  
    if(Math.abs(sum) < ans){  
        ans = Math.abs(sum);  
        ansL = arr[left];  
        ansR = arr[right];  
    }  
  
    if (sum < 0) {  
        left++;  
    }else{  
        right--;  
    }  
}

위와같이 오름차순 정렬 후, 양 끝 지점에 포인터를 배치합니다
포인터 위치의 값이 0보다 작다면 left를 이동하고, 아닌 경우 right를 이동하여
가장 적합한 정답을 찾습니다