목록합배열 (1)

평범한 연구소

[JAVA] 구간 합 (1차원, 2차원 배열)

합 배열합 배열은 원본 배열을 전처리한 배열합 배열 S 공식 (S=합배열, A=원본배열)S[i] = A[0] + A[1] + A[2] + ... + A[i-1] A[i] ~ A[j] 까지의 합(구간합)을 합 배열 없이 구하는 경우, 시간 복잡도는 O(N)코딩테스트에서 시간 복잡도는 생명🏄‍♀️ 구간 합합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 알고리즘구간 합 공식 (S=합배열)S[j] + S[i-1]  // i ~ j 까지 구간의 합 1차원 배열의 구간 합1. 배열의 구간 합을 구하는 작업을 선행한다.2. 구간 합 공식을 대입하여 결과를 도출한다.백준 11659번 예제로 공부해보자.https://jeongsoyeon.tistory.com/157 2차원 배열의 구간 합나는 2차원 배열의 경우..
JAVA/알고리즘 공부 2025. 3. 8. 18:04
이전 Prev 1 Next 다음