코딩테스트에서 자주 등장하는 알고리즘 중 하나인 투 포인터(Two Pointer) 기법에 대해 자세히 알아보겠습니다. 본 강좌에서는 투 포인터의 기본 개념을 설명하고, 이를 활용한 실제 문제를 해결해보겠습니다.
1. 투 포인터(Two Pointer)란?
투 포인터 기법은 배열이나 리스트와 같은 데이터 구조에서 두 개의 포인터를 이용하여 효율적으로 데이터를 처리하는 알고리즘 기법입니다. 일반적으로 문제의 크기가 커질수록 불필요한 반복문을 줄이고, 시간 복잡도를 개선하는 데 효과적입니다.
- 효율성: 시간 복잡도를 O(N)으로 줄여주는 경우가 많습니다.
- 간결함: 코드가 간단해지고 가독성이 향상됩니다.
- 적용 범위: 정렬된 배열, 문자열, 서브 배열(subarray) 문제 등 다양한 상황에서 사용할 수 있습니다.
2. 투 포인터의 기본 아이디어
투 포인터는 일반적으로 다음과 같은 두 가지 방법으로 사용됩니다:
- 왼쪽과 오른쪽 포인터: 배열의 양 끝에서 시작하여 중앙으로 이동하며 조건을 만족하는 요소를 찾습니다.
- 같은 방향으로 이동: 두 포인터가 같은 방향으로 이동하면서 특정 조건을 만족할 때까지 주변 요소를 검사합니다.
3. 실제 문제: 두 수의 합
다음은 투 포인터를 사용한 실제 문제입니다.
문제 설명
정렬된 배열 numbers와 목표 합 target이 주어질 때, 두 수의 합이 목표 합과 일치하는 두 수의 인덱스를 반환하는 함수를 작성하세요. 각 입력에는 정확히 하나의 해답이 존재한다고 가정하며, 같은 요소를 두 번 사용할 수는 없습니다.
입력 형식
numbers: [2, 7, 11, 15]
target: 9출력 형식
[0, 1]예제 설명
위 예제에서 2 + 7 = 9이므로 출력은 인덱스 0과 1입니다.
4. 문제 해결 과정
투 포인터를 사용하여 이 문제를 해결해보겠습니다. 다음 단계로 진행합니다:
Step 1: 포인터 초기화
배열의 시작과 끝에 포인터를 초기화합니다. 왼쪽 포인터는 left, 오른쪽 포인터는 right로 명명합니다.
Step 2: 조건 검사
While 루프를 사용하여 두 포인터가 교차할 때까지 반복합니다. 각 반복마다 현재 포인터가 가리키는 두 수의 합을 계산하고, 이 합이 target과 일치하는지 확인합니다.
Step 3: 합 비교
- 합이
target보다 작으면left포인터를 하나 오른쪽으로 이동합니다. - 합이
target보다 크면right포인터를 하나 왼쪽으로 이동합니다. - 합이
target과 같으면 두 인덱스를 반환합니다.
Step 4: 코드 구현
function twoSum(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) {
return [left, right];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return []; // 해답이 없는 경우
}Step 5: 코드 분석
이 코드의 시간 복잡도는 O(N)이며, 공간 복잡도는 O(1)입니다. 즉, 배열을 추가로 저장하지 않고도 문제를 해결할 수 있습니다.
5. 추가 예제 및 변형 문제
이제 다른 변형 문제를 살펴보겠습니다. 주어진 배열에서 세 수의 합이 target과 일치하는 모든 조합을 찾는 문제로 응용할 수 있습니다.
문제 설명
정수 배열 numbers와 정수 target이 주어질 때, 세 수의 합이 target이 되는 모든 조합의 인덱스를 반환하세요. 결과는 중복되지 않도록 합니다.
입력 형식
numbers: [1, 2, 3, 4, 5]
target: 9출력 형식
[[0, 3, 4], [1, 2, 4], [2, 3, 4]]해결 접근 방식
이 문제를 해결하기 위해, 두 번째 포인터를 추가하여 중복되지 않는 조합을 찾는 방법을 사용할 수 있습니다. 수정된 알고리즘은 다음과 같습니다:
function threeSum(numbers, target) {
let result = [];
numbers.sort((a, b) => a - b); // 배열 정렬
for (let i = 0; i < numbers.length - 2; i++) {
let left = i + 1;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[i] + numbers[left] + numbers[right];
if (sum === target) {
result.push([i, left, right]);
left++;
right--;
while (left < right && numbers[left] === numbers[left - 1]) left++; // 중복 제거
while (left < right && numbers[right] === numbers[right + 1]) right--; // 중복 제거
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}6. 마무리
투 포인터는 배열이나 리스트를 처리하는 데 있어 매우 유용한 기법입니다. 특히 정렬된 데이터를 다룰 때 성능을 획기적으로 개선할 수 있습니다. 본 강좌에서 다룬 내용을 통해 투 포인터의 기본 개념과 활용 방법을 이해하고, 실전 문제를 해결하는 데 도움이 되기를 바랍니다.
탐색 및 조합 문제에서 투 포인터를 사용할 수 있는 다양한 상황을 계속 연습하시고, 실제 코딩 인터뷰에서도 자신 있게 활용하시기 바랍니다.
연습 문제
다음 문제를 연습해 보세요:
- 정수 배열
numbers와 정수target이 주어질 때, 가장 가까운 두 수의 합이target이 되는 인덱스의 조합을 반환하는 문제 - 문자열 내에서 유일한 문자로 이루어진 서브스트링(substring)의 길이를 반환하는 문제
이와 같은 문제를 통해 투 포인터의 이해도를 높이고, 다양한 문제를 해결하는 경험을 쌓아보세요.