[백준/Python] 11659 구간 합 구하기 4

[백준/Python] 11659 구간 합 구하기 4

정답 코드 및 설명

전체 코드

N, M = map(int, input().split())
arr = list(map(int, input().split()))

prefixSum = [0] * (N+1)
for i in range(1, N+1):
    prefixSum[i] = prefixSum[i-1] + arr[i-1]

for _ in range(M):
    i, j = map(int, input().split())
    print(prefixSum[j] - prefixSum[i-1])

문제 설명

구간 합 구하기 문제는 특정 구간의 합을 빠르게 계산하는 것이다. 이 문제를 효율적으로 해결하기 위해 사용하는 기법 누적 합을 사용하는 것이다

누적 합(Prefix Sum) 알고리즘

누적 합 알고리즘은 배열의 각 위치에 대해, 그 위치까지의 모든 원소들의 합을 미리 계산해 두는 방법이다. 이렇게 하면, 어떤 구간의 합을 구하고자 할때, 해당 구간의 끝 지점까지의 누적 합에서 시작 지점 이전까지의 누적합을 빼주기만 하면, 그 구간의 합을 매우 빠르게 계산할 수 있다.

코드 설명

1. 입력으로 주어진 N개의 수에 대해서 누적합을 먼저 계산한다. prefixsum 배열을 사용하는 데 prefixSum[i] 는 주어진 배열의 첫 번째 원소부터 i 번째 원소까지의 합을 저장한다.

2. prefixSum[0] 을 0으로 먼저 초기화한다. 이는 구간의 시작 지점이 1번째 원소일 경우를 처리를 위한 초기화이다.

3. prefixSum 배열을 채울 때 각 i 에 대하여 prefixSum[i] = prefixSum[i-1] + arr[i-1] 공식을 사용한다. 이 공식은 이전까지의 누적 합에 현재 원소를 더해 다음 누적 합을 계산한다.

4. 구간 합을 구하려 할 때는, 주어진 구간 [i,j] 에 대하여 prefixSum[j] - prefixSum[i-1] 을 계산한다. 이는 i 번째 원소부터 j 번째 원소까지의 합과 같다.

시간 초과 문제

입력 방식을 sys 를 이용해 입력 받는 것으로 변경한 코드이다.

import sys

N, M = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

prefixSum = [0] * (N+1)
for i in range(1, N+1):
    prefixSum[i] = prefixSum[i-1] + arr[i-1]

for _ in range(M):
    i, j = map(int, sys.stdin.readline().split())
    print(prefixSum[j] - prefixSum[i-1])

위 코드로 문제를 풀 수 있다.