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

알고리즘 설명 출처: https://m.blog.naver.com/kks227/220795165570

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

 

투포인터 혹은 스라이딩 윈도우 기법은 연속적인 구간의 합이나 경우의 수를 구할때 매우 유용하다.

처음에 두개의 포인트 P1,P2를 설정하고 예를들어 배열의 구간 합이 특정 값을 만족할때  그 값을 만족하는 구간의 수를 구하는 문제가 있다. 이떄 배열이 모두 양수라고 가정을 하면 p2가 커질수록 합은 계속 증가하게 된다. 그래서 만약 합이 커지다가 특정 수를 초과하게되면 이제 반대로 p1값을 증가시키게된다. 왜냐하면 p1이 증가할수록 p1 p2가 포함하고 있는 구간의 범위가 줄어들기때문에 구간의 합도 작아지게된다. 

 

좀더 자세히 알고리즘 순서를 적자면 (순서가 매우 중요하다!)

 

1. 초기 p1,p2,sum,cnt(경우의 수) 0으로 설정 , 구간합 기준m설정

2. while(true)안에 넣기

3-1. 만약 sum이 m보다 크거나 같다면 sum-=arr[p1]을 한 후에 p1++로 카운트를 하나 올린다.

   2. 아니고 만약 p2==n이라면 (p2가 배열의 마지막 인덱스인n-1 까지 찍고 그다음인 n에 도달했다면 반복문을 탈출

   3. 만약 sum이 m보다 작다면 sum+=arr[p2]을 한 후에 p2++로 카운트를 하나 올린다.

4. 만약 sum==m이라면 cnt카운트값을 증가시킨다.

 

만약 3-1,3-2의 순서가 바뀐다면 그 전상황에서 p2를 카운트시켜 값이 증가했는데 단지 도착점에 도달했다는 이유때문에 그때 sum이 m보다 크거나 같아서 아직 p1을 더 올려가며 cnt값을 증가시킬 수 있는데 이것을 더해주지 못하고 종료하게 된다. 따라서 위와같은 순서를 반드시 지켜줘야 투포인터 알고리즘이 정상적으로 작동하게 된다.

 

투포인터 알고리즘 예제

백준: 2003 수들의 합/ 출처: https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

소스코드

 

그밖에도 투포인터 알고리즘과 관련된 문제

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

7453번: 합이 0인 네 정수

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

2143번: 두 배열의 합

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

1806번: 부분합