Developer Cafe

신장 트리 n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 만들어져 사이클이 없는 단순 연결 그래프를 신장 트리라고 한다. 깊이 우선 탐색을 이용하여 생성된 깊이 우선 신장 트리와 너비 우선 탐색을 이용하여 생성된 너비 우선 신장 트리가 있다. 최소 비용 신장 트리 무방향 가중치 그래프에서 가중치의 합이 쵯소인 신장 트리를 최소 비용 신장 트리라고 한다. 최소 비용 신장 트리를 만들기 위해 Kruskal이 만든 알고리즘과 Prime이 만든 알고리즘을 사용한다. Kruskal Kruskal 알고리즘은 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 Kruskal 알고리즘1 과 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 Kruskal 알..

트리는 비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조이다. 이진트리 모든 노드의 차수를 2 이하로 정하여 전체 트리의 차수가 2 이하가 되도록 만든 이진 트리는 왼쪽 서브 트리와 오른쪽 서브 트리를 가지는데, 서브 트리 역시 이진 트리가 된다. n개의 노드로 구성된 이진 트리는 (n-1)개의 간선을 가지며, 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개며, 노드의 최대 개수는 (2^h+1 - 1)개가 되는 성질을 가진다. 이진 트리를 순차 자료구조 방식을 이용하여 표현하는 방법은 높이가 h인 포화이진트리의 노드 번호를 배열의 인덱스로 사용하여 1창원 배열로 표현하는 것이다. 1차원 배열에서 인덱스 계산을 간단히 하기 위해서 인덱스 0번은 실제로 사용하지 않고 비..

트리 - 트리에는 가장 상위 노드를 루트라 부른다. 여기선 2가 루트다 - 90은 50, 150의 부모고 반대로 50, 150은 90의 자식이다. - 트리는 레벨이 있다. 여기선 4 레벨이다 (맨위가 1 레벨) 이진 트리(+트리 특징) - 각 노드의 작식은 0개나 1개, 2개다. - 한 노드에 자식이 둘이면 한자식은 부모보다 작은 값을, 다른 자식은 부모보다 큰 값을 가져야한다. 검색 - 111을 찾는다고 가정하고 두 자식중 부모가 111보다 큰지 작은지 비교 후 조건에 맞는 자식에게 타고 들어가면서 찾고자하는 값을 찾는다. (여기선 111이 부모 90보다 크다 고로 우측 150으로 타고옴) - 이진 트리 검색은 O(log N) 단계이다. 삽입 - 100을 삽입한다고 가정하면 먼저 루트90부터 큰지 작은..