[백준] 11659 구간 합 구하기 (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

작성코드

 

 

 

풀이

 

1) 기본 구현 방식

단순하게 i에서 j까지 리스트의 값들을 sum에 계속 저장해주는 방식이다.

하지만 이렇게 작성하면 시간 복잡도가 O(N*M)으로서 숫자가 커지게 되면 시간초과가 나오게 된다.

 

 

기본 방식으로 일정 구간 합을 구할 경우

 

10의 길이를 가진 arr 배열을 예시로 비교해보겠다.

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

ex) 3, 5 (3번째 수부터 5번째 수까지 합)

 

arr[2] 탐색

sum += arr[2]    # sum = 2

arr[3] 탐색

sum += arr[3]    # sum = 2+3 = 5

arr[4] 탐색

sum += arr[4]     # sum = 5+4 = 9

 

이런 과정을 거쳐 계산이 완료된다.

1회만 계산한다면 상관이 없지만 매 계산마다 탐색과 sum 과정을 거치게 된다.

 

이를 해결하기 위해 누적합 알고리즘을 사용한다.

 

 

2) 구간합 알고리즘

구간합 알고리즘이란 주어진 배열의 일정 구간의 합을 구할 때 최적화하는 알고리즘이다.

 

구간 합 알고리즘으로 일정 구간 합을 구할 경우

ex) 3, 5 (3번째 수부터 5번째 수까지 합)

 

미리 배열의 합들을 계산해서 리스트에 누적합 값들을 저장해준다. (한번만 해두면 매번 계산과정이 필요하지 않게 된다.)

(sum에 저장해둠)

 

sum = [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

 

sum[5] - sum[3]    # 15 - 6 = 9

 

누적합에서 해당되지 않는 부분까지의 누적합을 빼면 구간합 계산과 동일하다.