# tree
TreeSet / TreeMap / HashSet / HashMap
HashMap 클래스 키와 값을 해시 함수를 사용하여 매핑하여 데이터를 저장하는 자료구조입니다. 해시 함수를 사용하기 때문에 키를 빠르게 검색할 수 있습니다. 키와 값의 순서가 보장되지 않습니다. 키와 값 모두 null을 허용합니다. 키를 빠르게 검색하지만, 데이
이진 탐색 트리 (Binary Search Tree)
이진 트리와 이진 탐색 트리(BST)의 차이 이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree, BST)는 트리(Tree) 자료구조의 일종으로, 노드(Node)들이 서로 연결된 구조를 가지고 있다. 이 둘은 매우 비슷한 구조를 가지고
트리(Tree)
노드와 링크로 구성된 자료구조 (그래프의 일종, Cycle 없음) 계층적 구조를 나타낼 때 사용 -폴더 구조 (디렉토리, 서브 디렉토리) -조직도, 가계도, ... 트리의 구조 노드(Node) : 트리 구조의 자료 값을 담고 있는 단위 에지(Edge) : 노드 간의
백준 1949
문제'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.선정되지 못한 마을에 경각심을
백준 2533
문제깊이 우선 탐색(DFS)으로 DP를 계산DP에는 해당 노드까지의 최소 얼리어답터 수를 저장한다.그러면 각각의 노드에서는, 무조건 아래의 두 경우 중 하나이다.1) 해당 노드가 얼리어답터일 경우 무조건 자식 노드가 얼리어답터2) 해당 노드가 얼리어답터가 아닐 경우 자
[자료구조/알고리즘] Tree Traversal 이론 기초
해당 포스터는 자료구조 학습 내용 중 Tree Traversal 기초이론에 대한 내용을 정리한 것입니다.
[자료구조/알고리즘] Binary Search Tree 이론 기초
해당 포스터는 자료구조 학습 내용 중 Binary Search Tree 기초이론에 대한 내용을 정리한 것입니다.
[Java] LCA
최소 공통 조상(LCA, Lowest Common Ancestor)은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다.
백준 2213
문제어떠한 트리의 임의의 노드 정점은(풀이에서는 간편함을 위해 첫 번째 노드라 함)최대 독립집합에 포함되거나, 안되거나 무조건 두 경우 중 하나포함을 1, 미포함을 0으로 나타냄1번째 노드부터 깊이우선탐색(DFS)dpi : i번째 노드를 루트노드로하는 서브트리에서, 최
[Java] 이진 힙(Heap)
완전 이진 트리의 일종을 우선순위 큐를 위하여 만들어진 자료구조입니다.여기서, 우선순위 큐를 위해서 만들어졌다고 했는데, 우선순위 큐가 무엇인지 간단히 소개하고 넘어가겠습니다.우선순위의 개념을 큐에 도입한 자료 구조라고 생각하면 됩니다.기존의 큐(Queue)같은 경우에
[Java] 이진 트리(Binary Tree) + 이진 탐색 트리(Binary Search Tree)
이진 트리(Binary Tree)는 자식 노드가 최대 두개인 노드들로 구성된 트리를 의미합니다.
백준 15681
문제R을 루트노드로 갖는 트리에서,N + 1 번째 노드를 루트노드로 가지는 서브트리의 정점의 개수 저장(인덱스를 0부터 썼기 때문에 +1을 해주었다)node + 1 번째 노드를 루트노드로 갖는 트리의 각 정점들에 대해 각 정점을 루트노드로 갖는 서브트리의 정점의 개수를
백준 5639
문제문제 상단에 이진트리의 조건에 따르면루트 노드보다 작은 노드들은 모두 루트 노드 왼쪽 서브 트리루트 노드보다 큰 노드들은 모두 루트 노드 오른쪽 서브트리에 위치한다따라서 전위 순위로 입력 받은 첫 노드를 루트 노드에 놓고후에 이어지는 입력들은 루트 노드부터 각 노드