투 포인터 [BOJ 1806] 부분합

투 포인터란? 투 포인터는 말 그대로 2개의 포인터(가리키는 위치)를 통해 알고리즘의 시간 복잡도를 최적화하는 기법입니다.

다음과 같은 리스트가 있을 때 연속된 합이 14 이상인 경우 가장 짧은 길이를 구한다고 하면 가장 단순한 방법으로는 길이가 1인 경우 ~ 길이가 N인 경우를 모두 탐색함으로 문제를 해결할 수 있습니다. 이 경우에는 O(N^2)의 시간 복잡도를 가지므로 효율적이라고 말할 수 없습니다.

투 포인터 기법을 사용한다면 해당 문제를 O(N)의 시간 복잡도 만에 해결할 수 있습니다. 투 포인트 동작 과정 목표는 연속된 합이 14 이상인 리스트의 최소 길이를 구하는 것입니다. target = 14 Left 좌표와 Right 좌표를 0으로 초기화해주고 Value에 현재 리스트의 첫 번째 값을 넣어줍니다.

이후 동작 과정은 이렇습니다. Value 값이 목표값 보다 작다면 right를 오른쪽으로 한 칸 이동시키고 right 위치의 값을 Value에 더해줍니다.

Value 값이 목...