투포인터 알고리즘(Two Pointers Algorithm) 또는 슬라이딩 윈도우(Sliding Window)라고 부른다. 이번에 20년도 상반기 라인 공채 코딩 테스트에서 이를 활용할 만한 문제가 나왔다. 그래서 예전에 정리했던 내용을 떠올리며, 다시 정리하려 글을 쓴다.
알고리즘 문제를 풀다 완전탐색으로 해결하면 시간 초과가 나는 문제가 종종 있다. 어떻게 풀어야 하는지 그 당시 검색했을 때, 투 포인터 알고리즘 이 대안이었다.
1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태이다. 이때문에 투포인터 알고리즘이라 부른다.
N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 모든 경우의 수를 다 테스트 해보면 구간 합을 구간 배열로 O(1)만에 구한다고 해도 경우의 수는 O(N^2)이 된다. 따라서 문제를 풀 수 없다. N의 최대 범위가 너무 크기 때문이다.
이 문제에서 각 원소는 자연수이고 M 또한 자연수인데, 이 조건이 성립하면 사용할 수 있는 알고리즘은 다음과 같다.
- 포인터 2개를 준비한다. 시작과 끝을 알 수 있도록 start, end 라고 한다.
- 맨 처음에는 start = end = 0이며, 항상 start<=end을 만족해야 한다.
- 2개의 포인터는 현재 부분 배열의 시작과 끝을 가리키는 역할을 한다.
s=e일 경우 그건 크기가 0인, 아무것도 포함하지 않는 부분 배열을 뜻한다. 다음의 과정을 s < N인 동안 반복한다.
- 만약 현재 부분합이 M 이상이거나, 이미 e = N이면 s++
- 그렇지 않다면 e++
- 현재 부분합이 M과 같으면 결과 ++
쉽게 이해하자면, start와 end 를 무조건 증가시키는 방향으로만 변화시켜가면서 도중에 부분 배열의 합이 정확히 M이 되는 경우를 세는 것이다.
Ex) M = 5인 경우를 살펴보자.
초기 상태이며, 빨간색 포인터 : start, 파란색 포인터 : end이다. S : 합.
end가 뒤로 움직일 때는 새로 포함한 원소를 S에 더하고, start가 뒤로 움직일 때는 새로 넘긴 원소를 S에서 빼는 식으로 현재 [start, end)의 합 S를 매번 쉽게 구할 수 있다.
처음에는 이렇게 end만 증가하게 된다. S가 계속 M보다 작기 때문! 마지막엔 S>=M이 되었으므로 아래와 같다.
start를 한 칸 옮겼는데, 동시에 S = 5인 경우를 만났다. 이때 결과를 1 증가시켜 준다.
이런 식으로 포인터들이 움직이게 된다. 여기서 2번째로 S = 5인 지점을 만났으므로 결과를 1 증가시켜 준다.
그 직후, start가 1 증가하면서 start = end인 경우가 나온다.
계속 가다 보면 세 번째로 S = 5인 지점을 만난다.
그 이후 조건에 맞춰 포인터를 증가시키다 보면, end가 배열 끝을 가리키게 되어 더이상 증가할 수 없는 상태가 된다.
그렇게 되면 그냥 start만 증가시켜 가다가 start 역시 배열 끝에 다다르면 종료해도 되고, 그냥 그 자리에서 루프를 끝내버려도 된다. 이렇게 해서 S = 5인 경우는 3개 발견되었다.
- 시간 복잡도
- 이 알고리즘은 매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 있고, 각 포인터가 N번 누적 증가해야 알고리즘이 끝난다. 따라서 각각 배열 끝에 다다르는데 O(N)이라서 합쳐도 O(N)이 된다.
- 추천 문제(백준 기준)
- 2003 : 수들의 합
- 1644 : 소수의 연속합
- 1806 : 부분합
- 2230 : 수 고르기
- 1484 : 다이어트
- 2038 : 골룽 수열
- 2531 : 회전 초밥
- 2096 : 내려가기
- 2293 : 동전1