투포인터의 정의 및 장단점
- Two Pointers 는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘
- 여기서 두 개의 포인터를 사용하여 기존의 방식보다 시간을 개선할 수 있습니다.
- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
- 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다.
- 투 포인터 알고리즘은 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘을 뜻한다.
- 보통 lt(left), rt(right)나 s(start), e(end) 같은 식으로 포인터의 이름을 붙인다.
예제 문제 - 특정한 합을 가지는 부분 연속 수열 찾기
투포인터 알고리즘의 대표적인 문제입니다.
어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제입니다.
- 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.
- 현재 부분 합이 M과 같다면 카운트한다.
- 현재 부분 합이 M보다 작다면 end를 1 증가시킨다.
- 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.
- 모든 경우를 확인할 때까지 2-4번 과정을 반복한다.
위와 같은 리스트와 M=5 일 때의 예시를 생각해봅시다.
- [초기 단계] : 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 합니다.
- 현재의 부분 합은 1.
- 현재 카운트 : 0
- [Step 1] : 이전 단계에서의 부분합이 1 -> end를 증가시킵니다.
- 현재의 부분 합 : 3
- 현재 카운트 : 0
- [Step 2] : 부분합이 3 -> end를 증가시킵니다.
- 현재의 부분 합 : 6
- 현재 카운트 : 0
- [Step 3] : 부분합 6 -> start를 1 증가시킵니다.
- 현재의 부분 합 : 5
- 현재 카운트 : 1 (부분합이 5이기 때문에)
- 이걸 계속 반복하다가 마지막
- [마지막]
- 현재의 부분합 : 5
코드
n = 5 # 데이터의 개수 N
m = 5 # 찾고자하는 부분합 M
count = 0
interval_sum = 0
end = 0
# start를 차례대로 증가시키며 반복
for start in range(n):
# end만큼 이동시키기
while interval_sum < m and end < n:
interval_sum += data[end]
end += 1
# 부분합이 m일 때 카운트 증가
if interval_sum == m:
count += 1
interval_sum -= data[start]
print(count)
시간복잡도
매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 각 포인터가 n번 누적 증가해야 알고리즘이 끝납니다. -> 각각 배열 끝에 다다르는데 이라 둘을 합해도 여전히 입니다
'Computer Science > 알고리즘' 카테고리의 다른 글
Imos알고리즘 (누적합) (1) | 2023.05.09 |
---|---|
최단경로(다익스트라,플로이드워셜) (1) | 2023.01.19 |
다이나믹 프로그래밍 (0) | 2023.01.12 |
이진 탐색 (0) | 2023.01.09 |
정렬 (0) | 2023.01.04 |