data structure + algorithm
2022. 6. 29.
java/ 기존 배열의 합 배열을 만들어 구간 합 구하기
원본 배열에 대한 합 배열을 미리 생성해 가져다 쓰는 기법으로 입력 값의 범위가 넓을 때 시간 복잡도를 줄이기 위해 사용한다. 일차원 배열 원본 배열 int[] arr 생성 int[] arr = new int[] {1, 3, 5, 7, 9, 11}; 생성 결과 1 3 5 7 9 11 합 배열 int[] sum 생성 위와 같이 존재하는 원본 배열 arr에 대해 합 배열 int[] sum을 생성한다. int[] sum = new int[arr.length]; sum[0] = arr[0]; for (int i = 1; i < arr.length; i++) { sum[i] = sum[i - 1] + arr[i]; } 생성 결과 1 4 9 16 25 36 합 배열을 이용해 배열의 구간 합 구하기 1 3 5 7 9..
