💡 투 포인터 & 슬라이딩 윈도우
두 알고리즘의 공통점은 1차원 배열(선형 공간)을 반복적으로 탐색할 때, 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다.
비슷하면서도 다른 이 두 알고리즘의 차이점은 부분 배열 길이의 변화 여부이다.
🚀 투 포인터
1차원 배열에서, 가변적인 크기의 부분배열을를 조작하며 원하는 것을 얻는 형태의 알고리즘
이 때, 2개의 포인터는 부분배열의 시작과 끝을 가리킨다.
문제에서 주어진 배열이 연속된 부분배열을 이용하여 문제를 해결하는 것이 아니면 투포인터 알고리즘을 이용할 수 없다.
모든 배열의 값을 검사하여 "특정 조건"을 만족시키는 개수, 최저, 최대를 찾는 문제이므로 보통 조합이나 백트래킹을 떠올려 문제를 풀게 된다.
이 때, 투 포인터를 의도하고 출제된 문제일 경우 100% 시간초과를 겪게 된다.
투 포인터 알고리즘의 유형은 크게 두 가지가 있다.
1. 2개의 포인터 변수 시작점이 배열의 시작점인 경우.
2. 정렬된 배열 안에서, 2개의 포인터 변수가 각각 시작점과 끝점에 위치한 경우.
대표 문제 :
www.acmicpc.net/problem/2003
www.acmicpc.net/problem/3273
🚀 슬라이딩 윈도우
투 포인터와 유사하지만, 부분 배열의 크기가 고정적인 알고리즘
처음과 끝을 가리키느 포인터가 동시에 같이 움직이게 된다.
이름 그대로 고정된 윈도우가 슬라이딩 하는 것 처럼 움직인다.
투 포인터와 가장 다른 점은,
투 포인터는 부분 배열의 크기가 가변적이기 때문에 2개의 포인터 변수가 필요한 반면,
슬라이딩 윈도우는 부분 배열의 길이가 고정적이므로 포인터 변수가 2개일 필요가 없다.
슬라이딩 윈도우를 구현하기 위해서는 보편적으로 deque를 사용하며 요소를 순회한다.
대표 문제 :
www.acmicpc.net/problem/10025
www.acmicpc.net/problem/2075
🍕