코린이의 소소한 공부노트

1. 입력 - 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. - 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. - 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. - 1 ≤ N ≤ 100,000 - 1 ≤ M ≤ 100,000 - 1 ≤ i ≤ j ≤ N 2. 출력 - 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 3. 예제 4. 코드 import java.util.*; import java.io.*; class Main { static int n; static int[] tree; public static void main(String[] args) throws IOException { Buffe..

1. 개념 정리 1) 이진 인덱스 구조를 활용하여 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조 2) 펜윅 트리(Fenwick Tree)라고도 불린다. 3) 세그먼트 트리보다 구현하기 편하고 속도가 빠르다. - 세그먼트 트리는 필요한 리프 노드만 채우기 때문에 불완전 트리지만, 인덱스 트리는 리프 노드를 모두 채워서 만들기 때문에 인덱스를 활용할 수 있다. - 데이터의 개수가 N개일 때, 세그먼트 트리를 만들기 위해 필요한 공간을 통상 4*N만큼 준비했었다면 인덱스 트리를 만들 때는 N만큼만 준비하면 된다. 4) 인덱스는 1부터 사용하고, 인덱스를 활용하면 해당 인덱스의 값이 몇 개의 데이터의 합인지 알 수 있다. - 8비트로만 간단히 예시를 들어보면, 3과 -3을 비트 and 연산을 해보면 다..

1. 개념 정리 1) 여러 개의 데이터가 연속적으로 존재할 때 특정 구간의 데이터의 합을 담은 이진 트리 2) 실제 구현은 트리가 아닌 배열로 하게 된다. - 배열은 인덱스가 있어 접근성이 좋기 때문이다. 3) 세그먼트 트리를 이용한 구간 합 처리의 시간 복잡도는 O(lgn)이다. 2. 예시 1) 구간 합의 데이터가 될 배열을 준비한다. int[] arr = {1,2,3,4,5,6,7,8}; 2) 구간 합 트리가 될 배열도 준비한다. int[] tree = new int[32]; // arr.length * 4 // 데이터의 개수가 N개일 때 필요한 부분 합 트리의 공간은 // N 이상의 2의 거듭제곱수 중 가장 작은 것 * 2이다. // 여기서 N=8이므로 8 이상의 2의 거듭제곱수 중 가장 작은 것은..

1. Input 1) int[] nums 2) int[] queries 2. Output 1) 다음을 따라 만든 배열을 반환 - i번째 요소에 nums의 요소들의 합이 queries[i] 이하인 nums의 부분 배열 중 길이가 가장 긴 것을 찾아 그 길이를 저장 - 부분 배열은 nums상에서 연속적일 필요는 없다. 3. Constraint 1) n == nums.length 2) m == queries.length 3) 1 4 5. Code 1) 첫 코드(2023/06/26) class Solution { public int[] answerQueries(int[] nums, int[] queries) { int[] ans = new int[queries.length]; Arrays.sort(nums); ..

1. Input 1) int[][] ranges - ranges[i] = [start_i, end_i] 2) int left 3) int right 2. Output 1) [left, right] 범위의 정수가 모두 ranges에 담겨 있다면 true, 아니면 false를 반환 3. Constraint 1) 1

목표: 배열의 부분 합을 계산하는 클래스 구현 - 생성자 - int sumRange(int left, int right) 1. Input 1) 생성자: int[] nums; 2) sumRange(): 부분 합을 구할 인덱스의 범위 2. Output 1) sumRange(): nums[left]부터 nums[right]까지의 합 3. Constraint 1) 1

1. Input 1) int n 2. Output 1) n에 대한 pivot integer를 찾아서 반환 - pivot integer란 1부터 x까지의 합이 x부터 n까지의 합과 같게 되는 x를 말한다. 2) pivot integer가 없다면 -1을 반환 3. Constraint 1) 1

1. Input 1) int[] arr 2. Output 1) arr에서 구할 수 있는 모든 부분 배열 중 그 길이가 홀수인 것의 요소의 총합을 반환 3. Constraint 1) 1 [1,4,2,5,3] = 15 - 따라서 총합인 58을 반환한다. 5. Code 1) 첫 코드(2023/04/13) int sum = 0; for(int l=1 ; l

1. Input 1) int[] nums 2) int k 2. Output 1) nums의 부분배열 중 길이가 k인 것을 찾은 다음, 그 중 평균값이 가장 큰 부분배열의 평균을 double로 반환 3. Constraint 1) n == nums.length 2) 1

1. Input 1) int[] nums 2. Output 1) nums[i]를 기준으로 왼쪽 요소의 합과 오른쪽 요소의 합을 구한 후, 그 차이를 차례대로 담은 int[] 3. Constraint 1) 1 왼쪽합=10, 오른쪽합=11 -> 1 - nums[2] = 8 -> 왼쪽합=14, 오른쪽합=3 -> 11 - nums[3] = 3 -> 왼쪽합=22, 오른쪽합=0 -> 22 5. Code 1) 첫 코드(2023/02/27) int[] answer = new int[nums.length]; int totalsum = 0; for(int i=0 ; i