전체 글

자료구조 - [ Binary Heap ]

Binary Heap Heap은 트리에 기반한 특별한 자료구조로 우선순위가 높은 데이터가 부모로 배치되고 우선순위가 낮은 데이터가 자식으로 배치되는 관계를 가지고 있다. 삽입 순서와 상관없이 항상 우선순위가 가장 높은 데이터를 꺼내거나 삭제하기 때문에, 우선순위가 필요한 대기열이나 데이터 정렬이 필요할 때 사용할 수 있다. Heap에는 Binary Heap, Fibonacci Heap 등이 존재한다. Binary Heap은 Complete Binary Tree의 구조를 가지고 있으며, 삽입과 삭제 시 트리를 우선순위에 따라 재배치하는 과정을 거친다. Binary Heap 삽입 삽입시 항상 맨 마지막 Leaf 노드로 삽입되며, 삽입 후 부모의 우선순위와 비교해 Swap 한다. 부모의 우선순위보다 낮을 때까..

자료구조 - [ Red-Black 트리 ]

Red-Black 트리 Red-Black 트리는 AVL 트리와 비슷하게 스스로 균형 잡는 이진 탐색 트리로, 삽입/삭제 시 노드가 가지고 있는 색깔을 이용한 규칙을 통해 불균형을 완화하는 트리이다. 노드의 재배치를 빈번하게 실행하지 않기 때문에 삽입/삭제 연산이 많은 경우 AVL 트리보다 평균적으로 더 나은 성능을 가지고 있고, AVL 트리보다 덜 균형하기 때문에 탐색 횟수는 더 많을 수 있다. => 삽입/삭제 연산이 빈번하면 Red-Black 트리 / 탐색의 성능이 더 중요한 경우 AVL 트리를 이용하는 것이 낫다. 모든 노드는 빨강 또는 검정 루트 노드는 최종적으로 항상 검정 모든 Leaf 노드는 루트 노드와 동일한 색상을 가짐 모든 빨강 노드의 자식은 검정 노드(검정 노드의 자식은 상관 X) => ..

자료구조 - [ AVL 트리 ]

AVL 트리 AVL(Adelson-Velsky And Landis) 트리는 스스로 균형 잡는 이진 탐색 트리로 삽입과 삭제 시 트리의 균형도를 계산하여 불균형을 완화하는 트리이다. AVL 트리는 균형도만 존재한다. 균형도가 절댓값 2 이상이면 불균형 트리이다. 균형도를 계산한 후 트리의 회전 여부를 판단하여 불균형할 경우 LL, RR, LR, RL 회전을 한다. null 노드인 경우 높이는 -1, 노드가 존재할 경우 노드의 높이는 Max(좌측 자식 노드 높이, 우측 자식 노드 높이) +1 균형도 = 좌측 자식 노드 높이 - 우측 자식 노드 높이 균형도가 양수인 경우 좌측 서브 트리가 비대한 트리, 음수인 경우 우측 서브 트리가 비대한 트리 Leaf노드는 항상 높이와 균형도가 0이다. LL 불균형 트리 부..

백준 - [ 11051번: 이항 계수2 ]

이항 계수 2 문제 자연수 N\(N\)과 정수 K\(K\)가 주어졌을 때 이항 계수 (NK)\(\binom{N}{K}\)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N\(N\)과 K\(K\)가 주어진다. (1 ≤ N\(N\) ≤ 1,000, 0 ≤ K\(K\) ≤ N\(N\)) 출력 (NK)\(\binom{N}{K}\)를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 5 2 예제 출력 1 10 처음엔 아래의 공식을 이용했다. 분자, 분모를 각각 factorial 함수로 계산했는데 n이 커질수록 int의 최대 범위를 넘어나서 틀렸다. public class Main { public static int factorial(int num, int cnt) { if (nu..

자료구조 - [ 이진 탐색 트리 ]

이진 탐색 트리는 부모 노드 기준 작은 키는 좌측 자식 노드로, 큰 키는 우측 자식 노드로 유지하는 트리이다. 이러한 자료 구조는 데이터 탐색 시 노드를 이동하면서 재귀적으로 탐색 가짓수를 1/2로 줄여나가며 찾는다. 그러나 이진 탐색 트리는 키의 삽입 순서에 따라 트리의 균형이 달라지기 때문에 트리의 균형을 예측하기가 어렵다는 단점이 있다. 1. 이진 탐색 트리 삽입 부모 노드보다 작으면 좌측 자식 노드로, 부모 노드보다 크면 우측 자식 노드로 배치한다. 따라서 부모 노드 기준 좌측 끝에 있는 노드는 트리에서 가장 작은 키가, 부모 노드 기준 우측 끝에 있는 노드는 트리에서 가장 큰 키가 된다. 2. 이진 탐색 트리 삭제 노드를 삭제 시에도 이진 탐색 트리의 구조를 유지해야 하기 때문에 특정한 규칙에 ..

자료구조 - [ 이진 트리 순회 ( 깊이 우선 / 너비 우선 ) ]

1. 깊이 우선 탐색 1) 전위 순회 (pre-order) 부모 노드를 선 방문 후 좌측 서브 트리와 우측 서브 트리를 방문하는 방법 void visit(Node node) { System.out.println(node.data); } void preOrder(Node parent) { if (null == parent) { return; } visit(parent); preOrder(parent.left); preOrder(parent.right); } 2) 중위 순회 (in-order) 좌측 서브 트리를 방문하고 부모를 방문 후 우측 서브 트리를 방문하는 방법 void visit(Node node) { System.out.println(node.data); } void inOrder(Node pare..