투포인터

 

 

오늘은 수들의 합2에서 맞닥뜨린 투포인터 알고리즘에 대해 기록해보고자 한다.

 

2003번: 수들의 합 2

 

 

---

1. 투포인터는 어디에 쓰일까?

---

 

투포인터가 쓰이는 대표적인 예제로는 [특정한 합을 가지는 부분 연속 수열]을 찾을 때이다. 나는 슬라이딩 윈도우랑 쓰임새가 많이 헷갈렸다.

 

출처 : https://ji-musclecode.tistory.com/37

 

 

두 알고리즘의 차이는 투포인터는 구간의 너비가 조건에 따라 유동적으로 변하고, 슬라이딩 윈도우는 구간의 너비가 고정되어 있다는 것이다.

 

 

수들의 합2 문제는 고정된 구간의 너비를 갖지 않기 때문에 투포인터를 써야하는 문제였다. 슬라이딩 윈도우로 풀었더니 2%에서 바로 틀려버렸다 ㅎㅎ

 

 

---

2. 투포인터 알고리즘

---

 

 

투포인터 알고리즘은 S 시작점 하나를 기준으로 End가 목표 값을 이루기위해 어느 지점까지 움직일 수 있냐를 보는 것이다. 만약 목표값(M)이 10000이라고 한다면, Start(S) = 0번 인덱스 기준으로 End(E)는 2번 인덱스까지 가서 멈출 것이다.

 

 

왜냐하면 목표값(M) = 10000이 넘었기 때문이다. 목표값이 넘게되면 그제서야 Start(S)의 index를 한 칸 움직여 Sum에서 제해준다.

 

 

Start(S)를 움직이다보면 Sum = 10000지점에 닿은 것을 볼 수 있다. 우리의 목표값(M)과 같으면 result를 1개 up해주면 된다.

 

 

---

정리해보자면

1) 특정시작점(S)에 대해 끝점(E)을 1칸씩 움직이며 sum을 해준다. 이 과정을 목표값(M)보다 sum이 작을 때까지 해준다.

2) 목표값(M)보다 sum이 커졌다고 하면, 시작점 S를 전진한다.

3) 그러다가 sum이 목표값(M)과 같아졌다면 결과값에 1을 추가한다.

---

 

위에서 설명한 과정을 아래 코드로 구현한 것이다.

 

int N = 5;
int M = 10000;

int E = 0; //끝 포인터

int sum = 0;
int result = 0;

//1 ≤ N ≤ 10,000
for(int S=0; S<N; S++){ //시작 포인터
 
	while(sum<M && E<N){
		sum += numberList[E];
		E++; //마지막에 E++를 해주기 때문에 E<=N해주면 안됨
    }
            
	if(sum==M) result++;
    
	//while에서 나온 이상(커서 나왔으니까) S를 무조건 전진해야함
	sum -= numberList[S];

}

 

 

---

 

 

끝!