[알고리즘] 투 포인터 & 슬라이딩 윈도우

투 포인터 & 슬라이딩 윈도우 알고리즘

1차원 배열을 2회 이상 반복적으로 탐색을 해야할 경우 단순하게 한다면 O(N^2) 이상 시간 복잡도가 걸리지만 투 포인터와 슬라이딩 윈도우 알고리즘을 사용하게 된다면 부분 배열을 이용하여 시간 복잡도를 O(N)으로 줄일 수 있는 공통점이 있다.

투 포인터는 부분 배열의 길이가 변할 수 있지만, 슬라이딩 윈도우는 부분 배열의 길이가 고정적이라는 차이점이 있다.

투 포인터(Two Pointer)

투 포인터 알고리즘은 1차원 배열에서 각각 다른 원소를 가리키는 2개의 포인터를 조작해가면서 원하는 것을 얻는 알고리즘이다.

이러한 특성 때문에 투 포인터는 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 문제에 적용시킬 수 있다.

투 포인터로 해결해야 하는 문제에서는 모든 배열들의 값들을 모두 탐색하여 특정 조건을 만족하는 개수, 혹은 최저, 최대 값 등을 찾는 문제가 있는데, 이를 ‘조합', ‘백트래킹'으로 푼다면 시간 초과를 벗어날 수 없다.

투 포인터 알고리즘

투 포인터 알고리즘을 사용하기 위해서는 두 개의 포인터 변수를 사용해야 한다. 보통 (start, end) 또는 (left, right)를 사용한다.

그리고 두 가지 유형이 존재한다.

1. 2개의 포인터 변수 시작점이 배열의 시작점인 경우.
2. 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점(arr.length-1)에 위치한 경우

첫번째 유형으로 합이 T인 부분 배열을 찾는다면 알고리즘은 다음과 같다.

1. start = end = 0, sum = arr[0]으로 초기화 한다.
2. while(start≤end) 으로 반복문을 만든다.
3. sum과 T값을 비교한다.3.2. sum > T라면, sum-= arr[start] 해주고, start+1을 해줘서 부분 배열의 길이를 감소시켜서 합을 감소시켜준다.
4. 3.3. sum == T 이면 끝!
5. 3.1. sum < T 라면, end를 +1 해줘서 부분 배열의 길이를 증가 시켜주고 sum += arr[end]로 합을 증가시켜준다.

이 때 start와 end가 배열의 길이를 초과하지 않도록 조건문을 하나씩 더 추가해줘야 한다.

슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우 알고리즘은 투 포인터와 유사하지만, 부분 배열의 길이를 고정해서 탐색하는 방식이다. 투 포인터와 달리 두 개의 포인터 변수를 사용할 필요없이 고정적인 부분 배열의 크기와 한 개의 포인터 변수를 가지고 있다면 부분 배열의 양 끝을 알 수 있다.

슬라이딩 윈도우 알고리즘

1. 고정 길이 l과 시작 지점 포인터 p = 0으로 초기화한다.
2. p를 1씩 증가시키면서 (배열 길이 - l - 1 )까지 탐색한다.

슬라이딩 윈도우는 길이가 고정적이기 때문에 쉽게 구현할 수 있다.