JH-Labs

Balanced Tree (불균형) 이진탐색트리의 문제점은 최악의 경우 O(N)이 발생한다는 것이다. Balanced Tree는 항상 균형을 맞추어진 상태로 유지함으로써 O(logN)의 성능을 보인다. 하지만 데이터의 삭제, 삽입, 갱신이 발생할 때 Balance를 유지하기 위한 연산이 추가로 필요하게 된다는 단점이 있다. Balanced Tree의 종류로 AVL Tree와 레드블랙트리, 2-3 Tree, 2-3-4 Tree, B Tree 등이 있다. B-Tree는 다차원트리 B-Tree는 Balanced Tree이면서 다차원 트리이다. 하나의 노드가 가질 수 있는 자식 노드의 개수(링크 개수)를 M이라고 했을 때 하나의 노드에 '최대' M-1개의 자료를 담을 수 있으며 이 경우 M차 다차원 트리라고 한..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

TreeMap - Key-Value로 이루어진 entry를 Tree에 저장하는 자료구조 - Key를 기준으로 '정렬'한 형태의 Tree임 (~이진탐색트리) - Tree중에서도 레드블랙트리를 기반으로 함(이진탐색트리에서 balanced tree) - 즉, 모든 노드에서 왼쪽 서브트리의 값은 오른쪽 서브트리의 값보다 작음 - HashMap보다 성능이 떨어짐 - 하지만 정렬된 상태로 Map을 유지하거나 Key에 대해 범위 탐색을 할 경우 HashMap보다 유리함 cf. Heap과 구분해야 하는데, Heap은 루트 노드가 가장 우선순위를 큰 값을 갖는 형태지만 정렬되어 있지는 않음 - 최소 힙에서 최대값을 삭제하는 연산은 O(logN) 이라고 착각하기 쉬우나, O(N) 이 소요됨 - 이유는 힙은 정렬되어 있지 ..

이진탐색트리(Binary Search Tree) - 최대 자식노드를 2개 갖는 이진트리 - 정렬된 상태로 유지되기 때문에 탐색 효율이 좋음 (중위순회시 정렬된 상태로 출력됨) - Balanced Tree가 아니기 때문에 극단적으로 모든 노드가 자식노드를 1개씩만 갖게 되면 O(n) 성능을 보임 Red-Black Tree - 이진탐색트리의 일종이지만 Balanced Tree이기 때문에 성능을 O(logN)으로 보장함 - 이진탐색트리의 일종이므로 왼쪽 서브트리의 모든 값은 오른쪽 서브트리의 모든 값보다 작아야 함(정렬됨) - Red-Black Tree는 이진탐색트리 중에서 성능이 가장 좋다. - 따라서 리눅스 커널의 프로세스 관리, Java 8이상 HashMap에서 해쉬 블록의 value, 함수형 프로그래밍..

코드 /** * https://www.acmicpc.net/problem/12919 */ import java.io.*; public class Main { private static String S, T; private static final char A = 'A'; private static final char B = 'B'; public static void main(String[] args) throws IOException { init(); var result = solve(T); var bw = new BufferedWriter(new OutputStreamWriter(System.out)); bw.write(result ? "1" : "0"); bw.flush(); bw.close(); } ..

처음에는 선형탐색을 생각했지만 정렬을 한 번만 해 둔다면 이진탐색이 성능 상 더 좋은 알고리즘이 될 것으로 판단했다. [자바 소스코드] import java.util.Arrays; import java.util.Scanner; public class Main { static int[] inputs; public static void main(String[] args){ Scanner sc = new Scanner(System.in); int len = sc.nextInt(); inputs = new int[len]; for(int i=0; i target){ end = mid - 1; } else{ start = mid + 1; } } System.out.println("0"); } } [시간복잡도 분석..