2JINISHAPPY 2JINISHAPPY

AVL Tree AVL 트리는 아래의 성질을 만족하는 BST(Binary Search Tree)의 한 종류다 Tree 상의 모든 Node p에 대해 p의 left subtree와 right subtree의 height 차이가 최대 1을 넘을 수 없다 이러한 성질을 AVL 트리의 Balanced Property라고 하며, 일반적인 BST와 비교했을 때, Search 연산은 완전히 동일하지만 Insert/Delete 연산을 할 때 이 성질이 깨지지 않도록 추가적인 연산을 수행한다 위의 그림에서 12라는 노드를 추가했을 때, 해당 노드를 자손으로 가지는 노드들(4, 8, 15, 10, 12)의 height가 변한다 그리고 노드 15를 봤을 때 왼쪽 서브트리의 height가 2, 오른쪽 서브트리의 height가..

BST(Binary Search Tree)는 아래와 같은 편향 이진 트리(Skewed Binary Tree)일 경우, 성능이 악화된다 Complete Binary Tree일 때 탐색 시간복잡도는 O(log N)이지만, (최악의 경우) 연결리스트의 형태를 한 Skewed Binary Tree일 경우 시간 복잡도가 O(N)에 수렴한다 이러한 편향 현상은 BST에서 Insert, Delete 연산으로 인해 발생할 수 있어서, 이를 보완하기 위한 자료구조로 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)가 존재한다 그 대표적인 예시인 AVL Tree와 Red-Black Tree에서도 아래에서 소개할 Rotation 연산을 이용해서 스스로 Height 균형을 유지하기 때문에..

https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 새로 가입한 알고리즘 스터디에서 풀었던 문제 문자열을 이용한 저장을 구현할 때 딕셔너리를 사용하는게 많이 편해졌다 이 문제도 풀다풀다 코드가 엄청 길어졌지만 최종적으로는 엄청나게 짧아진 문제 이런 식으로 각 child는 모든 anscestor에게 수익을 분배하게 되는데, 각 노드가 얻게 되는 수익의 총합을 구하는 문제였다 트리를 제대로 이해하고 있으면 풀 ..

MST는 그리디 알고리즘을 이용해서 구할 수 있는 트리의 한 형태이다. 연결 그래프(하나의 Connected Component로 이루어진 그래프)에서 생성할 수 있는 부분 그래프이기도 하다. 그래프의 형태를 한 네트워크 회선이 존재할 때, 네트워크 구축 비용을 최소로 하는 경우의 수를 찾고 싶을 때 쓰이기도 한다. 그래프 G=(V,E)와 같고, 각 edge에 weight가 주어져 있을 때, 아래의 두 조건을 만족하는 G'( V(G), T )가 MST이다. 1️⃣ G'은 Connected하다. 2️⃣ G'은 포함할 수 있는 edge들의 cost 총 합을 최소로 한다. 해당 그래프에서는 연두색으로 칠해진 edge들을 선택했을 때 모든 vertex를 포함할 수 있으면서, cost의 합을 최소로 할 수 있기 때..