[기타 알고리즘] 구간 합 계산

 '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 의 appendix B의 순서에 해당하는 글들을 읽으며 정리하였다.

 이 책은 접하게 된지 이틀밖에 되지 않았지만 체계적으로 적혀있는 것 같아서 한 번 끝까지 독학해보고자 한다..!!

 블로그에는 글들만 정리하였지만, 실제 책에는 그림으로 상세한 설명이 나와있다 !

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

구간 합 계산

 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제를 말한다. 

예를 들어 수열 [10,20,30,40,50] 이 있을 때, 2번째 수부터 4번째 수까지의 합은 20+30+40 = 90이다.

 

 M개의 쿼리가 존재할 때 각 쿼리는 Left, Right 인 [Left,Right] 구간으로 주어진다. 이 모든 쿼리에 대해 구가느이 합을 출력하는 문제이다.

만약 M개의 쿼리가 각각, 매번 구간 합을 계산한다면 이 알고리즘은 O(NM)의 시간 복잡도를 가진다. M개의 쿼리가 수행될 때마다 전체 리스트의 구간합을 모두 계산하라고 요구하게 되기 때문에 위와 같은 시간 복잡도를 가진다.

 

 

 알고리즘을 설계할 때 여러 번 사용될 만한 정보는 미리 구해서 저장해놓을 수록 유리하다. 쿼리는 M개 이지만 N개의 수는 한 번 주어진 뒤에 변하지 않다. 따라서 N개의 수에 대해서 처리를 수행한 후, 나중에 M개의 쿼리가 각각 주어질 때마다 빠르게 구간합을 도출한다면 어떻게 해야할지에 대한 고민이 필요하다.

 이럴 때 많이 쓰이는 기법이 접두사 합이다. 각 쿼리에 대해 구간 합을 빠르게 구하기 위해서 N개의 수의 위치 각각에 대해 접두사 합을 미리 구해놓는 것이다. (접두사 합 : 리스트의 맨 앞부터 특정 위치까지의 합을 구해놓는 것을 의미한다.)

 

 접두사 합을 빠르게 구하는 알고리즘은 다음과 같다.

 1. N 개의 수에 대하여 접두사 합을 계산하여 배열 P에 저장한다.

 2. 매 M개의 쿼리정보 [L,R] 을 확인할 때, 구간의 합은 P[R]-P[L-1]이다.

 

이렇게 계산한다면 매 쿼리당 계산 시간은 O(1)이 되고, 결과적으로 N개의 데이터와 M개의 쿼리가 있을 때, 전체 구간 합을 모두 계산하는 작업은 O(N+M)의 시간 복잡도를 가진다.

 

예를 들어, [10,20,30,40,50] 이라는 데이터가 있다고 생각해보자. 이의 접두사 합을 구하면 [0,10,30,60,100,150]이다. 이를 활용해서 위의 알고리즘을 합친다면 구간 합을 빠르게 구할 수 있다.

 이를 코드로 작성하면 다음과 같다.

# 데이터의 개수 N과 전체 데이터 선언
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