투 포인터(백준 알고리즘 1644번)

♣ 투 포인터

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

시작점과 끝점 두 개의 점으로 접근할 데이터의 특정 범위를 표현할 수 있다. 

 

*대표적인 문제: 특정한 합을 가지는 부분 연속 수열 찾기

- n개의 자연수로 구성된 수열이 있다

- 합이 m인 부분 연속 수열의 개수를 구한다

- 수행 시간 제한은 O(N)이다. 

위의 수열에서 합이 5인 부분 연속 수열을 구하려면 경우의 수가 3가지이다. (2, 3), (3, 2), (5)

수열의 모든 구성 요소에 대해 요소를 하나씩 더하는 완전탐색을 할 경우 걸리는 시간이 O2이 되어 시간 초과가 난다. 

해결 방법은 아래와 같다. 

 

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

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

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

4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다. 

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

 

시작점과 끝점에 첫 번째 원소의 인덱스인 0을 넣는다. 현재의 부분합은 1이므로 카운트는 0이다. 

아직 부분합이 5에 도달하지 못했으므로 end를 1 증가시킨다. 그러면 start=0, end=1이므로 수열의 0번째, 1번째 원소에 두 번째 수인 2를 더한다. 

첫 번째 원소에서는 부분합이 3, 두 번째 원소에서는 부분합이 2이다. 여전히 5보다 부분합이 작으므로 end를 1 증가시킨다. start=0, end=2 이므로 수열의 0~2번째 원소에 데 번째 수인 3을 더한다. 

첫 번째 원소에서 부분합이 6, 두 번째 원소에서 부분합이 5, 세 번째 원소에서 부분합이 3이다. 첫 번째 원소와 두 번째 원소의 부분합이 5 이상이므로 start를 2 증가시킨다. 또한 두 번째 원소에서 부분합이 5이므로 카운트를 1 증가시킨다. start=2, end=2 이므로 첫 번째와 두 번째 원소는 제외하고 세 번째 원소부터 다시 부분합을 구하게 된다. 

현 단계에서 세 번째 원소의 부분합은 3이고, 5보다 부분합이 작으므로 end를 1 증가시킨다.  start=2, end=3

세 번째 원소의 부분합이 5, 네 번째 원소의 부분합이 2이다. 카운트를 1 증가시키고, start도 1 증가시킨다.  start=3, end=3

네 번째 원소의 부분합이 2이므로 end를 1 증가시킨다. start=3, end=4. 네 번째 원소의 부분합이 7, 다섯 번째 원소의 부분합이 5이다. 카운트를 1 증가시킨다. 또한 네 번째 원소의 부분합이 7이기 때문에 start를 1 증가시킨다. 

 

 

♣ 백준 알고리즘 1644번

 

 

 

♣ 문제 풀이

step1. 자연수에서 소수 골라내기

에라토스테네스의 체 알고리즘을 이용하여 소수를 골라낸다. 

count는 더해서 목표값이 되는 경우의 수를 체크하는 변수이다. 

 

step2. 투 포인터 알고리즘 사용하여 목표값이 되는 경우의 수 구하기 

 

 

투 포인터 start와 end의 값을 0으로 설정한다. 정렬된 소수를 따라가면서 더해지는 결과를 저장할 리스트를 total로 정의한다. 

 

while문을 보면 end와 start의 순서가 바뀌어 있는데 위에서 설명한 투 포인터 알고리즘에서처럼 end가 start의 역할을, start가 end의 역할을 하도록 구성하였다.  위의 while문을 실행하면 다음과 같은 결과가 나온다. 

 

처음에 end=0이므로 for문의 범위는 0이상, 1미만이다. 따라서 i는 0만 될 수 있다. 

total[0] += numbers[0] 이므로 total[0]은 첫 번째 소수인 2를 더한 값으로 변한다. 만약 total[0]을 더한 값이 목표값인 n과 같다면 count에 1을 더한다. 그런데 소수를 더할 때, total 값이 목표값인 n을 넘는다면 더 이상 해당 index에 해당하는 total을 신경쓸 필요가 없다. 따라서 total[i]>=n 일 때 new_end에 1을 더한다 .이렇게 for문이 끝나면 numbers의 다음 소수를 각 total 값에 더해야 하므로 start에 1을 더한다. 또한 end값을 new_end값으로 바꾸어서 total[i]가 목표값을 달성한 경우를 제외한다. 

 

end=0, start=1 (total[0]은 2로, 목표값인 20을 만족시키지 못했기 때문에 end는 여전히 0이다. 

for문에서 범위는 0이상, 2 미만이다. 따라서 total[0]과 total[1]에 numbers[1]의 값을 더해야 한다. 두 번째 소수는 3이므로

total[0] = 5, total[1] = 3 

 

이런 방식으로 쭉 수를 더해가면서 total 리스트를 완성한 후, 마지막으로 count를 출력한다. 

n= 20인 경우, for문이 끝날 때마다 total 리스트를 출력하면 아래와 같은 결과가 나온다. 

소수를 더해가는 과정에서 딱 20이 되는 경우가 존재하지 않으므로 count는 0이다. 

 

♣ 참고자료

투 포인터

https://freedeveloper.tistory.com/393

[이것이 코딩 테스트다 with Python] 39강 투 포인터