[알고리즘] 투포인터

투포인터란?

- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

- 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬의 counquer영역의 기초가 되기도 함

 

 

특정한 합을 가지는 부분 연속 수열 찾기

투포인터의 대표적인 알고리즘 문제

어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제

 

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스를 가리키도록 한다

2. 현재 부분 합이 M과 같다면 카운트한다.

3. 현재 부분합이 M 보다 작다면(sum < M) end를 1 증가시킨다. ( end++ )

4. 현재 부분합이 M 보다 크거나 같다면 (sum >= M) start를 1 증가시킨다. ( start++ )   

5. 모든 경우를 확인할 때까지 2-4번을 반복한다.

 

그림으로 알아보기

M =5 

int arr [] = {1,2,3,2,5}

 

[초기단계]

시작점과 끝점이 첫 번째 인덱스를 가리키도록 한다

- 현재 부분의 합 1

- 현재 카운트 0

 

[Step1]

이전 단계에서 부분합이 1 -> end 증가시킨다

- 현재 부분의 합 3

- 현재 카운트 0

 

[Step2]

부분합 3 -> end 증가

- 현재 부분 합 6

- 현재 카운트 0

 

[Step3]

부분합 6 ( 5가 넘었기 때문에 ) Start 1 증가

- 현재 부분의 합 5

- 현재 카운트 1

 

[Step1 ~ Step3 반복]

 

[마지막]

 

코드

int sum = 0, start = 0, end = 0, count = 0;

while (true){
    if(sum >= num){ //합이 num 보다 크거나 같다면
        sum -= arr[start++]; // 값을 빼주고 start++
    }else if(end == num){ //end가 맨 끝에 도착했을 경우
        break; //반복문 끝냄
    }else { //합이 num 보다 작다면
        sum += arr[end++];
    }

    if(sum == num){ //sum이 num 과 일치 한다면
        count++; // count증가
    }
}

 

 

시간 복잡도 O(N)

매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 각 포인터가 n번 누적 증가해야 알고리즘이 끝남

각각 배열 끝에 다다르는데 O(N)이라 둘을 합쳐도 여전히 O(N)

 

---

참고 

https://butter-shower.tistory.com/226