문제

수 N개가 주어졌을 때 i번째 수에서 j번째 수까지의 합을 구하는 프로그램 작성

풀기 전 상식

구간 합

• 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

구간 합의 핵심 이론

• 합 배열을 구해야 함
• 리스트 A가 있을 때 합 배열 S는 다음과 같이 정의

<aside> 💡 합 배열의 S정의 S[i] = A[0] + A[1] + A[2] + . . . + A[i-1] + A[i]

합 배열 S를 만드는 공식 S[i] = S[i-1] + A[i]

</aside>

• 합 배열 ⇒ 기존의 리스트 데이터를 전처리한 배열
• 합 배열을 미리 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도는 O(N) → O(1)로 감소

구하는 공식

인덱스: (0) (1) (2)(3)(4)(5)
리스트A: 15  13  10  7  3  12
     ➕⬇️    ⬇️➕.  
합배열S: 15➡️➕28  38 45  48 60
        |----------|
     구하고자 하는 구간 합 영역

S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]

S[1] = A[0] + A[1]

S[5] - S[1] = A[2] + A[3] + A[4] + A[5]

출력

	 5 3 //데이터의 개수, 질(문)의 개수
 5 4 3 2 1 //구간 합을 구할 대상 배열
 1 3
 2 4
 5 5

12
9
1

손으로 풀어보기

• 여기 배열을 보면 순서가 5 4 3 2 1 인 걸 확인할 수 있음