📚 목차
요약
- 구간 합이란, 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 알고리즘이다.
1. 구간 합
1. 구간 합이란?
- 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 알고리즘
- 그냥 0번째 요소부터 n번째 요소까지 더한 값을 배열로 만드는 것
2. 구간 합 배열의 구조 예시
- 배열 A의 2번째 인덱스부터 4번째 인덱스 까지의 합은 합 배열의 4번째 인덱스 빼기 2번째 인덱스와 동일하다.
- A[2] + A[3] + A[4] = S[4] - S[2]
2. 문제 풀어보기
🖥️ 백준 11659 - 구간 합 구하기4
11659번: 구간 합 구하기 4