트리

#1. 문제https://www.acmicpc.net/problem/4256  #2. 풀이 1. 트리의 순회 [자료구조]#5_트리[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다.  Overview 개념이진트리순회이진 탐색 트리균형 이진트리AVL 트리레드-블랙 트리Map, Set힙 #0. 개념1. 트리? [정의] : 트리는 1:n 관계의webddevys.tistory.com트리 자료구조는 세 가지 순회 방법을 갖습니다. 모두 현재 노드를 기준으로 (1) 전위 순회(루트->왼쪽->오른쪽), (2) 중위 순회(왼쪽->루트->오른쪽), 그리고 (3) 후위 순회(왼쪽->오른쪽->루트)가 있습니다. 대부분의 경우, 주어진 트리 자료구조의 두 가지 순회 내용을 알려주고, 다른 하나의 순회 내용을 구하는 문제..

#1. 문제https://www.acmicpc.net/problem/13511  #2. 풀이 1. 트리 [자료구조]#5_트리[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다.  Overview 개념이진트리순회이진 탐색 트리균형 이진트리AVL 트리레드-블랙 트리Map, Set힙 #0. 개념1. 트리? [정의] : 트리는 1:n 관계의webddevys.tistory.com트리 자료구조는 1:N 관계의 계층 구조를 갖는 그래프의 한 종류입니다. 트리 자료구조의 각 노드 간 연결 관계는 간선으로 나타내며, 순환 구조를 갖지 않기 때문에 "계층 구조"를 형성합니다. 트리 자료구조의 노드 개수가 N개라면, 간선의 개수는 N-1개입니다.  2. LCA [알고리즘]#7_LCA(Least Common Ancest..

#1. 문제https://www.acmicpc.net/problem/1949  #2. 풀이 1. 트리https://webddevys.tistory.com/287 [자료구조]#5_트리[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의webddevys.tistory.com트리 자료구조는 그래프의 한 종류로, 1:N 관계의 계층구조를 갖는 비 선형 자료구조입니다. 만약, 트리 노드의 개수가 N이라면, 간선의 개수는 N-1이며, 비순환 구조입니다.  2. DPhttps://webddevys.tistory.com/311 [알고리즘]#5..

#1. 개념 트라이(Trie)는 검색 트리의 일종으로, 주로 문자열 검색에 사용되는 자료구조입니다. 트라이 검색 트리의 각 노드는 문자열의 특정 문자를 나타내며, 자식 노드에 대한 링크(배열 혹은 맵)를 가지고 있는 트리 자료구조 중 하나입니다. #2. 동작 방식 1. 검색 트라이 검색 트리에서 특정 문자열을 검색할 경우, 해당 문자열의 각 노드를 트라이 검색 트리의 루트 노드를 시작으로 순차적으로 탐색합니다. 만약, 해당 문자열의 각 문자를 나타내는 노드를 모두 성공적으로 찾고, 그 끝에 문자열의 끝을 나타내는 마커가 존재하면, 해당 문자열은 트라이 검색 트리에 존재합니다. 2. 삽입/삭제 트라이 검색 트리에 새로운 문자열을 삽입할 때, 트리의 루트 노드부 시작하여 각 문자에 해당하는 노드를 순차적으로..

#1. 문제 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net #2. 풀이 1. 완전 이진트리 [자료구조]#5_트리 [자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의 webddevys.tistory.com 완전 이진트리는 이진트리의 한 종류로, 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있으며, 마지막 ..

#1. 문제 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #2. 풀이 1. 트리 [자료구조]#5_트리 [자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의 webddevys.tistory.com 트리 자료구조는 1:N 관계의 계층 구조를 갖는 그래프의 한 종류입니다. 트리는 노드와 간선으로 이루어져 있으며, 노드 간의 연결..

#1. 문제 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #2. 풀이 1. 트리 [자료구조]#5_트리 [자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의 webddevys.tistory.com 트리 자료구조는 1:N 관계의 계층 구조를 갖는 그래프의 한 종류입니다. 트리는 노드와 간선으로 이루어져 있으며, 노드 간의 연결 관..

#1. 문제 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #2. 풀이 1. 트리 [자료구조]#5_트리 [자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의 webddevys.tistory.com 트리는 그래프 자료구조의 한 종류로, 1:N 관계의 계층 구조를 갖는 비 선형 자료구..

#1. 개념 1. LCA(Least Common Ancestor) LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가장 깊은 곳에 위치한 공통 조상 노드를 의미합니다. LCA 알고리즘을 효율적으로 구현하는 방법으로 Binary Lifting 기법이 있습니다. 2. Binary Lifting 기법  Binary Lifting 기법은 주어진 트리 자료구조에서 두 노드의 LCA를 찾는 방법 중 하나입니다. 특히, Binary Lifting 기법은 깊이가 깊은 트리에서 두 노드의 LCA를 찾는데 효율적입니다. BL의 핵심 개념은 각 노드에 대해 미리 점프할 수 있는 조상 정보를 계산해 ..

#1. 문제 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net #2. 풀이 1. 트리 [자료구조]#5_트리 [자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의 webddevys.tistory.com 트리는 1:N 관계의 계층 구조를 갖는 비 선형 자료구조입니다. 트리는 노드..