🔍 투 포인터(Two-Pointer) 알고리즘 정리 및 팁

🔍 투 포인터(Two-Pointer) 알고리즘 정리 및 팁

2025. 2. 24. 16:45ㆍ프론트엔드/Next JS

728x90

✅ 1. 투 포인터(Two-Pointer) 알고리즘이란?

투 포인터는 두 개의 포인터(left, right)를 활용하여 배열을 탐색하는 방식입니다.
일반적으로 배열이 정렬되어 있어야 적용 가능하며, 다음과 같은 원칙을 따릅니다.

📌 투 포인터의 핵심 원칙

정렬된 배열에서 사용 → 필요에 따라 sort()를 이용하여 정렬 (O(N log N))
두 개의 포인터(left, right)를 활용하여 탐색 진행
- left → 보통 **배열의 시작(0번 인덱스)**에서 시작
- right → 보통 **배열의 끝(마지막 인덱스)**에서 시작
조건을 만족하면 두 포인터를 조정
- 합이 작으면 left++ (더 큰 값 필요)
- 합이 크면 right-- (더 작은 값 필요)

✅ 2. 투 포인터를 활용한 "좋은 수(GOOD NUMBER)" 문제 풀이

주어진 문제에서 "좋은 수"란 다른 두 숫자의 합으로 표현될 수 있는 수입니다.

🔹 알고리즘 흐름

입력값을 정렬 (sort())
각 숫자(target = v1[k])에 대해, 두 개의 다른 수(v1[i] + v1[j])를 찾기 위해 투 포인터 적용
포인터 조정
- v1[left] + v1[right] == target → "좋은 수" 발견 (ans++)
- v1[left] + v1[right] < target → 더 큰 값 필요 (left++)
- v1[left] + v1[right] > target → 더 작은 값 필요 (right--)

📌 투 포인터 적용 코드 (최적화)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v1(n);

    for (int i = 0; i < n; i++) {
        cin >> v1[i];
    }

    // 1. 정렬 수행 (O(N log N))
    sort(v1.begin(), v1.end());

    int ans = 0;

    // 2. 각 숫자가 "좋은 수"인지 확인
    for (int k = 0; k < n; k++) {
        int target = v1[k];
        int left = 0, right = n - 1;

        while (left < right) {
            if (left == k) { // 자기 자신을 포함하면 안됨
                left++;
                continue;
            }
            if (right == k) { // 자기 자신을 포함하면 안됨
                right--;
                continue;
            }

            int sum = v1[left] + v1[right];

            if (sum == target) { // "좋은 수" 발견
                ans++;
                break; // 해당 숫자가 "좋은 수"이면 더 이상 탐색할 필요 없음
            } 
            else if (sum < target) {
                left++; // 합이 부족하면 left 증가
            } 
            else {
                right--; // 합이 크면 right 감소
            }
        }
    }

    cout << ans << endl;
    return 0;
}

✅ 3. 시간 복잡도 분석

단계 연산 횟수 시간 복잡도

배열 정렬	O(N log N)	O(N log N)
투 포인터 탐색	O(N^2)	O(N^2)
총 시간 복잡도	O(N log N) + O(N^2)	O(N^2)

🔹 기존 O(N^3)보다 훨씬 빠름!
🔹 N이 최대 2000일 경우 O(N^2) = 4,000,000 정도의 연산으로 해결 가능 🚀

✅ 4. 투 포인터 알고리즘의 장점

이중 for문을 사용하지 않고도 빠르게 해결 가능 (보통 O(N^2))
배열이 정렬되어 있다면 불필요한 탐색을 줄일 수 있음
데이터 크기가 커질수록 효율성이 극대화됨

✅ 5. 투 포인터 활용 팁

🟢 팁 1: 투 포인터는 반드시 "정렬된 배열"에서 사용

sort(v1.begin(), v1.end());  // 정렬 후 사용해야 함

왜 정렬해야 할까?
- 투 포인터는 값을 비교하면서 이동하기 때문에 정렬되지 않으면 정확한 결과를 얻을 수 없음.

🟢 팁 2: 포인터가 겹치지 않도록 조건 설정

while (left < right) { ... }

왜 left < right 조건이 필요할까?
- 포인터가 서로 겹치면 같은 원소를 두 번 사용할 수 있어 오류가 발생할 수 있음.

🟢 팁 3: 특정 조건을 만족하면 break; 사용

if (sum == target) {
    ans++;
    break;
}

특정 조건을 만족하면 **불필요한 탐색을 줄이기 위해 break;**를 사용하여 빠르게 루프 종료.

🟢 팁 4: 값이 부족하면 left++, 값이 크면 right--

if (sum < target) left++; // 합이 부족하므로 더 큰 값 필요
else right--; // 합이 크므로 더 작은 값 필요

투 포인터 알고리즘에서는 값을 조정하는 방향이 중요.

✅ 6. 투 포인터를 활용할 수 있는 문제 유형

유형 예제

✅ 두 수의 합	BOJ 3273 - 두 수의 합
✅ 세 수의 합	BOJ 2473 - 세 용액
✅ 부분합	BOJ 1806 - 부분합
✅ 좋은 수	BOJ 1253 - 좋은 수

🎯 7. 결론

기존 방법 (O(N^3)) 투 포인터 (O(N^2))

모든 가능한 두 수의 합을 찾음	포인터를 이동하면서 최적의 값을 탐색
시간 초과 발생 가능	빠른 탐색 가능
N=2000일 때 O(N^3) = 8,000,000,000 연산 필요	O(N^2) = 4,000,000 연산으로 해결 가능

✅ "정렬된 배열에서 특정 조건을 만족하는 두 개의 원소를 찾을 때, 투 포인터는 강력한 해결책이 된다!" 🚀

🔹 투 포인터 활용 요약

배열 정렬 (O(N log N))
포인터(left, right)를 설정
조건에 따라 left++, right-- 조정
탐색 최적화 (O(N^2))