투 포인터
투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 2개의 점 위치를 기록하면서 처리하는 알고리즘이다.
10명의 학생 중, (2,3,4,5,6,7) 번의 학생을 부를 때, 각각을 부르지 않고 2번부터 7번 이라고 부르는 것 처럼 리스트에 담긴 데이터에 순차적으로 접근해야할 때 시작점과 끝점을 이용한다.
이를 이용해 풀 수 있는 문제 중, 가장 대중적인 문제는 특정한 합을 가지는 부분 연속 수열 찾기 문제다.
예를 들어,
[1 2 3 2 5] 와 같은 리스트가 주어져 있고, 합계가 5인 부분 연속 수열을 찾고자 하면, 시작점과 끝점을 이용해 문제를 해결할 수 있다.
- 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다.
- 현재 합이
M(합계)과 같다면, 카운트한다.- 현재 부분합이
M보다 작다면 끝점의 인덱스를 1 증가시킨다.- 현재 부분합이
M보다 크면 시작점의 인덱스를 1 증가시킨다.- 모든 경우를 확인할 때 까지 3-4번을 반복한다.
코드는 아래와 같다. n은 데이터의 개수며, m은 찾고자 하는 부분 합을 뜻한다.
n = 5
m = 5
data = [1, 2, 3, 2, 5]
count = 0
interval_sum = 0
end = 0
for start in range(n):
while interval_sum < m and end < n:
interval_sum += data[end]
end += 1
if interval_sum == m:
count += 1
interval_sum -= data[start] # end가 지나간 자리의 값을 빼줘야 함
print(count)
---
3
하지만 위 코드의 경우, 리스트 원소에 음수 데이터가 포함되어 있는 경우 문제를 해결할 수 없다.
이 밖에도 정렬되어 있는 두 리스트의 합집합 같은 문제에 효과적으로 사용할 수 있다.
이미 정렬되어 있는 2개의 리스트가 입력으로 주어지고, 두 리스트를 합쳐 정렬한 결과를 계산하는 문제다.
- 정렬된 리스트
A와B를 입력받는다.- 리스트
A에서 처리되지 않은 원소 중 가장 작은 원소를i가 가리키도록 한다.- 리스트
B에서 처리되지 않은 원소 중 가장 작은 원소를j가 가리키도록 한다.A[i]와B[j]중에서 더 작은 원소를 결과 리스트에 담는다.- 리스트
A와B에서 더 이상 처리할 원소가 없을 때 까지 2~4번의 과정을 반복한다.
코드는 다음과 같다.
n, m = 3, 4
a = [1, 3, 5]
b = [2, 4, 6, 8]
result = [0] * (n+m)
i = 0
j = 0
k = 0
while i < n or j < m:
if j >= m or (i < n and a[i] <= b[j]): # 리스트 B의 모든 원소가 처리되었거나,
리스트 A의 원소가 더 작을 때
result[k] = a[i]
i += 1
else:
result[k] = b[j]
j += 1
k += 1
for i in result:
print(i, end= " ")
---
1 2 3 4 5 6 7 8
구간 합 계산
구간 합이란, 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제다.
예를 들어, [10, 20, 30, 40, 50]이 있다고 가정해보면, 여기서 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40으로, 90이다.
M개의 쿼리가 존재한다고 가정해보면, 각 쿼리는 Left, Right로 구성되며 이는 [Left, Right] 구간을 의미한다.
만약 이 경우에서 M개의 쿼리를 각각 계산한다면, 알고리즘의 시간 복잡도는 O(NM)이 된다.
만약 N과 M이 충분히 큰 상황이라면, 알고리즘을 풀 수 없는 경우가 생긴다.
이를 해결하기 위해 접두사 합을 이용하며, 이는 리스트의 맨 앞부터 특정 위치까지의 합을 구해놓은 것이다.
각 쿼리에 대해 구간 합을 빠르게 계산하기 위해서는 N개의 수 위치 각각에 대하여 접두사 합을 미리 구해 놓으면 된다.
N개의 수에 대하여 접두사 합을 계산하여 배열P에 저장한다.- 매
M개의 쿼리 정보 [L,R]을 확인할 때, 구간 합은P[R] - P[L-1]이다.
예를 들어, [10, 20, 30, 40, 50]과 같은 리스트의 접두사 합을 구하면
[0, 10, 30, 60, 100, 150] 이다.
위에서 제시한 알고리즘대로, P[R] - P[L-1]을 계산하면, 구간 합을 바로 도출할 수 있고, 이는 N개의 데이터와 M개의 쿼리가 있을 떄 O(N+M)의 시간 복잡도를 가진다.
예를 들어 첫번 째 수부터 세번 째 수까지의 구간 합을 물어보는 [1,3]에 대하여,
P[3] - P[0] = 60이 답이 된다.
코드는 아래와 같다.
n = 5
data = [10, 20, 30, 40, 50]
sum_value = 0
prefix_sum = [0]
for i in data:
sum_value += i
prefix_sum.append(sum_value)
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left-1])
---
70