구간 합1 [Algorithm] 구간 합 (Prefix Sum) 구간 합 (Prefix Sum) ■ 정의 - 수들의 나열에서 특정 구간의 합을 의미 - 보통 1차원 배열에서 인덱스 사이의 값들의 합을 구하는데 사용 ■ 구간 합 알고리즘 - 구간 합 공식: sum[j] - sum[i - 1] // i에서 j까지의 구간 합 - 합 배열(P)을 미리 계산해 두면 구간 합은 한 번에 계산 가능 - 알고리즘의 시간복잡도: O(1) ■ Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class No11659 { public static void main(String[] args) .. 2023. 5. 1. 이전 1 다음