바이너리 인덱스 트리(Binary Indexed Tree, BIT)는 2진법 인덱스 구조를 활용해 구간 합 문제를 해결해 줄 수 있는 자료구조이다. 펜윅 트리(fenwick tree)라고도 한다. 바이너리 인덱스 트리를 구현하려면, 어떤 수 X를 이진수로 나타냈을 때, 0이 아닌 마지막 비트를 알아야한다. 0이 아닌 마지막 비트를 찾는 방법 어떤 수 X의 0이 아닌 마지막 비트를 찾기 위해서 X & -X를 계산하면 된다. L[i]는 i를 2진수로 나타냈을 때, 0이 아닌 마지막 비트값을 저장하고 있는 배열이다. 즉, 3을 이진수로 나타냈을 때 011 이므로 0이 아닌 가장 마지막 비트값은 L[3]=1 이다. Tree[i]는 arr[i]로부터 앞으로 L[i] 개의 합을 저장하고 있는 배열이다. - Tree..
💡 PriorityQueue 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 우선순위 큐를 구현하는 방식인 힙(Heap)에서 데이터를 넣었다가 꺼내는 작업은 정렬하는 작업과 동일하다. 이 경우 시간복잡도는 O(NlogN)이 된다. 따라서 순서 상관없이 주어진 데이터를 우선순위 큐에 넣기만 하면 루트노드는 가장 우선순위가 큰 값을 가지고 먼저 제거된다. 문제에서는 N번째로 큰 수를 찾는 문제로 Collections.reverseOrder()메서드를 활용하여 높은 숫자가 우선순위가 될 수 있도록 한다. import ja..
우선순위 큐 (PriorityQueue) 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 우선순위 큐를 구현하는 방법은 다양하다. ① 단순히 리스트를 이용하여 구현 ② 힙(Heap)을 이용하여 구현 데이터의 개수가 N개일 때, 구현 방식에 따라 시간 복잡도가 다르다. 우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. 이 경우 시간 복잡도는 O(NlogN) 이다. 힙(Heap)의 특징 힙(Heap)은 완전이진트리의 일종 힙(Heap)에서는 항상 루트노드를 제거한다. 최소 힙(min heap) 루트노드가 가장 작은 값을 가진다. 따라서 값이 ..
Stack은 마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO, Queue는 먼저 들어간 데이터를 먼저 꺼내는 FIFO 구조이다. Stack의 메서드 메서드 설명 boolean empty() stack이 비어있는지 Object peek() Stack의 맨 위에 저장된 객체 반환 Object pop() stack의 맨 위에 저장된 객체를 꺼내 반환 Object push(Object o) stack에 객체를 저장 int search(Object o) stack에서 주어진 객체를 찾아 그 위치를 반환, 못찾으면 -1 반환 💡 위치가 1부터 시작 Queue의 메서드 메서드 설명 boolean add(Object o) Queue에 객체를 추가 boolean offer(Object o) Queue에 객체를 저장 ..
이진트리 이진트리 순회(DFS) 전위순회: 중 - 왼 - 오 중위순회: 왼 - 중 - 오 후위순회: 왼 - 오 - 중 import java.util.*; class Node { int data; Node lt, rt; // 왼쪽 주소, 오른쪽 주소 저장 public Node(int val) { data = val; lt = rt = null; } } class Main { Node root; public void DFS(Node root) { if (root == null) return; else { // System.out.print(root.data + " "); 전위순회 DFS(root.lt); // System.out.print(root.data + " "); 중위순회 DFS(root.rt); /..
2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 💡 이진탐색(Binary Search) 문제 구하고자 하는 것 : 두 공유기 사이의 최대거리 lt = 1 rt = arr[n-1] ➜ 너무 세세하게 생각X. 그냥 가장 멀리있는 좌표 선택 ➜ 답(두 공유기의 최대거리)은 lt~rt 사이에 확실하게 있다. mid = (lt + rt ) / 2 가장 인접한 두 공유기의 거리를 mid라고 했을 때, 답이 가능한지 검증 ➜ 공유기의 배치 수를 count하는 함수 생성 ..
메모이제이션(Memoization) 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행속도를 빠르게 하는 기법이다. 값을 기록해 놓는다는 점에서 캐싱(Caching) 이라고도 한다. 피보나치 수열 메모제이션을 추가한 방법의 시간복잡도는 O(N) 이다. static int[] fibo; // 피보나치 수열 값을 저장할 배열 선언 public int DFS(int n) { if(fibo[n] > 0 ) return fibo[n]; // 메모이제이션 ✨ if (n < 2) return fibo[n] = n; else return fibo[n] = DFS(n - 1) + DFS(n - 2); } 조합수 💡 nCr =n-1C..
💡 이분탐색(Binary Search) 문제 ✅ 구하고자 하는 것 : N개를 만들 수 있는 랜선 최대 길이lt = 1rt = 랜선 길이 중 가장 긴 값 ➜ lt ~ rt 사이의 구하고자 하는 값이 확실하게 있다.자를 랜선의 길이가 mid이면 답으로써 가능한 숫자인가 검증 ➜ 얻을 수 있는 랜선의 개수를 구하는 함수 생성얻을 수 있는 랜선의 개수가 N개 보다 크거나 같으면 자를 랜선의 길이를 늘려도 됨 lt=mid+1반대면 랜선의 길이 줄이기 rt=mid-1👨🏻💻 실행코드import java.util.*;import java.io.*;public class Main { private static BufferedReader br = new BufferedReader(new InputStrea..
2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 💡 이진탐색(Binary Search) 이진탐색으로 해결할 수 있는 문제들의 유형은 비슷하다. lt와 rt를 정하고 lt ~ rt 사이에 찾고싶은 답이 분명히 있다라는 확신이 있는 문제에 적용한다 + 최대/최소 구하고자 하는 것 : 절단기를 설정할 수 있는 높이의 최대값 lt = 0 : 절단기에 설정할 수 있는 가장 작은 값 rt : 나무의 길이 중 가장 긴 값 ➜ lt ~ rt 사이의 구하고자 하는 값이 확실하게 있다. ..
이진 탐색(Binary) 알고리즘을 이용해서 해결해야 하는 문제 유형은 비슷하다. 주로 최대/최소를 물어본다. 1. lt 와 rt를 정했을 때, lt ~ rt 사이에 분명 답이 있다는 확신 2. mid = (lt+rt)/2 가 답으로써 가능한 숫자인지 검증 3. 최대/최소를 구해야 하므로 더 나은 답이 있는지 확인 몇 가지 알고리즘 문제를 통해 알아보자. 문제 1 9 3 ( 9가지의 노래를 3개의 DVD에 넣을 때 DVD의 최소용량) 1 2 3 4 5 6 7 8 9 (분) 구하고자 하는 것 : DVD의 최소 용량 lt = 9 : 최소한 9분(제일 긴 노래)을 넣을 수 있어야 한다. rt = 45 : 최대한 노래 전부는 넣을 수 있어야 한다. ➜ 답(DVD의 용량크기)은 9 ~ 45 사이에 확실하게 있다...
버블 정렬(Bubble sort)서로 인접한 두 수를 비교하여 정렬하는 알고리즘이다. 시간복잡도 : O(n2) public void bubble_sort(int arr[], int n) { for (int i = n - 1; i > 0; i--) { for (int j = 0; j arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; }}}} 선택 정렬(Seleciton sort)① 정렬되지 않은 부분 중 최소값을 찾는다.② 그 값을 정렬되지 않은 부분의 맨 앞의 수와 교체한다.③ 정렬된 ..
