알고리즘 – 투 포인터 (Two Pointers)
- 투 포인터 알고리즘 이란?
- 1차원 배열에서 두 개의 점 위치를 이용하여 문제를 해결하는 알고리즘
- 시간 복잡도 = O(N)
- 예제 – 소수의 연속합 (백준 1644번)
# Python Code
N = int(input())
sosu_bool = [True for _ in range(N+1)]
sosu_bool[0] = False
sosu_bool[1] = False
sosu = []
# 에라토스테네스의 체
for i in range(2, N+1):
if not sosu_bool[i]: continue
else: sosu.append(i)
for j in range(i*2, N+1, i): sosu_bool[j] = False
del sosu_bool
# 투 포인터 알고리즘
interval_sum = 0
end = 0
count = 0
for start in range(len(sosu)):
while interval_sum < N and end < len(sosu):
interval_sum += sosu[end]
end += 1
if interval_sum == N:
count += 1
interval_sum -= sosu[start]
print(count)- 과정 – 소수의 연속합 (백준 1644번)
조건 : 범위(소수)의 합이 기준 값과 동일한 횟수 출력
예시 기준 값 : 17
시작 지점(start)과 종료 지점(end)의 범위 합이 기준 값보다 작으므로 end의 위치를 0->1로 증가시킵니다
그리고 다음 비교를 위해 start의 위치를 0->1로 증가시킵니다
결과 값 : 2