[알고리즘] 투포인터(Two pointers)와 슬라이딩 윈도우(Sliding window)

 

 예제문제는 leetcode로 리뷰할 거기도 하고, 이미 다른데서 포스팅을 많이 해 둬서 특정 문제가 아닌 기본 개념에 집중해서 포스팅을 하려고한다.

 

 투 포인터와 슬라이딩 윈도우의 기본 concept은 다음과 같다. 

 1. 배열의 특정 두 부분에 포인트를 설정한다. 해당 두 포인터의 사이는 "타겟이 있을 법한 범위"이다.

 2. 조건에 따라 해당 포인트를 옮겨가며 타겟을 찾는다.

 

 두 알고리즘의 원리는 같지만 투 포인터의 경우  포인터가 가리키는 값 두 개 자체에만 집중하기 때문에 반복문 loop마다 조건에 따라 포인트 사이의 거리가 달라질 수있지만 슬라이딩 윈도우의 경우 반복문 loop간 window사이의 교집합이 알고리즘의 핵심이기 때문에 두 점사이의 거리가 일정(/고정) 되어있다는 점이 특징이다.

 

 시간 복잡도는 두 알고리즘 모두 최악의 경우 원소 모두를 탐색하므로 O(n)이다.

투 포인터 기본 개념

1. 시작점과 끝 점을 설정한다.

2. 기준점이 타겟값과 같으면 기준점을 리턴한다.

3. 기준점이 타겟값과 다르면 시작점 또는 끝점을 이동하여 윈도우 크기를 변화시키면서 기준점 또는 기준 영역을 변화시킨다.

4. 종료조건:

    - 끝 점을 배열의 길이로 설정한 경우: start > end

    - 끝 점을 0으로 설정한 경우: end == len(배열)

슬라이딩 윈도우 기본 개념

 슬라이딩 윈도우로 해결해야하는 문제들은 윈도우의 크기(k)가 주어진다. 고정 크기의 윈도우가 1씩 이동하면서 첫 번째 원소를 제외한 나머지 원소는 모두 공유하기 때문에 원소 하나만 고려하면 된다는 것이 해당 알고리즘의 핵심적인 부분이다.

    1. 시작 윈도우는 배열의 첫 번째 원소부터 k-1번째 원소이다.

    2. 배열을 0부터 -k까지 인덱스 i로 순회하면서 배열의 i번째 원소(직전 loop에서 윈도우의 첫 번째 원소)와 i+k번째 원소를 활용하여 타겟값을 찾는다.

    3. 종료 조건

         - sliding window가 배열의 끝에 도달했을 경우, 즉 (sliding window의 시작 index == len(배열)-1-k) or (sliding window의 끝 index == len(배열)-1)

 

 최대 부분합 문제를 예로 많이 드는데, [2,3,4,5,6,7]에서 연속된 세 원소의 부분 배열을 비교해야하는 문제라면, 완전 탐색(brute force)기법이라면 각 loop 마다 세번씩 더하는 작업을 해야하지만( window = arr[i] + arr[i+1] + arr[i+2] ) 슬라이딩 윈도우 기법을 사용하면 i 를 빼고 i+3을 더하면 된다 ( window = window - arr[i] + arr[i+3] ).

 

 혹시 위 문단만보고 어차피 연산 작업은 같은 거 아닌가? 라는 생각이 든다면 알고리즘 문제는 항상 수가 엄청 클 때를 생각해야한다는 점을 잊지말자. 위에서는 비교해야하는 부분 배열의 길이가 3이었지만 만약 부분배열의 길이가 10만이라면 brute force의 경우 arr[i]부터 arr[i+99,999]를 더하는 코드를 구현해야한다. 다 적을 수는 없을 것이므로 for문으로 구현할 것이고, 결론적으로 sliding window는 중첩 for문을 단일 for문으로, 시간 복잡도를 O(kn)에서 O(n)으로 단축시키는 효과를 낸다.