728x90
1. Two Pointer Algorithm
전제
투 포인터 알고리즘 : 리스트(배열)가 '정렬'이 되어있어야 함!
특징
- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
- 구간 합의 경우 오직 누적 합(합 배열)에서 기존의 배열을 순차적으로 접근(X), 기존의 배열의 합에 접근(O) 이기 때문에 다름
- 흔히 2,3,4,5,6,7번 학생을 지목해야 할 대 간단히 '2번부터 7번까지의 학생'이라고 부름
- 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있음
Caution
- 포인터 2개가 모두 한 쪽 끝에서 시작할 수도 있으나, 양쪽 끝에서 시작할 수도 있음
- 연속한 구간 합을 구하는 경우 : 한 쪽 끝에서 시작
- 두 수의 합이 특정 수가 되는 경우를 구하는 경우 : 양쪽 끝에서 시작 (특정 수를 for문으로 돌릴 수 있음
특정한 합을 가지는 부분 연속 수열 찾기
- n개의 자연수로 구성된 수열이 존재
- 합이 m인 부분 연속 수열의 개수를 구하기
- 수행 시간 제한은 O(N)임 : 데이터의 개수만큼 원소를 확인하며 선형적으로 동작하는 알고리즘을 탐색
- 완전 탐색을 사용할 경우 O(N^2)임
투 포인터로 다음과 같이 해결 가능
1. start와 end에 첫 번째 원소의 index(0)을 가리키도록 함
2. 현재 부분 합이 M과 같다면, 카운트 함
3. 현재 부분 합이 M보다 작다면, end를 1 증가시킴
4. 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킴
5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복
2. Methods
Method 1 (모두 한 쪽 끝에서 포인터가 시작할 경우)
- end = 0 (index로 해석) ; cnt = 0
- start를 for loop를 이용해 차례대로 증가시키며 반복
- for start in range(n) :
- while loop를 이용해 end를 최대한 오른쪽으로 이동시키기
- while sums < m and end < n :
- end가 매 loop 마다 초기화되지 않으므로(고정) O(N)
- sums == n 일 때 cnt+=1
n = 5 # number of data
m = 5 # subtotal which you want to find
data = [1,2,3,2,5]
cnt = 0
interval_sum = data[0]
end = 0
# start를 차례대로 증가시키며 반복
for start in range(n) :
# end를 가능한 만큼 이동시키기
while interval_sum < m and end < n :
end+=1
interval_sum+=data[end]
# 부분합이 m일 때 카운트 증가
if interval_sum == m :
cnt+=1
interval_sum -= data[start]
print(cnt)
Method 2 (각 포인터들이 양쪽 끝에서 시작할 경우)
- start, end = 0, n-1
- sums = array[start] + array[end]
- while start < end :
- sums > m, sums < m 일 때 end, start 각각 업데이트
- sums == m일 때 start, end 모두 업데이트 (어차피 하나만 업데이트 해도 같지 않기 때문)
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
array = sorted(list(map(int, input().split())))
# start, end를 index로 해석
start, end = 0, n-1
cnt = 0
while start < end :
sums = array[start] + array[end]
if sums > m :
end -=1
elif sums < m :
start +=1
else :
cnt +=1
start +=1
end -=1
print(cnt)
728x90
