[자료구조] 구간 합

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃

https://youtu.be/O514yiWg8YE?si=2U5WPE1m75BjhSHN 

---

리스트 A가 있을 때 합 배열 S의 정의

: S[ i ] = A[ 0 ] + A[ 1 ] + A[ 2 ] + ... + A[ i - 1 ] + A[ i ]

 

합 배열 S를 만드는 공식

: S[ i ] = S[ i - 1 ] + A[ i ]

 

A[ i ] ~ A[ j ] 구간 합을 구하는 공식

: S[ j ] - s [ i - 1 ]

S[ j ] = A[0] + A[1] + ...+ A[ i - 1 ] + A[ i ] + ... + A[ j ]

S[ i ] = A[0] + A[1] + ...+ A[ i - 1 ] + A[ i ]

S[ j ] - S[ i - 1 ] = A[ i ] + ... + A[ j ]

---

실제로 문제를 풀어보니, 살짝 다르게 이해하는게 쉬웠다.

책에서는 합 배열 S와 기존 배열 A를 같은 크기로 설정하였는데 이와 다르게 진행했다.

합 배열 S의 크기를 기존 배열 A보다 1 크다고 생각한 후, S[0] = 0을 넣은 후 시작하는 것이다.

 

S[0] = 0

S[1] = A[0]

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

...

S[i] = A[0] + A[1] + ... + A[i-1]

 

유튜브 영상에 나와 같은 생각을 한 사람의 댓글이 있었고, 책 저자 분의 답변은 아래와 같았다.

본인이 이해하기 쉽고 정의가 확실히 되었다면 상관 없는 모양이다.