Develog

문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 제출한 답안 package BOJ; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class BOJ_1068 { private static int N; private static boolean[] visited; private static int[][] graph; private static int leafCount = 0; public stat..

🎯 Heap Heap(힙)은 최대 값 또는 최소 값을 빠르게 찾기 위한 자료구조입니다. 일반적으로 우선순위 큐(Priority Queue)와 같이 사용됩니다. 부모 노드와 자식 노드 간의 크기 관계를 이용하여 효율적인 삽입, 삭제, 탐색 연산을 수행할 수 있는 트리 기반의 자료구조입니다. Heap의 구조 Heap은 완전 이진 트리(Complete Binary Tree)의 형태를 갖고 있습니다. 완전 이진 트리는 모든 레벨에서 노드들이 꽉 차있고, 마지막 레벨에서는 왼쪽부터 순서대로 채워져 있습니다. Heap은 크게 Max Heap과 Min Heap으로 나눌 수 있습니다. Max Heap은 부모 노드가 자식 노드보다 큰 값을 가지는 Heap이고, Min Heap은 부모 노드가 자식 노드보다 작은 값을 가지..

🎯 Trie 트라이(Trie)는 검색 트리의 일종으로, 문자열 탐색에 사용되는 자료 구조입니다. 트라이는 문자열을 이진 검색 트리(Binary Search Tree)처럼 저장하지 않고, 각 노드의 문자열을 표현합니다. 이러한 방식으로 트라이는 문자열 검색 및 삽입에서 높은 성능을 보이며, 특히 문자열 검색에 대해 O(m)의 시간 복잡도를 가집니다. (m은 검색하는 문자열의 길이입니다.) Trie의 구조 ⭐️ {"A", "to", "tea", "ted", "ten", "i", "in", "inn"} 을 트라이로 구현 트라이는 문자열을 탐색하기 위한 자료구조이므로 문자열 탐색을 위해서는 다음 글자에 해당하는 노드를 타고 따라가면 된다. 또 트라이의 중요한 속성 중 하나는 루트에서부터 내려가는 경로에서 만나는..

🎯 Tree Tree는 하나의 root 노드에서 시작하여 여러 개의 자식 노드를 가질 수 있는 자료구조입니다. 각 노드는 부모-자식 관계로 이어져 있으며, 루트 노드는 부모가 없는 특수한 노드입니다. Tree는 계층적인 구조를 나타내는 데에 유용하게 사용됩니다. Tree의 용어 루트노드 : 트리의 최상위에 있는 노드 [A] 자식노드 : 노드 하위에 연결된 노드 [B,C,D]는 [A]의 자식노드 부모노드 : 노드의 상위에 연결된 노드 [A]는 [B,C,D]의 부모노드 차수(Degree) : 자식노드의 수 [A]의 Degree는 3 이파리노드(Leaf) : 자식이 없는 노드(= 단말노드 : Terminal Node) [K,L,F,M,N,I,O,P] 형제노드 : 동일한 부모를 가지는 노드 [B,C,D]는 부모..