[python] 백준 11659 : 구간 합 구하기 4 (실버 3)

https://www.acmicpc.net/problem/11659

해당 문제를 풀때는 너무 쉬운데? 라고 생각했지만 바로 시간초과가 떠버렸다...

아래 코드는 맨 처음 작성했던 시간 초과가 발생한 코드이다.

이대로 실행하면 구간 마다 SUM 을 실행시키기 때문에 O(n*m)의 시간 복잡도가 발생한다고 한다.

import sys
input = sys.stdin.readline
n , m = map(int,input().split())
arr = list(map(int,input().split()))
for _ in range(m):
    start , end = map(int,input().split())
    print(sum(arr[start-1:end]))

모르겠어서 검색해보니 누적 합을 사용하면 된다고 한다.

누적합이란?

누적 합(prefix sum)은 배열의 특정 구간 합을 빠르게 계산하기 위한 방법입니다. 이는 배열의 각 요소까지의 누적된 합을 미리 계산하여 저장한 배열을 사용합니다. 이렇게 하면 임의의 구간 합을 일정한 시간 복잡도로 계산할 수 있습니다.

누적 합의 원리

1. 누적 합 배열 생성:
   • 원래 배열의 각 요소까지의 합을 계산하여 누적 합 배열에 저장합니다.
   • 예를 들어, 배열 arr가 [a1, a2, a3, ..., an]이라면, 누적 합 배열 prefix_sum은 다음과 같이 정의됩니다:
     • prefix_sum[0] = 0 (편의를 위해 첫 번째 요소를 0으로 설정)
     • prefix_sum[i] = arr[0] + arr[1] + ... + arr[i-1] (1 ≤ i ≤ n)
2. 구간 합 계산:
   • 구간 [l, r]의 합을 구하기 위해 prefix_sum[r] - prefix_sum[l-1]을 계산합니다.
   • 이 식의 의미는 배열 arr에서 l번 인덱스부터 r번 인덱스까지의 합을 구하는 것입니다.

예제

예를 들어, arr = [1, 2, 3, 4, 5]가 주어졌다고 합시다.

1. 누적 합 배열 생성:
   • prefix_sum[0] = 0
   • prefix_sum[1] = 1 (1)
   • prefix_sum[2] = 1 + 2 = 3
   • prefix_sum[3] = 1 + 2 + 3 = 6
   • prefix_sum[4] = 1 + 2 + 3 + 4 = 10
   • prefix_sum[5] = 1 + 2 + 3 + 4 + 5 = 15
   따라서 prefix_sum 배열은 [0, 1, 3, 6, 10, 15]이 됩니다.
2. 구간 합 계산:
   • 예를 들어, arr의 인덱스 2부터 4까지의 합을 구하려면:
     • l = 2, r = 4
     • 구간 합은 prefix_sum[4] - prefix_sum[1] = 10 - 1 = 9

장점

• 시간 복잡도: 각 쿼리에 대해 구간 합을 O(1)O(1)O(1) 시간에 계산할 수 있습니다.
• 사전 처리: 누적 합 배열을 만드는 데 O(n)O(n)O(n) 시간이 걸립니다.

밑에 코드는 누적 합을 적용한 코드이다. 누적합을 적용하면 계산하는 과정에서 걸리는 시간 복잡도는 O(1) 이라고 합니다. 앞으로 현업에서 코드에 구간합을 계산 할 일이 있을때 누적합을 사용하면 전체적인 프로그램의 성능이 크게 향상될 것이기에 유용하다고 생각한다.

import sys
input = sys.stdin.readline
n , m = map(int,input().split())
arr = list(map(int,input().split()))
prefix = [0 for _ in range(n+1)]
for i in range(1,n+1):
    prefix[i] = prefix[i-1] + arr[i-1]
for _ in range(m):
    start , end = map(int,input().split())
    print(prefix[end]-prefix[start-1])