[투 포인터] 효율적인 배열 탐색의 비법

투 포인터(Two Pointer) 

투 포인터(Two Pointer) 기법은 배열이나 리스트를 빠르게 탐색하거나 조건을 만족하는 부분 구간을 찾을 때 매우 유용한 알고리즘입니다.

이 글에서는 투 포인터의 개념부터 다양한 유형, 그리고 언어별(파이썬, C++, 자바, 자바스크립트) 예제 코드까지 다루며, 여러분이 투 포인터를 완벽히 이해하고 실전 문제에 적용할 수 있도록 도와드리겠습니다.

 

---

1.  투 포인터(Two Pointer)란?

투 포인터는 말 그대로 두 개의 포인터를 이용해 배열이나 리스트를 탐색하는 방법입니다. 이 두 포인터는 한 방향으로 움직이거나, 서로 반대 방향으로 이동하며 문제를 해결합니다.

투 포인터 기본 형태

1. 시작점과 끝점(start, end)을 설정합니다.
2. 각 포인터를 조건에 따라 이동시키면서 원하는 답을 찾습니다.

특히 "정렬된 배열", "특정 합을 구하는 문제", "최적 구간 찾기" 등에서 주로 활용됩니다.

투 포인터가 필요한 상황

• 정렬된 배열에서 두 수의 합을 찾을 때 (Two Sum 문제)
• 배열에서 특정 조건을 만족하는 연속 부분 구간 찾을 때
• 슬라이딩 윈도우(Sliding Window) 문제에서
• 문자열이나 배열을 빠르게 검색할 때

투 포인터를 사용할 때 주의할 점

• 배열이 정렬되어 있어야 하는 경우가 많습니다. (아니라면 먼저 정렬)
• 포인터 이동 조건을 잘못 설정하면 무한 루프가 발생할 수 있습니다.
• 인덱스 범위 초과를 항상 조심해야 합니다.

 

---

2.  투 포인터 유형 정리

유형	설명	예시 문제
양쪽 끝(start, end) 이동	정렬된 배열에서 두 수의 합 찾기	Two Sum (정렬 배열)
한 방향으로(start만 이동)	부분 합, 최소 길이 연속 부분 배열	최소 부분 배열 길이 문제
두 문자열 비교	포인터를 각각 문자열에 적용	Subsequence 문제

 

---

3.  주요 언어별 투 포인터 기본 예제

문제 예시 : 정렬된 배열이 있을 때, 합이 target이 되는 두 원소를 찾아라.

a.  Python (파이썬)

def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None

# 사용 예시
nums = [1, 2, 3, 4, 6]
target = 7
print(two_sum(nums, target))  # 출력: (0, 4)

b.  C++

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

pair<int, int> two_sum(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target)
            return {left, right};
        else if (sum < target)
            left++;
        else
            right--;
    }
    return {-1, -1};
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 6};
    int target = 7;
    auto result = two_sum(nums, target);
    cout << result.first << ", " << result.second << endl; // 출력: 0, 4
}

c.  Java (자바)

public class TwoPointerExample {
    public static int[] twoSum(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[]{left, right};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 6};
        int target = 7;
        int[] result = twoSum(nums, target);
        System.out.println(result[0] + ", " + result[1]); // 출력: 0, 4
    }
}

d.  JavaScript (자바스크립트)

function twoSum(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const sum = nums[left] + nums[right];
        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return null;
}

// 사용 예시
const nums = [1, 2, 3, 4, 6];
const target = 7;
console.log(twoSum(nums, target)); // 출력: [0, 4]

 

---

4.  마무리

• 투 포인터는 두 개의 포인터를 활용하여 배열이나 문자열을 빠르게 탐색하는 알고리즘입니다.
• 정렬된 배열, 부분 구간 합, 슬라이딩 윈도우 등에 자주 활용됩니다.
• 문제에 따라 포인터를 한 방향 또는 양방향으로 이동시켜 조건을 만족합니다.
• 다양한 문제 유형에 널리 사용되며, 효율적인 시간 복잡도를 제공합니다.

 

---