투 포인터와 슬라이딩 윈도우

투 포인터

보통 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제풀이 전략

투 포인터는 주로 정렬된 배열을 대상으로 하여, 2개의 포인터가 좌우로 자유롭게 움직이며 문제를 풀이함

 

시간복잡도

매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 각 포인터가 n번 누적 증가해야 알고리즘이 종료

=> 각각 배열 끝에 다다르는데 O(N 이라 둘을 합해도 여전히 O(N)

 

 

슬라이딩 윈도우

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘

 

투 포인터와 비슷하지만 일반적으로 고정 사이즈 윈도우를 사용하는 경우를 슬라이딩 윈도우로 따로 구분한다.

또한 주로 정렬된 배열을 대상으로 하는 투포인터와 달리 슬라이딩 윈도우는 정렬 여부에 관계없이 활용된다.

 

 

 

 

투 포인터의 경우 윈도우 사이즈가 가변적이며 좌우 포인터가 자유롭게 이동할 수 있다.

슬라이딩 윈도우는 위 그림에서는 정렬되어있지만 [3,1,5,4,2]와 같은 정렬되지 않은 배열에서도 적용이 가능하다.

윈도우 사이즈는 고정이며 좌 또는 우 한쪽 방향으로만 이동한다.