공부 기록/알고리즘
Do it! 알고리즘 코딩테스트 with JAVA - (3) 구간 합
yurison
2023. 6. 4. 08:23
구간 합
- 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
- 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 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