투 포인터 알고리즘이란?
투 포인터 알고리즘은 배열이나 리스트에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 데 사용되는 알고리즘이다. 이 알고리즘은 일반적으로 정렬된 배열에서 특정한 합이나 조건을 만족하는 부분 배열을 찾거나, 두 배열을 병합하는 경우에 효과적으로 사용된다.
투 포인터 알고리즘의 주요 아이디어는 두 개의 포인터를 사용하여 배열 내에서 움직이면서 원하는 조건을 찾아내는 것이다. 보통 시작점과 끝점을 나타내는 두 포인터를 사용하며, 이 두 포인터는 배열을 훑으면서 조건에 맞게 이동한다.
투 포인터 알고리즘 예시
간단한 예제로 정렬된 배열 내에서 두 수 사이의 합이 특정 값이 되는 경우(부분수열)를 찾는 예시이다.
- 시작과 끝 포인터 초기화: 배열의 시작지점에 시작과 끝 포인터를 놓는다.
- 포인터 이동: 포인터가 가리키는 두 수 사이의 합을 목표값과 비교한다.
- 합이 목표 값보다 작으면 끝 포인터를 오른쪽으로 옮긴다.
- 합이 목표 값보다 크면 시작 포인터를 오른쪽으로 이동한다.
- 합이 목표 값과 같으면 원하는 조건을 찾은 것이다.
프로그래머스(https://www.programmers.co.kr)의 level2 연속된 부분 수열의 합 문제로 간단한 코드 예시를 들어보면,
function solution(sequence, k) {
let answer = [];
let start = 0; // 시작 포인터 초기화
let sum = 0;
for(let end = 0; end < sequence.length; end++) { // 끝 포인터 초기화 및 반복문 시작
sum += sequence[end]; // 끝 포인터에 해당하는 값을 더해준다.
while(sum > k) { // 시작 포인터와 끝 포인터 사이의 부분수열의 합이 k보다 큰 경우
sum -= sequence[start]; // 시작 포인터의 값을 합에서 제외한다.
start += 1; // 시작 포인터를 오른쪽으로 옮긴다.
}
if(sum === k) { // 합이 k와 같을 경우 조건에 만족한다.
if(answer.length > 0) { // 기존에 조건을 만족하는 부분 수열이 존재하는 경우
if(answer[1] - answer[0] > end - start) { // 기존 부분 수열보다 현재 부분 수열의 길이가 더 짧을 경우
answer = [start, end]; // 현재 부분 수열로 바꿔준다.
}
} else {
answer = [start, end]; // 기존에 조건을 만족하는 부분 수열이 존재하지 않을 경우 현재 부분수열을 바로 대입해준다.
}
}
}
return answer;
}
와 같이 코드를 작성할 수 있다.