배열의 특정 연속된 구간을 처리하는 경우
- 합이 5인 부분 연속 수열의 개수를 구하시오.
- 특정 구간에 해당하는 데이터들의 합을 모두 구하시오.
투 포인터(Two pointers)
리스트에 순차적으로 접근해야 할 때 두 개의 점을 이용해 위치를 기록하면서 처리하는 기법
투 포인터를 활용한 알고리즘 설명
- 특정한 합을 가지는 부분 연속 수열 찾기
- 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
- 현재 부분 합이 M과 같다면, 카운트한다.
- 현재 부분 합이 M보다 작거나 같다면, end를 1 증가시킨다.
- 현재 부분 합이 M보다 크다면, start를 1 증가시킨다.
모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.
# 데이터의 개수 N과 부분 연속 수열의 합 M을 입력 받기
n, m = 5, 5
data = [1, 2, 3, 2, 5]
result = 0
summary = 0
end = 0
# start를 차례대로 증가시키며 반복
for start in range(n):
# end를 가능한 만큼 이동시키기
while summary < m and end < n:
summary += data[end]
end += 1
# 부분 합이 m일 때 카운트 증가
if summary == m:
result += 1
summary -= data[start] # start가 증가하면서 이전의 start 값을 빼줌
print(result)
- 구간 합 빠르게 계산하기
1) 아래와 같이 N개의 정수로 구성된 수열이 있습니다.
2) M개의 쿼리(Query)정보가 주어집니다.
각 쿼리는 L과 R로 구성됩니다.
[L, R]구간에 해당하는 데이터들의 합을 모두 구하는 문제입니다.
3) 시간 제한: O(N+M)
[문제 해결 방법]
- 접두사 합(Prefix Sum): 리스트의 앞에서부터 특정 위치까지의 합을 의미하고
- Prefix Sum을 계산하여 배열 P에 저장한다.
- 매 M개의 쿼리 정보를 확인할 때, 구간 합은 P[R]-P[L-1]이다.
# 데이터의 개수 N과 데이터 입력 받기
n = 5
data = [10, 20, 30, 40, 50]
# Prefix Sum 배열 계산
summary = 0
prefix_sum = [0]
for i in data:
summary += i
prefix_sum.append(summary)
# 구간 합 계산
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left-1])