구간 합
- 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
- 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.
- 구간 합 배열을 만드는 공식 : S[i] = S[i - 1] + A[i]
- 구간 합을 구하는 공식 : i에서 j까지의 구간 합 => S[j] - S[i - 1]
문제 풀이
https://yurison.tistory.com/298
[백준/자바] 11659 - 구간 합 구하기 4
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int line = sc.nextInt(); int[] sumArr = new int[n + 1]; for(int i=1; i
yurison.tistory.com
'공부 기록 > 알고리즘' 카테고리의 다른 글
| Do it! 알고리즘 코딩테스트 with JAVA - (6) 스택과 큐 (0) | 2023.06.05 |
|---|---|
| Do it! 알고리즘 코딩테스트 with JAVA - (5) 슬라이딩 윈도우 (0) | 2023.06.05 |
| Do it! 알고리즘 코딩테스트 with JAVA - (4) 투 포인터 (0) | 2023.06.04 |
| Do it! 알고리즘 코딩테스트 with JAVA - (2) 디버깅 (0) | 2023.06.03 |
| Do it! 알고리즘 코딩테스트 with JAVA - (1) 시간복잡도 (0) | 2023.06.03 |
