유혁스쿨

최소공통조상이란? 트리 그래프에서 임의의 두 노드를 선택했을 때, 선택한 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모노드를 탐색할 때 처음 공통으로 만나게되는 부모노드를 말한다. 핵심이론 트리의 높이가 크지 않을 때(시간복잡도 ↓)의 예시 ex) 노드4, 노드5의 LCA → 루트노드에서 탐색을 시작해 각 노드의 부모노드와 깊이를 배열에 저장한다. (여기서 탐색은 DFS 혹은 BFS 알고리즘을 사용) index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 부모노드 0 1 1 2 2 3 3 4 4 6 6 7 7 11 11 깊이 1 2 2 3 3 3 3 4 4 4 4 4 4 5 5 Step 01) 깊이가 다를경우 만약 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부..

이진 트리 각 노드의 자식의 갯수(차수)가 2 이하로 구성된 트리 트리는 기본적으로 그래프의 표현과 일차원 배열 표현으로 나뉜다. 그래프의 표현으로는 인접리스트를 활용한 BFS, DFS탐색 알고리즘 유형이 있으며 1차원 배열 표현으로는 인덱스 트리와 LCA 유형이 있다. 이진트리는 1차원 배열로 표현하는 인덱스 트리, LCA라고 볼 수 있다. 종류 편향 이진 트리 포화 이진 트리 완전 이진 트리 노드들이 한쪽으로 편향 돼 생성됨 트리의 높이 모두 일정, 리프노드가 꽉참 마지막 레벨 제외하고 노드들이 완전하게 채워짐, 마지막 레벨은 왼쪽부터 채워짐 ⓐ ／ ⓑ ／ ⓒ ／ ⓓ ／ ⓔ ⓐ ∧ ⓑ ⓒ ∧ ∧ ⓓ ⓔⓕ ⓖ ⓐ ∧ ⓑ ⓒ ∧ ⓓ ⓔ 편향 이진 트리에 저장시 탐색속도 저하 및 많은 공간이 낭비된다. 따..