선형공간인 1차원 배열에서 특정 조건을 만족하는 연속 구간의 합을 구해야 한다고 가정해보자.
가장 먼저 떠오르는 방식으로는 배열의 인덱스를 처음부터 끝까지 돌면서 완전 탐색을 할 수 있을 것이다. 하지만 이는 O(N^2)의 시간복잡도가 걸리므로 효율성 면에서 좋지 않다.
시간복잡도를 O(N) 수준으로 개선시킬 수 있는 아래의 알고리즘 4가지 중 하나를 선택하여 효율성을 개선시켜보자.
- 투포인터 알고리즘 O(N)
- 슬라이딩 윈도우 알고리즘 O(N)
- 누적합 알고리즘 O(N)
- 펜윅트리 알고리즘 O(logN)
투포인터 알고리즘
인덱스를 가리키는 두 개의 포인터를 사용하여 구간의 길이를 가변적으로 잡아가며 특정 조건을 만족하는 구간을 찾는다. 두 포인터 모두 각각 약 N번 움직이기 때문에 O(N+N) = O(N)이 된다.
n = 5 # 데이터의 개수 N
m = 5 # 찾고자 하는 부분합 M
data = [1, 2, 3, 2, 5] # 전체 수열
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) 포인터 2개가 같은 방향으로 진행하는 경우
2) 포인트 2개가 양끝에서 반대로 진행하는 경우
3) 포인터 하나는 한 쪽 방향으로만 진행하고, 다른 포인터는 양쪽 모두 진행하는 경우
3 가지가 존재한다.
슬라이딩 윈도우 알고리즘
고정적인 크기로 구간을 움직일 때 자주 활용된다.
투포인터 알고리즘과 다른 점은 투포인터의 경우 가변적으로 움직이기 때문에 시작 지점과 끝 지점을 모두 알아두어야 하는 반면, 슬라이딩 윈도우 알고리즘은 구간의 길이가 고정적이어서 시작 위치만 알아도 끝 위치를 자동으로 알 수 있기 때문에 두 개의 포인터가 필요 없다는 점이다.
슬라이딩 윈도우 알고리즘만의 특징은 마치 창문을 왼쪽에서 오른쪽으로 조금씩 밀듯이 구간을 이동한다는 것이다. 이런식으로 이동하게 되면 기존 구간과 새 구간에서 겹치는 부분이 생기는데 이 값을 새로 구하지 않고 그대로 사용한다. (따라서 여기서 시간복잡도를 줄일 수 있음) 결국 우리가 고려해야할 점은 이동으로 인해 빠지게 된 원소의 값을 삭제하고, 반대로 새로 추가된 원소의 값을 더해주는 것 뿐이다
# 고정 길이의 구간합의 최댓값을 구하는 문제
numbers = [3, -1, 8, -2, 0, 9, -3] # 배열
n = len(numbers) # 배열의 개수
k = 3 # 찾고자 하는 부분합
window = sum(numbers[:k])
answer = window
for i in range(k, n):
window += numbers[i] - numbers[i - k] #맨 앞 원소를 삭제하고, 현재 원소를 추가함
answer = max(answer, window)
print(answer)Prefix Sum 알고리즘
Prefix Sum(접두사 합)은 리스트의 맨 앞부터 특정 인덱스(위치)까지의 합을 구해 놓은 배열 S를 활용해 구간합을 구하는 방식이다.
이전 인덱스 값을 활용하여 현재 인덱스 값을 구한다는 점에서 dp의 일종이라고 볼 수 있다.
data = [10, 20, 30, 40, 50, 60]
query = [(1, 3), (2, 5), (3, 4)]
prefix_Sum = [data[0]]
for d in data[1:]:
prefix_Sum.append(prefix_Sum[-1] + d)
for l, r in query:
if l == 0:
print(prefix_Sum[r])
else:
print(prefix_Sum[r]-prefix_Sum[l-1])구간합 문제에서는 위처럼 여러 개의 쿼리로 구성된 경우가 많다. 배열의 개수를 N, 쿼리의 개수를 Q라고 할 때 시간복잡도는 O(N+Q)가 될 것이다.
펜윅트리 알고리즘
세그먼트 트리의 일종으로 펜윅트리 또는 바이너리 인덱스 트리로 불리운다.
펜윅트리의 핵심은 부분합으로 구간합을 만들어낼 수 있다는 점이다.
펜윅트리를 활용해서 시간복잡도를 O(logN)으로 줄일 수 있는데, 이에 대한 내용은 설명이 꽤 방대하므로 다음 글에서 이어서 작성하도록 하겠다 !
