[알고리즘] 투 포인터

1. 개념

두 개의 포인터를 사용하는 알고리즘, 보통 left와 right, start와 end 등으로 정한다

 

2. 투 포인터 이동 원칙

• 문제마다 이동 원칙은 달라짐
• 대체로 수가 차례대로 정렬되어 있을 때 적용

1) start와 end가 같이 처음부터 시작

sum은 start부터 end까지의 합을 의미함

sum < N

아직 합이 주어진 수 보다 작으니 end를 증가시키고, 그 end를 sum에 더해서 다시 start 부터 end까지의 합을 구해봄

• end++;
• sum = sum + end

sum > N

주어진 수 보다 합이 더 커졌으니  이때의 start부터 end는 정답이 될 수 없는 범위인 것. 그러니 범위의 변경이 필요. 그런데 end를 증가시키면 소용이 없음. 어차피 더 커지기만 하니까. 그래서 sum에서 start를 빼서 start를 변경하기 위한 준비를 하고, start를 1 증가해서 범위를 바꿔봄.

• sum = sum - start_index;
• start_index++;

sum == N

주어진 수와 합이 같아짐. 그러니 정답을 증가시켜줌. 정답인 게 나왔으니 범위 변경이 필요함. end를 증가시키고 그 end를 sum에 더해줌. 이렇게 하면 당연히 sum이 N보다 커지지만 이건 다음 차례에서 해결가능하니 신경쓸 필요 없음.

• answer++;
• end++;
• sum = sum + end;

이렇게 하다가 end가 N이랑 같아지면 더 이상 할 게 없다는 것이니 종료함

2) start와 end가 양쪽 끝에서 시작

sum은 양쪽 start와 end가 가리키는 것의 합을 의미

sum < N

아직 합이 주어진 수보다 작으니 작은 걸 더해서 같아지는지 확인을 해야 함. 그러니 start의 인덱스를 늘리고 sum을 다시 계산함

• start++;

sum > N

합이 주어진 수보다 크니 큰 거보다 약간 작은 큰 걸 더해봐야 함. 그러니 end의 인덱스를 줄이고 sum을 다시 계산함

• end--;

sum == N

합이 주어진 수랑 같으니 답을 1 증가시키고, start의 인덱스는 증가시키고 end의 인덱스는 감소시켜서 새로운 쌍을 찾아서 sum을 다시 계산함

• start++;
• end--;

start와 end가 같아질 때까지 반복

3. 특징

• O(N)의 시간 복잡도를 가짐

4. 관련 문제

백준 2018

[Silver V] Title: 수들의 합 5, Time: 284 ms, Memory: 17728 KB -BaekjoonHub · Lee-Min-Jung/coding_test_practice@cb2184a

백준 1940

[Silver IV] Title: 주몽, Time: 204 ms, Memory: 16464 KB -BaekjoonHub · Lee-Min-Jung/coding_test_practice@f85de16

백준 1253