투 포인터와 슬라이딩 윈도우
이 두 알고리즘은 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다는 공톰점이 있습니다.
하지만 이 두 알고리즘의 차이는 부분 배열 길이의 변화 여부 입니다.
투 포인터 알고리즘은 부분 배열의 길이가 가변적이지만, 슬라이딩 윈도우 알고리즘은 부분 배열의 길이가 고정적 입니다.
투 포인터
투 포인터는 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘입니다. 여기서 중요한 것은 "연속되고 가변적인"입니다.
투 표인터 알고리즘에서는 대게 두 개의 유형이 존재합니다.
1. 2개의 포인터 변수 시작점이 배열의 시작점인 경우.
2. 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점(arr.length-1)에 위치한 경우
투 포인터로 해결해야 하는 문제에서는 모든 배열의 값들을 필연적으로 탐색하여 특정 조건을 일치시키는 개수 혹은 최저, 최대 값 등을 찾는 문제이므로 대게 '조합','백트래킹'을 떠올리기 쉽습니다. 틀린 키워드는 아니지만 '백트래킹'으로 시간을 줄여준다고 하더라도 출제나는 '투 포인터'를 의도하고 출제하기 때문에 시간 초과를 벗어날 순 없을 것 입니다.
사용 조건으로는 각 원소는 자연수이고 M 또한 자연수여야만 사용 할 수 있다. 알고리즘의 작동 방식은 우선 두 개의 포인터(start,end)를 지정한다. 이 변수는 각 각 부분배열의 첫 부분과 끝 부분을 의미한다.
Start = 0, End = 1 이여야하며 Start <= N-2, End <= N-1 까지 진행한다.
그 이후 sum[N] 배열을 준비하여 1차원 배열에 1 ... N번째까지의 합을 구한다. 두 포인터가 움직이는 규칙은 간단하다.
- sum[end] - sum[start] >= M 이라면 start를 한 칸 뒤로 옮긴다.
- 반대의 경우 end를 한 칸 뒤로 옮긴다.
