투 포인터

투 포인터

1차원 배열이 있고 두개의 포인터를 이용해 원하는 값을 찾아내는 알고리즘이다.

가장 대표적은 예로는 N개의 수에서 합 M의 개수를 찾는 문제이다.

 

포인터로 사용할 s,e와 합을 저장할 S가 있다고 한다면 이론적으론 다음과 같다.

 

1. S >= M 이면 S -= A[s++]

2. e == N 이면 break

3. S < M 이면 s += A[e++]

4. S == M 이면 ans++

 

이 과정을 거쳐서 M의 개수를 찾는 방식이다.

 

그림과 같이 이해하면 다음과 같다.

 

처음은 다음과 같다. 초록색 화살표를 s, 파란색 화살표를 e라고 한다면 처음은 0에서부터 시작한다.

현재 S값이 M보다 작기 때문에 3번 과정이 수행된다.

지금 상태는 S == M인 상태이다. 그렇기 때문에 ans를 4번이 실행되고 1번이 실행된다.

지금 상태를 보면 S < M인 상태에서 e == N인 상태이다. 이때 2번의 조건에 걸리면서 종료하게 된다.

 

이를 코드로 보면 다음과 같다.

int s,e;
s = e = 0;
int sum = 0;
int ans = 0;
while(true) {
	if(sum >= M) sum -= arr[s++];
	else if(e==N) break;
	else sum += arr[e++];
	if(sum==M) ans++;
}

 

 

풀어볼 문제

http://boj.kr/2003

2003번: 수들의 합 2