[개념정리] Two pointer algorithm

 

투포인터 알고리즘 :

 

1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 두개의 포인터를 조작해서 원하는 인덱스, 값을 얻는 방법

 

 

쓰는 이유 :

 

아래와 같은 문제를 투포인터로 풀이할 수 있다.

BP로 풀게된다면 시간복잡도가 O(N^2)가 되어 시간초과가 날 수 있다.

 

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

2003번: 수들의 합 2

 

 

사용 방법 :

​

1. 포인터를 두 개 준비한다. left, right (초기에는 left=right=0) (이후 left<=right)

-> 배열을 left와 right가 가리키면 [left, right) 로 사용된다. left이상 right미만 값을 가리키는것

​

2. 조건문

-> 1. 현재의 부분합이 목표값 이상이거나 right==원소의 갯수 이면 left를 ++

-> 2. 아니면 right++

-> 3. 현재의 부분합이 목표값과 같다면 결과count++

즉 left와 right를 무조건 증가시키는 도중에 부분의 합이 정확히 목표치일때의 count를 세는 것이다.

​

​

예시 :

2003번의 2번째 예시를 예로 들어 풀이해보겠다.

​

주어진 원소의 갯수는 10개 / 이들의 연속합으로 구하고자 하는 숫자는 5

빨간색 : left

파란색 : right

-> 현재의 부분합 0 (<5) 이고 right!=10 이므로 right를 ++해준다.

​

-> 현재의 부분합 1 (<5) 이고 right!=10이므로 right를 ++해준다.

​

-> 현재의 부분합 3 (<5) 이고 right!=10이므로 right를 ++해준다.

​

-> 현재의 부분합이 6 (>5) 이니 left를 ++해준다.

​

-> 현재의 부분합이 5 (>=5) 이니 left를 ++ 해주고, 결과 count++

​

-> 현재의 부분합이 3 (<5) 이니 right를 ++ 해준다.

​

이와 같이 계속 이동시켜보자.

5 이니 count++

5 이니 count++

right가 끝에 다다랐으니 left를 ++ 해준다.

목표값 이하지만 right가 더이상 갈 수 없으므로 left ++

끝까지 다다랐으니 종료해보도록하자.

끝냈을 때 합이 5인 것의 count 는 3이다.

​

이와같이 투포인터 알고리즘을 사용할 경우 예외없이 부분합을 구할 수 있다.

​

​

코드 :

​아래의 풀이를 참조

dbstndi6316.tistory.com/140

[백준문제풀이] 2003 수들의 합 2