빈스토리

세그먼트 트리란 통계 트리라고도 하며 배열의 구간 합을 구할 때 적합한 구조입니다! 백준 2042번 문제가 세그먼트 트리를 사용하는데 세그먼트 트리를 공부하고 풀어보면 좋을 것 같습니다 :) 저는 나동빈님의 블로그 글을 보고 공부하여 문제를 풀었고 그것을 제 블로그에 기록했습니다. 참고로 아래 설명에 나오는 제 코드는 java로 작성한 코드입니다! [예시] 배열 {1, 2, 3, 4, 5, 6, 7, 8}의 구간합을 세그먼트 트리로 나타내면 아래와 같습니다. 루트 노드는 모든 구간의 합으로 이루어져 있고 이는 왼쪽과 오른쪽 노드의 합을 의미합니다. 이것을 이용하여 세그먼트 트리를 생성하는 메소드를 작성해 보겠습니다. 세그먼트 트리 생성(init) long init(int start, int end, in..

순열(Permutation) 서로 다른 것들 중 몇 개를 뽑아서 한줄로 나열하는 것 (nPr = n!) n>12인 경우, 시간 복잡도 폭발적으로 상승 void permutation(int cnt) { if (cnt == r) { // 순열 생성 완료 return; } for (i 1 to n) { if (isSelected[i]) continue; numbers[cnt] += i; isSelected[i] = true; permutation(cnt + 1); isSelected[i] = false; } } 조합(Combination) 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것 void combination(int cnt int index) { if(cnt == r) { // 조합 생성 완료 ..

스택(Stack) Stack은 LIFO구조로 나중에 들어온 객체가 먼저 나가는 자료구조입니다. 꺼내려면 위에서부터 꺼내야하고 정리할 때는 아래서부터 쌓는 장롱 속 이불과 같은 구조입니다. Java에서는 java.util 패키지에 구현된 Stack을 사용합니다. Stack stack = new Stack(); stack.push(1); stack.push(2); stack.pop(); 큐(Queue) Queue는 FIFO구조로 처음 들어온 객체가 먼저 나가는 자료구조입니다. 한 줄 서기와 같이 먼저 줄을 선 사람이 먼저 나가는 구조 입니다. Java에서는 java.util 패키지의 Queue를 사용하지만 선언 시에는 LinkedList 또는 ArrayDequeue를 사용합니다. Queue는 Interfac..