누적 합(prefix sum)은 그 특성상 배열의 부분합을 빠르게 구하는데 굉장히 유용하다. 이번에는 1차원 배열에서의 누적 합의 성질과 이를 이용하여 해결 가능한 문제들을 다뤄본다.
1. 누적 합의 성질
어떤 1차원 배열 A = [a(1), a(2), ... , a(n)] 에 대해, 누적합 S(k)는 다음과 같은 성질을 가진다.
① S(k) = a(1) + a(2) + ... + a(k)
② S(1) = a(1)
③ S(k) = S(k-1) + a(k)
④ a(i) + a(i+1) + ... + a(j-1) + a(j) = S(j) - S(i-1)
2. 구간 합 구하기 4(https://www.acmicpc.net/problem/11659)
매우 간단한 누적합 활용문제이다.
import sys
input = sys.stdin.readline
def sol11659():
# 수열의 크기 n, 질의의 갯수 m
n, m = map(int, input().split())
# n개의 수로 이루어진 수열
seq = [0, *map(int, input().split())]
# 수열의 누적합 전처리
for i in range(1, n + 1):
seq[i] += seq[i - 1]
# 각 질의에 대해 정답을 계산하여 answer 에 삽입
answer = []
for _ in range(m):
i, j = map(int, input().split())
answer.append(seq[j] - seq[i - 1])
# 출력형식에 맞춰 정답리스트 반환환
return '\n'.join(map(str, answer))a(i) + a(i+1) + ... + a(j-1) + a(j) = S(j) - S(i-1) 임을 이용하여 문제를 해결하였다.
3. 광고 삽입(https://programmers.co.kr/learn/courses/30/lessons/72414)
영상 전체의 길이와 시청자들이 어느 구간을 재생했는지의 로그들이 주어질 때, 광고를 삽입할 최적의 위치를 찾기위해 가장 재생횟수가 많은 구간의 시작시간을 구하는 문제이다. 만약 재생횟수가 가장 많은 구간이 여러개라면 그 중 가장 빠른 시작시간을 반환한다. 위의 문제보다는 복잡하지만 역시 누적 합을 활용하여 해결할 수 있는 문제이다.
주어지는 데이터는 동영상 전체의 재생시간 play_time 과 광고의 재생시간 adv_time, 영상의 재생구간 로그들이 담긴 리스트 logs이다. 문제를 해결하는 과정은 다음과 같다.
① 먼저, 제한사항에 광고의 재생시간은 동영상의 재생시간보다 짧거나 같게 주어진다는 조건이 있다.
광고의 재생시간이 영상의 재생시간보다 짧을 경우에는 평범하게 최적의 광고시간을 탐색하면 그만이지만
같을 경우에는 애초에 탐색할 필요가없다. 영상의 시작시간이 곧 광고의 시작시간이 될 수 밖에 없기 때문이다.
② play_time 과 adv_time은 'HH:MM:SS' 의 문자열 형태이기 때문에 다루기 쉽도록 정수형태로 파싱해줄 필요가 있다.
가장 작은 초단위로 시간을 변환한다. HH * 3600 + MM * 60 + SS 로 간단하게 변환 가능하다.
③ 다음은 광고가 삽입될 최적의 위치를 찾기위해 로그를 분석해야한다. 가장 먼저 떠오르는 방식은 1초에 한칸씩
0으로 초기화된 배열을 할당하여 재생된 부분마다 1씩 더해주는 것으로 가장 재생수가 많은 구간을 탐색하는
것이다. 다행히도 play_time의 범위가 00:00:00 부터 99:59:59, 즉, 0초부터 359999초 까지라는 조건이 있기 때문에
배열의 형태로 충분히 나타낼 수 있다.
④ 예를 들어 로그가 '00:00:00-00:00:04', '00:00:02-00:00:07', '00:00:06-00:00:10' 의 세 개라고 생각해보자.
문제의 제한사항에 "예를 들어, 00시 00분 01초부터 00시 00분 10초까지 동영상이 재생되었다면, 동영상
재생시간은 9초 입니다." 라는 조건이 있다. 즉, 종료시간은 재생구간에 들어가지 않는다는 것이다.
이에 따라 위 로그를 배열상에 표현하면 아래와 같은 형태가 된다.
문제는 여기서 발생한다. 로그 한번마다 구간내의 값을 모두 1 씩 증가시키려면 재생시간의 길이가 N, 로그의 갯수가
M일 때 최악의 경우(모든 로그의 범위가 영상의 재생시간과 같을 경우) O(NM) 의 시간복잡도를 보인다.
이 문제에서 N은 최대 360000, M은 최대 30만의 크기를 가지기에 이 알고리즘은 매우 비효율적이다.
⑤ 여기서 우리는 누적 합의 성질 중 하나인 S(k) = S(k-1) + a(k) 를 활용할 수 있다. 이번엔 로그의 시작 시간과
종료 시간에만 시청횟수의 증감을 더해보자. 그러면 다음과 같은 형태가 된다.
각 로그의 시작 시간인 0, 2, 6초에는 +1을, 종료 시간인 4, 7, 10초에는 -1을 더하였다. 이제 위 테이블에서
누적합의 성질에 따라 누적합을 구해보자. 그러면 다음과 같은 형태가 된다.
한눈에 봐도 ④ 에서 구했던 로그마다 전 구간의 값을 1씩 증가시키는것으로 얻었던 배열과 같음을 알 수 있다.
게다가 이 방식은 O(N+M)의 시간복잡도로 위의 O(NM)의 알고리즘과 같은 결과를 얻을 수 있다. 이와 같이
누적 합을 활용하면 어떤 배열에 여러 구간에 대한 증/감을 반영하는 작업을 굉장히 효율적으로 처리할 수 있다.
⑥ 여기까지 구하고나면 다음은 어렵지 않다. 위에서 구한 배열에서 영상의 시작시간부터 시작하여 광고 시간만큼의
구간의 합이 최대치가 되는 구간의 시작시간을 구하면 된다. 최댓값이 여러개라면 가장 빠른 시간을 구하라는 조건도
처음 찾은 최댓값이 더 큰 값이 오기 전에는 갱신되지 않도록 하면 자동으로 충족된다. 여기서 구간합이 최대가 되는
경우를 찾는 것도 두 가지 방법이 있다.
⑦ 하나는 마찬가지로 누적 합을 이용한 방법이다. a(i) + a(i+1) + ... + a(j-1) + a(j) = S(j) - S(i-1) 임을 이용하여,
위 배열의 누적합을 다시한번 구한 뒤 구간마다 구간합을 빠르게 구할 수 있다.
⑧ 다른 하나는 투 포인터를 활용하는 방법이다. 첫 번째 구간의 합만을 구한 뒤, 다음 구간으로 넘어갈때마다
첫 번째 요소를 빼고 새로운 요소를 더하는 식으로 구간합을 갱신해나갈 수 있다.
⑨ 마지막으로 구한 시작시간을 다시 'HH:MM:SS' 의 형태의 문자열로 변환하여 반환하면 된다.
위 절차에 따라 문제를 해결한 코드는 다음과 같다.
1) 누적 합의 성질을 활용하여 최대 구간합을 구한 방식 (⑦)
def solution(play_time, adv_time, logs):
# ① 광고의 재생시간이 영상의 재생시간과 같다면 영상의 첫 부분에 삽입하면 된다.
if play_time == adv_time:
return '00:00:00'
# ② 영상 재생시간과 광고 재생시간을 초단위의 정수로 변환
pt, at = stoh(play_time), stoh(adv_time)
# ③ 시간별 재생횟수를 나타내기위한 타임라인 배열을 생성
timeline = [0] * 360001
# ④, ⑤ 로그를 분석하여 재생 시작시간과 종료시간을 구한 뒤
# 누적 합을 활용하여 타임라인에 재생 횟수를 표기
for log in logs:
s, e = map(stoh, log.split('-'))
timeline[s] += 1
timeline[e] -= 1
for i in range(1, 360001):
timeline[i] += timeline[i - 1]
# ⑦, ⑧ 영상의 시작시간부터 timeline의 at(광고 재생시간)크기의 구간합이 최대가 되는 경우를 탐색
# 다시 한번 누적 합을 구하는 전처리작업을 수행하여 구간 합을 더 쉽게 구할 수 있도록 한다.
for i in range(1, 360001):
timeline[i] += timeline[i - 1]
# 최대 구간 합 maxw, 정답으로 반환할 시작시간 answer
maxw, answer = timeline[at-1], 0
# 영상의 시작시간부터 탐색 시작
for s in range(1, pt - at+1):
# 누적 합의 성질을 활용하여 구간 합을 구한다
w = timeline[s+at-1] - timeline[s-1]
# 만약 새로운 구간합이 최대 구간합 maxw보다 크다면 maxw와 answer 갱신
if w > maxw:
maxw, answer = w, s
# 광고를 삽입할 최적의 시작시간을 문자열로 변환하여 반환
answer = htos(answer)
return answer
# 문자열 형태의 시간을 초단위의 정수로 변환
def stoh(times):
h, m, s = map(int, times.split(':'))
return h * 3600 + m * 60 + s
# 초단위의 정수를 문자열 형태의 시간으로 변환
def htos(sec):
h = sec // 3600
sec %= 3600
m = sec // 60
s = sec % 60
return '%02d:%02d:%02d' % (h, m, s)
2) 투 포인터를 활용하여 최대 구간합을 구한 방식 (⑧)
def solution(play_time, adv_time, logs):
# ① 광고의 재생시간이 영상의 재생시간과 같다면 영상의 첫 부분에 삽입하면 된다.
if play_time == adv_time:
return '00:00:00'
# ② 영상 재생시간과 광고 재생시간을 초단위의 정수로 변환
pt, at = stoh(play_time), stoh(adv_time)
# ③ 시간별 재생횟수를 나타내기위한 타임라인 배열을 생성
timeline = [0] * 360001
# ④, ⑤ 로그를 분석하여 재생 시작시간과 종료시간을 구한 뒤
# 누적 합을 활용하여 타임라인에 재생 횟수를 표기
for log in logs:
s, e = map(stoh, log.split('-'))
timeline[s] += 1
timeline[e] -= 1
for i in range(1, 360001):
timeline[i] += timeline[i - 1]
# ⑦, ⑧ 영상의 시작시간부터 timeline의 at(광고 재생시간)크기의 구간합이 최대가 되는 경우를 탐색
# 최대구간합 maxw, 정답으로 반환할 시작시간 answer
maxw, answer = sum(timeline[:at]), 0
# 초기 구간합 w = maxw
w = maxw
# 영상의 시작시간부터 탐색 시작
for s in range(1, pt - at+1):
# 투 포인터를 활용하여 구간합을 갱신해나가는 방식을 사용
w = w - timeline[s-1] + timeline[s+at-1]
# 만약 새로운 구간합이 최대 구간합 maxw보다 크다면 maxw와 answer 갱신
if w > maxw:
maxw, answer = w, s
# 광고를 삽입할 최적의 시작시간을 문자열로 변환하여 반환
answer = htos(answer)
return answer
# 문자열 형태의 시간을 초단위의 정수로 변환
def stoh(times):
h, m, s = map(int, times.split(':'))
return h * 3600 + m * 60 + s
# 초단위의 정수를 문자열 형태의 시간으로 변환
def htos(sec):
h = sec // 3600
sec %= 3600
m = sec // 60
s = sec % 60
return '%02d:%02d:%02d' % (h, m, s)
구간 합을 활용하여 효율적으로 문제를 해결해야하는 경우는 코딩테스트에서 꽤 자주 보인다. 잘 기억해두자.
'코딩테스트 > 알고리즘' 카테고리의 다른 글
| #35 위상 정렬(Topological Sorting) (0) | 2021.09.14 |
|---|---|
| #34 누적 합(Prefix Sum) - 2차원 (0) | 2021.09.13 |
| #32 문자열 탐색 - 트라이(Trie) 2 (0) | 2021.09.09 |
| #32 문자열 탐색 - 트라이(Trie) 1 (0) | 2021.09.08 |
| #31 문자열 탐색 - KMP 알고리즘(2) (0) | 2021.09.07 |