TIL- 누적합(구조합) 알고리즘이란?

2024-06-03

오늘의 학습 🌠

---

---

• 👨🏻‍💻 누적합 핵심 개념
  • 수들이 나열되어 있을 때 특정 구간의 합을 쉽게 구해주는 알고리즘

---

• 🙋🏻‍♀️ : 인덱스 3부터 10까지의 누적합(구간합)은 무엇인가요?

• 👨🏻‍🏫 : 4+6+2+3+5+9+23+4 = 56입니다.

• 🙋🏻‍♂️ : 인덱스 8부터 10까지의 누적합(구간합)은 무엇인가요?

• 👨🏻‍🏫 : 9+23+4 = 36입니다.

• 🙅🏻‍♀️ : 이 과정은 너무 비효율적이지 않은지.. 만약 만 번이 넘는 과정이라면?

---

→ 이러한 과정을 토대로 Prefix Sum, 누적합(구간합) 알고리즘을 고안해내게 되었습니다.

• “S” : 합 배열, “A” : 원본 배열

S[0] = A[0];

for(int i = 1; i < 8; i++)
{
		S[i] = S[i-1] + A[i];
}

• 여기서 S[3] = 25는 A[0]+A[1]+A[2]+A[3] 입니다.

• 즉, A[0]부터 자기 원본 배열이 A[3] 까지의 합을 의미합니다.

• 그렇다면 40은 무엇일까요?

• A[0]부터 자기 인덱스 값인 A[6]까지의 합을 의미할 것입니다.

• 우리는 이런 합 배열을 가지고 누적합을 간단히 구할 수 있습니다!

---

🙋🏻‍♂️ : 인덱스 3부터 6까지의 누적합(구간합)을 구하고 싶어요!

💻 : S[6] - S[2] = 40 - 18 = 22

• 확인 : A[3]~A[6] : 7+8+4+3 = 22

🙋🏻‍♀️ : 인덱스 1부터 7까지의 누적합(구간합)을 구하고 싶어요!

💻 : S[7] - S[0] = 41 - 5 = 36

→ S[1]+ S[1] + S[2]+S[3]+S[4]+S[5]+S[6]+S[7]까지의 합을 구하는 과정보다 굉장히 간편해 집니다.

---

❓ 원본 배열 A에 대해서 i~j까지 구간합을 구할 때 S 합배열로 구한다고 하면 어떻게 해야될까요?

• S[j] - S[i-1]
• 3~8까지 구간합이라면 S[8]-S[2]이므로

🍮 누적합 단점

• 원본 배열의 인덱스 3번째의 수가 바뀌었을 경우 합 배열의 인덱스 3번부터 끝까지 바꾸어 주어야 합니다.

추가 🕤

---

🐱‍🏍— —🤸🏻‍♀️ ~~~ 야~호~