[알고리즘] Two Pointers 알고리즘이란?

투포인터 알고리즘이란?

투포인터 알고리즘 또는 슬라이딩 윈도우라고 부른다. 

1차원 배열이 있고, 배열에서 각자 다른 원소를 카리키고 있는 2개의 포인터를 조작하면서 원하는 값을 얻는 방법이다.

설명

1. 포인터 2개를 준비 , start_index , end_index

2. 항상 start_index <= end_index를 만족해야 한다.

3.2개의 포인터는 현재 부분 배별의 시작과 끝을 가리키는 역할

 

과정

 

초기상태

원하는 값 N=5 

부분 배열의 합이 5보다 작다. 따라서 e+1를 해준다.

 

하지만 아직도 부족하다. e+1추가

e+1추가

 

이번에는 N값보다 합이 크기 때문에 S+1

 

합과 N값이 같다. count +1 해주고 e+1

 

이후 과정은 e포인터가 마지막에 도달 할 때 까지  반복

 

 

시간복잡도

두개의 포인터가 일차원 배열 위를 움직인다. 그리고 end포인터가 배열의 마지막에 도달할 경우 종료최악의 경우에도 start와 end가 둘 다 배열의 마지막으로 오는 경우로 O(2n)이다.따라서 투포인트 알고리즘의 시간복잡도는 O(N)

 

참고문제)

2018번: 수들의 합 5

해설)

[백준] 2018번 연속된 자연수의 합 구하기