투 포인터 알고리즘: 리스트에서 특정한 합이나 패턴 찾기

투 포인터 알고리즘이란?

주로 배열이나 리스트에서 두 개의 포인터를 사용하여 문제를 해결하는 기법

이 알고리즘을 사용하면 선형 시간 복잡도 O(N)으로 동작하며, 정렬된 배열 또는 리스트에서 특정한 합이나 패턴을 찾는 문제에 효과적으로 사용된다

 

예시?

예시는 이전에 백준 알고리즘 1644번: 소수의 연속합 문제에 사용되었던 투 포인터 알고리즘을 사용한 풀이에서 예시를 들어 설명하도록 하겠다

문제에 대한 설명은 아래 참고 링크에 올라온 글을 참고하면 좋을 것 같다

 

이 문제의 경우, 소수들의 연속적인 합이 몇개가 있는지 출력하는 문제이다

target number가 41인 경우를 예를 들어 설명하자면,

먼저 에라토스테네스의 체 알고리즘을 사용하여 41까지의 소수를 primes 배열에 저장할 것이다

 

그 후 현재의 sum이 target number보다 작으므로 end의 인덱스에 해당하는 수들을 sum에 더해주고, end를 1씩 올려준다

해당 과정을 반복하다 보면

end가 6으로 올라갔을 때,

primes[0] ~ primes[5] 까지의 합이 41(target number와 같아지는)이 되는 지점이 등장하고 count를 1 올려준다

이는 소수의 연속합이 N이 되는 지점이다

 

이후 같다면 start가 1 올라가고 그 후는 다음과 같다

sum이 target number보다 작으므로, end를 하나 올려준다

 

sum이 target보다 크므로, start를 하나씩 올려주면서 해당 인덱스의 요소를 sum에서 빼준다

 

그렇게 start 인덱스를 올리다 보면, sum이 41이 되는 지점이 나타나는데

이 경우 조건을 또 만족하게 되므로 count를 1 올려준다

 

마지막으로 이 과정을 계속 반복하다 보면,

마지막 경우의 수인 요소 하나만으로 조건을 만족하게 되는 경우가 나오게 되고,

이후 반복문에서 end == len(primes) 조건이 만족하여 break를 통해 반복문을 빠져나오게 된다

 

이를 활용한 문제

1644번: 소수의 연속합

 

풀이

백준 알고리즘 1644번: 소수의 연속합