[Java] 03-2. 자료구조 : 구간 합 구하기 1

🧑🏻‍💻 하루코딩 님의 Do it! 알고리즘 코딩테스트 강의(인프런)를 듣고 정리한 내용입니다. 

 

 

01. 구간 합

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

➡️ 코딩 테스트에서 사용 빈도가 높으니 알아두는 것이 좋음!

 

✔️ 구간 합의 핵심 이론 

•  구간 합 알고리즘을 활용하기 위해서는 먼저 합 배열을 구해야 한다. 
• 합 배열의 정의는 다음과 같다 
  → S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]
  → 즉 배열 A가 있을 때 합 배열 S[i]는 A[0]부터 A[i] 사이의 합을 말하는 것이다.
  → 합 배열 S를 만드는 공식 : S[i] = S[i-1] + A[i] 
• 구간 합을 구하는 공식 
  → S[j] - S[i-1] // i 에서 j 까지의 구간 합 
  → 만약 배열 A에서 구간 합 2~5를 구하고 싶다면 S[5] - S[1] 을 해주면 된다.
  → 우리는 A[2]에서 [5]까지의 합을 구하고 싶은 것이니 S[1] 구간 합을 빼주면 원하는 값이 나오는 것이다.
• 합 배열을 미리 구해두면 구간 합은 합 번의 계산으로 구할 수 있다! 

 

 

❓만약에 배열의 값이 자주 바뀌게 된다면 합 배열 사용이 어렵지 않을까?

➡️ 이런 경우에 사용할 수 있는 것이 "인덱스 트리(Indexed Tree)", 이 부분은 나중에 설명을 들을 수 있을 것