[코테 공부] 구간 합 구하기

 

자료구조 파트의 두 번째 파트인 구간 합이다. 

구간 합을 처음 들었을 때는 그냥 어떤 범위 안 값들의 합을 

반복문 이용해서 구하는 거 얘기하는건가..? 라는 생각이 들었다. 

 

근데 공부하면서 구간 합 공식이라는 것을 처음 알게되었다. ㅋㅋ...

 

---

※구간 합

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

▶ 예를 들어 어떠한 배열의 특정 범위에 있는 값들의 합을 구하고 싶을 때, 

이 값을 빨리 구할 수 있는 알고리즘이다. 

▶ 이 알고리즘은 코딩 테스트에서 사용 빈도가 높다. 

 

★ 합 배열

→ 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. 

→ 합 배열은 다음과 같이 배열의 값을 하나씩 더해서 각 인덱스까지의 합을 저장한 배열이다. 

→ 합 배열을 만드는 공식은 다음과 같다. 

 

★ 구간 합 구하기

→ 구간 합을 구하는 공식은 다음과 같다. 합 배열을 이용해서 구한다. 

→ 이해가 안 된다면 그림을 보면 확실히 이해할 수 있다. 

---

오늘은 구간 합을 알아봤다. 

이제부터 무식하게(?) 반복문을 불필요하게 사용하는 것 보다는

처음 알게 된 구간 합을 쓰는 게 코딩테스트에서는 중요하게 작용할 거 같다는 생각을 했다.