자연어(NLP) 자연어(NLP)

문제:  그래프에서  깊이  우선  탐색(Depth-First  Search,  DFS)과  너비  우선  탐색 (Breadth-First Search, BFS)의 개념과 예시를 들어주세요. DFS는 가능한 하나의 길을 깊이로 끝까지 탐색하고, 그 후에 필요시(막히면)이전 단계로 돌아가는 방법입니다. BFS는 시작 노드에서 가까운 노드부터 순서대로 탐색하는 방법입니다. DFS는 스택을 사용하고 BFS는 큐를 사용합니다.DFS는 경로를 빠르게 탐색에 유리하지만 찾은 경로가 시작노드와의 거리가 최단거리는 알수없으나,BFS는 찾은경로가 최단 경로임을 보장할수 있습니다.관련 개념:Depth-First Search (깊이 우선 탐색): 깊이 방향으로 경로를 탐색하는 데 적합한 그래프 탐색 알고리즘입니 다. Bre..

Q. 그래프의 최소 신장 트리 (Minimum Spanning Tree) 알고리즘 중 프림 (Prim) 알고리즘과 크루스칼 (Kruskal) 알고리즘의 차이점과 사용 사례에 대해 설명해 주세요A. 프림 알고리즘 (정점에 focus)-임의의 정점(Node)에서 시작-현재 트리에서 가장 가중치가 낮은 길을 따라 확장-모든 정점(노드)이 트리에 포함될때까지 반복 (또는 N-1간선)A. 크루스칼 알고리즘 (간선 focus)-가장 가중치 낮은 간선부터 순서대로 트리에 넣음-사이클 발생시 하나 건너띈다-모든 정점이 트리에 포함될 때까지 반복     •임의의 Undirected 그래프에서, 모든 Vertex를 최소한의 Edge를 사용해 연결하는 것•이때 Cycle이 있으면 안됨 (특정 지점에서 시작해서, 길을 따라가..

AVR 트리1. 이진탐색 트리 성질 충족 (가운데가 기준)2. 모든 노드의 balance Factor 절대값이 1 이하인 경우(1포함)3. AVR의 균형유지(balance)유지 Balance Factor임의의 node에 대해서, 다음을 balance factor로 정의(좌측 Subtree의 높이) - (우측 Subtree의 높이) 루트노드와 최하단의 leaf와의 거리 depth  1. LL 회전( Left-Left-Rotation)삽입된 노드가 왼쪽 자식의 왼쪽 SubTree에 있는 경우 2. RR 회전( Right-Right-Rotation)1기준으로 보면 오른쪽 자식의 오른쪽 subtree 3. LR회전삽입된 노드가 왼쪽자식의 오른쪽 자식으로 삽입 4. RL 회전오른쪽 자식의 왼쪽 서브트리에 들어감

이진트리: 자식 최대 두개 • 이진탐색트리: 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 크다 • 완전이진트리(complete binary tree): 마지막 층을 제외하고 모든 층이 완전히 채워져 있으며,      마지막 층의 모든 노드는 가능한 왼쪽에 있다 • 포화이진트리: 모든 층이 전부 완전히 채워진 이진트리이진탐색트리 탐색,삽입,삭제https://youtu.be/XOZQEcqW06s - YouTube www.youtube.com이진탐색트리 중위순회https://youtu.be/uz0KaYHySIg이진 탐색트리시간복잡도 정리필요재귀적 적용 - 개념 이진 탐색 트리(Binary Search Tree, BST)는 각 노드의 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값을 가지는 트리입니..

트리탐색Level-order Traversal아래그림) 동일한 깊이를 가지는 노드는 좌측부터 방문모두 순회하면 한단계내려감 (depth부터 내려가는게 아니라)  Tree와 Subtreesubtree: tree의 부분 tree 아래그림)전위순회 (Pre-order Traversal)Root Node부터 간다.Root Node => 왼쪽 Sub-Tree  아래그림)중위순회  (In-order Traversal)Root는 좌측우측 사이에         중위-  왼쪽 subtree, 루트노드, 오른쪽 subtree재귀적으로 중위순회처음: 왼쪽subtree -> 15두번짹: 15의 왼쪽 subtree - 36subtree의 subtree(똑같은원리 반복- 재귀)      아래그림93의 왼쪽 subtree 중위순회..

Graph 꼭지점 node - vertexedge - 모서리 아래그림) 아래그림)node 인접해있다.graph 탐색시 이동한 족적이 walk A-C-B-D-E열린 Walk - 처음과 끝이 다른 walk닫힌 Walk - 처음과 끝이 같은 walk Path- walk 중에 중복된게 없으면 pathcycle- 닫힌 walk와 path의 조건을 모두 만족하면 cycle 아래그림)중복되서 cycle 아님 Tree다음의 두조건을 만족하는 경우를 tree라고 함1) graphy가 연결 graphy일때2) 주어진 graphy는 cycle이 없다.tree는 자식 node와 부모 node의 관계로 이어져 있다. 보통, 독립적인것은 cycle되기힘듬 아래그림)Root Node - 부모 node가 없으면Leaf Node - ..