C&C++8 [C/자료구조] MST, 크루스칼(Kruskal), 프림(Prim) 알고리즘 1) MST(Minimum Spanning Tree) 신장 트리(Spanning Tree) 무방향 그래프 G(V,E)에서 E에 속한 간선들로 사이클을 포함하지 않으면서 모든 정점 V를 연결한 부분 그래프를 신장 트리(Spanning Tree)라 한다. 그래프에서 신장 트리는 여러 형태로 존재할 수 있으며, 신장 트리의 특징은 n개의 정점을 갖는 그래프에서 신장 트리에 속하는 간선의 수는 n-1개이며 사이클을 이루지 않는다는 특징이 있다. MST란 최소 비용 신장 트리(이하 최소 신장 트리)를 뜻하며, 무방향 그래프의 간선들에 가중치가 주어진 경우, 여러 신장 트리 중에 간선들의 가중치 합이 최소인 신장 트리를 말한다. 효율적인 통신 망 설계 등에 이용될 수 있다. 2) 크루스칼(Kruskal) 크루스칼이.. 2022. 12. 21. [C/자료구조] 최대, 최소 힙(heap) 정렬 구현 힙(heap) 자료구조 - 부모가 되는 노드의 값이 자식 노드보다 크거나 작은 자료구조 - 완전이진트리의 구조를 가짐 - 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 - 방식에 따라 최대 힙(max heap)과 최소 힙(min heap)으로 나뉨 힙(heap)의 구현 - 힙을 저장하는 표준적인 자료구조는 배열 이다. - 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다. - 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. · 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다. - 힙에서의 부모 노드와 자식 노드의 관계 · 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 · 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 +.. 2022. 11. 30. [C/자료구조] 연결 리스트 다항식 덧셈 연결 리스트를 이용하여 희소 다항식을 표현 동적 메모리를 이용한 단순 연결 리스트로 표현하였음 한 개의 노드는 data / link 2가지의 값을 가짐 (data는 현재 노드의 값, link는 다음 노드의 주소) 노드의 data는 '계수(coef)'와 '차수(expn)'값을 가짐 이때, 연결 리스트는 '차수' 내림차순 정렬된 형태를 가짐 두 다항식을 더하는 add_poly 함수 구현 두 리스트 list1, list2 를 인자로 받음 두 다항식을 더한 결과 리스트 ListType* new_poly 생성 및 초기화 두 리스트의 감시할 노드를 가르키는 ListNode* h1, *h2 생성, 각 리스트의 head로 초기화 h1 또는 h2 가 하나라도 NULL 값이 아니면 반복 h1이 NULL인 경우, h2 노드.. 2022. 11. 20. [C/자료구조] 하노이탑 문제 하노이탑이란? 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 하노이탑의 조건 한 번에 한개의 원판만 옮길 수 있다. 맨 위에 있는 원판만 이동할 수 있다. 크기가 작은 원판위에 큰 원판이 쌓일 수 없다. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다. 이제 문제 자체는 이해했으니, 이를 체계적으로 정의해보자. "체계적"이라함은, 문제의 입력과 출력을 보다 함수에 가깝게 정의하자는 것이다. 우리는 "원반의 이동횟수를 최소화하고자 할 때, 각 원반을 옮기는 모든 순서를 출력하는 것"으로 한다. 이때 각 이동의 출력은 '3번 원반을 A에서 C와 같이로 정하며.. 2022. 10. 22. 이전 1 2 다음