1. 투 포인터(Two Pointers) 알고리즘이란?
투 포인터는 두 개의 포인터를 이용하여 배열이나 리스트를 탐색하는 알고리즘 기법이다.
주로 정렬된 배열에서 특정 조건을 만족하는 쌍을 찾거나, 연속된 부분 배열을 탐색하는 문제에서 사용된다.
이 방법을 사용하면 O(N^2) 복잡도의 문제를 O(N)으로 최적화할 수 있습니다.
2. 투 포인터 동작 원리
- 시작점과 끝점에서 이동
- 오름차순 정렬된 배열에서 특정 합(target)을 찾을 때 사용
- 좌측 포인터(left)는 작은 값부터, 우측 포인터(right)는 큰 값부터 이동
- 두 포인터를 조절하면서 특정 조건을 만족하는 값을 찾는다.
아래 예제를 통해 원리에 대한 설명 하겠습니다.
특정 합을 가지는 두 숫자 찾기 (Two Sum)
문제: 정렬된 배열에서 합이 9 되는 두 숫자의 인덱스를 찾는다.
입력 예시
int[] nums = {1, 2, 3, 5, 7, 10, 12};
int target = 9;
투 포인터 진행 과정
1. left(🔴)는 처음 인덱스에서 시작, right(🔵)는 끝에서 시작
2. sum을 비교하면서 작으면 left++, 크면 right--
3. sum == target 이면 정답 찾음
| 단계 | left 포인터 (🔴) | right 포인터 (🔵) | 합(sum) | 진행 방향 |
| 초기 | 🔴1 (idx:0) | 🔵12 (idx:6) | 1 + 12 = 13 | sum > target → right 감소 |
| 2 | 🔴1 (idx:0) | 🔵10 (idx:5) | 1 + 10 = 11 | sum > target → right 감소 |
| 3 | 🔴1 (idx:0) | 🔵7 (idx:4) | 1 + 7 = 8 | sum < target → left 증가 |
| 4 | 🔴2 (idx:1) | 🔵7 (idx:4) | 2 + 7 = 9 | sum == target → 정답 찾음 |
최종결과 : [1, 4] → (nums[1] = 2, nums[4] = 7)
Java 코드
- 시간 복잡도: O(N)
- 두 개의 포인터를 사용하여 선형 탐색 진행
import java.util.Arrays;
public class MainClass {
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, 5, 7, 10, 12};
int target = 9;
int[] result = twoSum(nums, target);
// 최종결과: [1, 4]
System.out.println("최종결과: " + Arrays.toString(result));
}
}3. 투 포인터 응용 예시
슬라이딩 윈도우를 활용한 부분 배열 최소 길이 찾기
문제 : 연속된 부분 배열의 합이 target 이상이 되는 최소 길이를 구하는 문제
(left 포인터를 이동하며 구간을 줄여가면서 최적 해 찾기)
입력 예시
int[] nums = {2, 3, 1, 2, 4, 3};
int target = 7;
포인터 이동 과정
| 단계 | left(🔴) | right(🔵) | 부분합(sum) | 최소 길이 |
| 초기 | 🔴2 (idx:0) | 🔵2 (idx:0) | sum = 2 | - |
| 2 | 🔴2 (idx:0) | 🔵3 (idx:1) | sum = 5 | - |
| 3 | 🔴2 (idx:0) | 🔵1 (idx:2) | sum = 6 | - |
| 4 | 🔴2 (idx:0) | 🔵2 (idx:3) | sum = 8 | minLength = 4 |
| 5 | 🔴3 (idx:1) | 🔵2 (idx:3) | sum = 6 | - |
| 6 | 🔴3 (idx:1) | 🔵4 (idx:4) | sum = 10 | minLength = 3 |
| 7 | 🔴1 (idx:2) | 🔵4 (idx:4) | sum = 7 | minLength = 3 |
| 8 | 🔴2 (idx:3) | 🔵4 (idx:4) | sum = 6 | - |
| 9 | 🔴2 (idx:3) | 🔵3 (idx:5) | sum = 9 | minLength = 2 |
최소 길이 부분 배열: [4, 3] (길이: 2)
Java코드
- 시간 복잡도: O(N)
- 슬라이딩 윈도우(Sliding Window) 방식으로 최적화
- 연속된 부분 배열을 유지하면서 최소 길이 갱신
public class MainClass {
public static int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0, minLength = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right]; // 오른쪽 포인터 확장
while (sum >= target) { // 조건을 만족하면 최소 길이 업데이트
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left]; // 왼쪽 포인터 축소
left++;
}
}
return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
}
public static void main(String[] args) {
int[] nums = {2, 3, 1, 2, 4, 3};
int target = 7;
int result = minSubArrayLen(target, nums);
System.out.println("최소 길이: " + result); // 최소 길이: 2 (부분 배열: [4,3])
}
}4. 투 포인터 알고리즘이 적합한 문제 유형
1) 정렬된 배열에서 특정 조건을 만족하는 두 수 찾기
- Two Sum 문제 (합, 차이)
- 배열에서 두 숫자의 차이가 K인 쌍 찾기
- 배열에서 곱이 특정 값을 만족하는 두 수 찾기
2) 연속된 부분 배열 문제
- 최소 길이의 부분 배열 찾기
- 가장 큰 합을 가지는 연속된 부분 배열 찾기
3) 문자열 처리 문제
- 가장 긴 중복 없는 부분 문자열 찾기
- 애너그램(Anagram) 검사
4) 백준 및 프로그래머스 관련 문제
- 백준 - 3273번: 두 수의 합, 2470번: 두 용액, 1806번: 부분합, 1644번: 소수의 연속합, 2003번: 수들의 합 2
- 프로그래머스 - 레벨 2: 구명보트, 레벨 3: 보석 쇼핑, 레벨 2: 연속된 부분 수열의 합
5. 정리
투 포인터 알고리즘은 정렬된 배열에서 최적의 방법으로 특정 조건을 만족하는 요소를 찾는 강력한 알고리즘 입니다.
- 브루트포스 대비 O(N²) → O(N)으로 성능 최적화 가능
- 슬라이딩 윈도우와 결합하여 다양한 문제 해결 가능
- 데이터 크기가 클수록 효과적인 알고리즘
위와같은 장점도 있지만, 투포인터 알고리즘은 중복된 값이 있는 경우 차가적인 고려가 필요합니다. 또한 배열이나 리스트에서는 효과적이지만 트리, 그래프, 해시맵과 같은 비선형 자료구조에서는 적용 하기 어렵다는 단점이 있습니다.
'기타 > Algorithm' 카테고리의 다른 글
| [Algorithm] 소수(Prime Number) 구하기 (0) | 2024.07.28 |
|---|---|
| [Algorithm] 숫자의 합 구하기(백준 11720번) (0) | 2024.07.27 |
