투 포인터(Two Pointers)란?
투 포인터 기법은 효율적인 알고리즘 설계를 위한 기법 중 하나입니다. 이 방법은 주로 정렬된 자료구조에서 특정 조건을 만족하는 데이터 쌍이나 서브 배열을 찾는 데 유용합니다. 기본적으로 두 개의 포인터를 사용하여 배열의 시작과 끝 또는 두 개의 다른 요소를 가리키며, 이를 통해 문제를 해결합니다.
투 포인터 기법은 여러 데이터 문제를O(n)의 시간 복잡도로 해결할 수 있게 해줍니다. 일반적으로 연속된 배열의 문제, 합 문제, 부분 배열 문제에서 많이 사용됩니다. 이 방법은 투 포인터의 위치를 조정함으로써 문제의 조건에 맞는 답을 찾도록 설계됩니다.
문제 설명: 특정 합을 갖는 부분 배열 찾기
문제: 정수 배열 nums가 주어질 때, 두 개의 수를 선택하여 그 합이 주어진 정수 target과 일치하는지 찾는 알고리즘을 작성하시오. 단, 각 요소는 단 한번만 사용할 수 있습니다. 두 수의 인덱스를 배열의 형태로 반환하시오.
예시 입력:
nums = [2, 7, 11, 15], target = 9
예시 출력:
[0, 1]
설명: nums[0] + nums[1] = 2 + 7 = 9.
문제 풀이 과정
1. 문제 이해
본 문제는 주어진 배열에서 두 수의 인덱스를 찾는 것을 목표로 합니다. 문제의 핵심은 각 수가 단 한 번만 사용될 수 있다는 점입니다. 따라서, 특정 합을 찾기 위해 조합을 만들어내는 과정이 필요합니다.
2. 접근 방법
투 포인터 기법을 통해 두 포인터를 이용해 문제를 해결할 예정입니다. 배열을 정렬하더라도 원래의 인덱스를 추적할 수 있도록 해야 합니다. 또한, 배열이 정렬되어 있으므로 두 포인터의 위치를 조정하여 최적의 솔루션을 찾을 수 있습니다.
3. 알고리즘 설계
- 배열을 정렬합니다.
- 두 포인터를 설정합니다: 하나는 배열의 첫 번째 요소를 가리키고, 다른 하나는 마지막 요소를 가리킵니다.
- 합이
target에 도달했다면 해당 인덱스를 반환합니다. - 합이
target보다 작다면 왼쪽 포인터를 오른쪽으로 이동시켜 합을 증가시킵니다. - 합이
target보다 크다면 오른쪽 포인터를 왼쪽으로 이동시켜 합을 감소시킵니다. - 위 과정을 반복하다가 두 포인터가 겹치면 종료합니다.
4. C++ 코드 구현
#include
#include
#include
using namespace std;
vector twoSum(vector& nums, int target) {
unordered_map numMap;
vector result;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (numMap.find(complement) != numMap.end()) {
result.push_back(numMap[complement]);
result.push_back(i);
return result;
}
numMap[nums[i]] = i;
}
return result; // 결괏값을 못 찾은 경우
}
int main() {
vector nums = {2, 7, 11, 15};
int target = 9;
vector indices = twoSum(nums, target);
cout << "[" << indices[0] << ", " << indices[1] << "]" << endl;
return 0;
}
5. 코드 설명
위 C++ 코드는 주어진 nums 배열을 순회하며 target 값을 만들 수 있는 두 수의 인덱스를 찾습니다. 해시맵(unordered_map)을 사용하여 시간 복잡도를 O(n)으로 유지합니다. 첫 번째 수를 선택할 때마다 그 보완 수(target - nums[i])가 해시맵에 존재하는지 확인하여, 존재한다면 두 인덱스를 결과로 반환합니다.
해시맵은 각 수를 빠르게 조회할 수 있게 해주며, 배열을 한 번만 순회하여 효율적으로 답을 찾을 수 있도록 도와줍니다.
6. 복잡도 분석
위 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(n)입니다. 해시맵을 통해 보완 수를 기록하고 이를 통해 효율적인 검색을 가능하게 합니다. 배열이 정렬되지 않은 경우가 많아 해시맵을 통한 접근이 유리합니다.
마무리
투 포인터 기법은 배열 문제에서 매우 유용하게 사용됩니다. 본 문제와 같이 정렬되지 않은 배열에서 특정 합을 만족하는 두 수를 찾는 것은 자주 등장하는 문제입니다. 알고리즘의 최적화를 위해 해시맵을 사용하는 것도 좋은 전략입니다.
다양한 문제를 풀어보며 투 포인터 기법을 익히고, 이를 다른 문제에 확장하여 응용할 수 있도록 연습해보시길 바랍니다.