1. 투포인터 알고리즘
리스트에 접근할때, 두개의 포인터(노드, 점) 위치를 기록하면서 처리하는 방식을 의미한다.
예를 들어, 2-3-4-5-6-7 의 학생을 지목할때 보통은 2번부터 7번까지의 학생으로 지칭하는 경우가 많은 것처럼, 리스트에 담긴 데이터에 접근할때 시작점과 끝점을 지정하고 이를 기록하면서 데이터를 처리하거나, 접근하고자 하는 데이터 범위를 표현하는 방법을 지칭한다.
2. 적용 - 특정 합을 가지는 부분적인 연속 수열 추출
- N개의 자연수로 구성된 수열이 있다고 가정하자.
- 합이 M인 연속적인 부분 수열의 개수를 개수는(*O(N)↓)?
위 수열 안에서 특정 조건(합이 5인 데이터들을 탐색)을 만족하는 부분 수열을 구한다고 할 때, 데이터 탐색을 시작점과 끝점이 존재하는 데이터 범위를 계속 기록 및 수정해가면서 탐색한다는 점이 핵심이다.
전체적인 과정은 다음과 같다.
- 시작점(start)와 끝점(end)을 첫번째 인덱스(0)을 가르키도록한다.
- 현재 부분합이 M일 경우, 그때 count + 1한다.
- 부분합이 M보다 작다면 end+ 1(범위증가)한다.
- 부분합이 M보다 크다면 start + 1(범위감소)한다.
- 이 과정을 반복하고, 시작점과 끝점이 존재하는 "범위", 즉 투포인터를 기준으로 데이터를 탐색해 나간다.
즉 위와 같이 알고리즘을 반복하면서, 예를 들어 부분합이 M보다 작았다면 end+1로 범위를 늘려서 부분합을 늘린다.
end인덱스가 배열의 최고 인덱스까지 도달할때까지 반복한다.
#N개의 자연수로 구성된 수열이 있을때
#합이 M인 부분적인 연속 수열의 개수를 구하는 알고리즘은?
##투포인터 알고리즘(시작점과 끝점을 지정하여 접근하는 데이터의 범위를 표현하는 것)
n = 5 #데이터 개수
m = 5 #연속수열의 부분합
data = [1, 2, 3, 2, 5]
count = 0
sum = 0
end = 0
for start in range(n):
#start는 전체 반복문에서 반복, 이 경우는 합이 m보다 클 때
#아래 경우는 end를 +1한 경우로 합이 m보다 작을때
while sum < m and end < n: #추가조건 : end가 n보다 작을때만
sum = sum + data[end] #일전의 합이 sum에 저장
end = end + 1
if sum == m: #부분합이 m일때 카운트 증가
count = count + 1
#이후 수행되는 알고리즘은 sum이 크거나 같다면 start + 1
#이전 start 값에 대한 값은 감산
sum = sum - data[start]
print(count)3. 참조자료
이코테 2021 - 투포인터 알고리즘
https://www.youtube.com/watch?v=cswJ1h-How0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9
