[알고리즘] Two Pointers (투 포인터) / Sliding Window (슬라이딩 윈도우)

Two Pointers (투 포인터) / Sliding Window (슬라이딩 윈도우)

 

 

 

1. 투 포인터

 

투 포인터란 1차원 배열에서 배열을 가리키고 있는 2개의 포인터를 조작하여, 원하는 값을 얻는 알고리즘이다.

 

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

예를 들어, [문제 : 수들의 합2] 에서 우리는 N개의 수열에서 특정 구간의 합이 M이 되는지를 알고싶다. 

단순히 모든 경우의 수를 다 구하면 가능은 하지만, 경우의 수가 O(N^2)이라 원하는 시간 내에 불가능 할 것이다. 

 

 

이런 경우, 사용되는 것이 투 포인터이다. O(N)

먼저, 포인터 2개를 잡는다. (start, end)

 

 

처음에 start와 end는 둘 다 0에서 시작한다. 우리의 현재 sum의 값과 우리가 찾는 M값을 비교하여 start와 end 포인터를 옮겨주면 된다. 단, start는 항상 end보다 작거나 같다 (start <= end) 

 

 

 

1) start < N 보다 작을 때

2) 만약 현재 sum의 값이 M보다 크면,

 

 

sum에서 현재 start 위치 값을 빼주고 start를 한 칸 앞으로 이동한다.(start++)

 

 

 

3) end가 N에 도달하면 while문을 빠져나온다.

 

 

 

4) sum이 M보다 작으면

 

sum에 현재 end 위치 값을 더해주고 end를 한 칸 뒤로 이동한다. (end++)

 

 

 

5) sum이 M과 같으면 count를 해준다.

 

 

while(start < N) {
    if(sum >=M) sum -= arr[start++]; // sum이 M보다 커졌을 때, 새로운 현재 값을 빼주고, start를 한칸 앞으로 이동한다. 
    else if(end == N) break;
    else sum += arr[end++]; //(sum이 M보다 작을 떄) sum에 새로운 현재 값을 더해준 후, end 포인터를 한 칸 이동
           
    if(sum == M) answer++; // sum이 M과 같은 값일 때 
}

 

 

 

 

2. 슬라이딩 윈도우

 

슬라이딩 윈도우는 투 포인터와 유사하다.

 

차이점은 투 포인터는 두 개의 포인터를 이용해서 유동적인 구간의 양 끝의 기준으로 세운다면, 슬라이딩 윈도우는 구간의 넓이가 동일하여 포인터가 두 개가 없어도 된다. 

 

 

구간이 일정하기 때문에, 한 칸씩 앞으로 이동하면 겹치는 영역이 존재한다. 그래서 구간의 합이나 구간에서의 최솟값 등을 구할 때, 새로 영역으로 들어오는 값(+)과 그 전에 영역에 있었던 값(-)만 체크해주면 된다.

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

[문제 : N번째 큰 수]에서도 N이라는 고정 크기가 있기 때문에, 그 고정 크기를 기준으로 우선순위큐에 있는 N번째 숫자와 새롭게 들어오는 값만 체크를 해주면 된다. 

 

 

 

 

3. 참고 문제

1) [백준] 수들의 합2

https://void2017.tistory.com/162

[백준] 2003 수들의 합2

 

2)[백준] 부분합

https://void2017.tistory.com/163

[백준] 1806 부분합

 

3)[백준] N번째 큰 수

https://void2017.tistory.com/334

[백준] 2075 N번째 큰 수