Two pointers
투 포인터
두 위치를 움직이며 필요한 조합을 찾아요
합이 12인 서로 다른 두 위치를 찾아요
목표 합12
두 값의 합1 + 10 = 11
현재 위치비교 대상확인한 값
예제 코드
C++
<vector>std::vector<int> pair_sum(const std::vector<int>& a, int target) { int left = 0; int right = static_cast<int>(a.size()) - 1; while (left < right) { int total = a[left] + a[right]; if (total == target) return {left, right}; if (total < target) { ++left; } else { --right; } } return {};}Python
def pair_sum(a, target): left, right = 0, len(a) - 1 while left < right: total = a[left] + a[right] if total == target: return [left, right] if total < target: left += 1 else: right -= 1 return []시작하기
양 끝에서 시작해요
서로 다른 두 값의 합이 12이 되는지 찾아요. 배열은 오름차순이어야 해요.
사용 조건
정렬된 배열에서 목표 합을 만드는 서로 다른 두 위치를 찾는 예제를 살펴봐요. 투 포인터는 두 인덱스를 관리하는 여러 풀이 방법의 이름이에요.
먼저 알아두면 좋아요
정렬된 배열과 조건문을 알고 시작해요. 이 예제의 두 포인터는 양 끝에서 안쪽으로 움직여요.
동작 원리
양 끝의 두 값을 더해 목표와 비교해요. 합이 작으면 왼쪽을 오른쪽으로, 합이 크면 오른쪽을 왼쪽으로 옮겨요.
정렬되어 있으므로 옮긴 방향에서 합이 어떻게 달라질지 판단할 수 있어요. 두 포인터가 만나면 서로 다른 두 위치를 고를 수 없어 끝나요.
- 시간
- O(n) · 이미 정렬된 입력을 기준으로 해요
- 추가 공간
- O(1) · 두 인덱스를 관리해요
주의할 점
- 이 양끝 탐색은 정렬된 배열을 전제로 해요. 원래 인덱스가 필요하면 정렬할 때 따로 기억해요.
- 이 예제는 한 쌍만 찾아요. 모든 쌍의 개수나 중복 처리는 별도로 설계해야 해요.