미새문지

트리(Tree) 노드(Node)들이 연결된 계층적인 자료구조 특징 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖는다. 자식 노드도 0개 이상의 자식 노드를 가지는 반복적인 트리를 구성한다. 용어 루트(Root) 트리의 최상위에 있는 노드 부모(Parent) 노드 바로 위에 연결된 노드 자식(Child) 노드 바로 아래에 연결된 노드 리프 노드(leaf Node) 자식이 없는 마지막 노드 내부 노드(Internal Node) 리프 노드를 제외한 모든 노드 레벨(Level) 루트 노드부터의 거리 트리 순회 방법 전위 순회(preOrder) 루트를 먼저 방문하고 왼쪽 자식노드부터 오른쪽 자식 노드까지 순서대로 방문 중위 순회(inOrder) 왼쪽 자식 노드를 먼저 방문하고, 루트..

위상정렬 수서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘 답이 한 가지가 아니라 여러 가지가 존재할 수 있고 DAG(Directed Acyclic Graph)에만 적용이 가능하다. DAG는 사이클이 발생하지 않는 방향 그래프이며, 사이클이 발생하면 위상정렬을 수행할 수 없다. 위상정렬은 두 가지 해결책을 낼 수 있는데 현재 그래프가 위상정렬이 가능한지, 위상정렬이 가능하면 그 결과는 무엇인지이고 스택과 큐를 이용해 알고리즘을 짤 수 있다. 진행 과정(큐를 사용) 1. 진입차수가 0인 정점을 큐에 삽입 2. 큐에서 원소를 꺼내 연결된 모든 간선 제거 3. 간선 제거 이후 진입차수가 0이 된 정점을 큐에 삽입 4. 큐가 빌 때 까지 2번, 3번 과정 반복. 모..