투 포인터
1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 형태를 투포인터 알고리즘이라고 한다.
대표적인 문제
N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하는 문제.
모든 경우의 수를 다 테스트해 본다면, 구간 합을 구간합 배열로 O(1)만에 구한다고 해도 경우의 수가 이미 O(N^2)라 통과할 수 없다.
각 원소는 자연수이고, M 또한 자연수일 때 사용할 수 있는 알고리즘이 투 포인터다.
- 포인터 2개를 준비하고, 시작과 끝을 나타낼 수 있는 start, end라고 칭하자
- 처음에는 start, end 모두 0부터 시작하며, 항상 start<=end를 만족해야 한다.
- 이 두개의 포인터는 현재 부분 배열의 시작과 끝을 가리키는 역할을 맡는다.
즉, start = end일 경우에는 크기가 0. 아무것도 포함하지 않는 부분 배열을 뜻한다.
아래의 과정을 start < N 일동안 반복해준다.
- 현재 부분합이 M 이상이거나, end = N 이면 start +1
- 그렇지 않다면 end + 1
- 현재 부분합이 M과 같다면 count + 1
그림 출처 : https://m.blog.naver.com/kks227/220795165570
초기 상태. end가 움직이면 새로 포함된 원소를 S에 더하고, start가 움직이면 새로 넘긴 원소를 S에서 빼는 방법으로 [start, end]의 값을 쉽게 구할 수 있게 된다.
S가 M보다 작기때문에 end가 계속 증가한다. 마지막에는 S가 M값을 넘었기 때문에
start가 한칸 옮겨지게 된다. 이 때, S = 5를만족하는 경우를 찾았고, count++해준다.
이런 식으로 포인터들이 움직인다.
쭉 움직이다가 end가 배열 끝을 가리키게 되어 더 이상 증가할 수 없는 상태가 된다.
start만 계속 증가시키다가 start도 배열끝에 다다르면 종료해도 되고, 그 자리에서 루프를 끝내도 무방하다.
투 포인터의 시간복잡도는 O(N)
투포인터와 비슷한 알고리즘으로 슬라이딩 윈도우라는 유형의 테크닉이 존재한다.
슬라이딩 윈도우
마치 창문을 한쪽으로 밀면서 문제를 푸는 것과 모양새가 유사해서 붙여진 이름이다.
투 포인터처럼 구간을 훑으면서 지나간다는 공통점이 있지만, 슬라이딩 윈도우는 항상 구간의 넓이가 동일하다는 차이점이 있다.
