언제나 휴일

[C언어 알고리즘] 7.4.2 크루스칼 알고리즘 소스 코드다음은 C언어로 작성한 크루스칼 알고리즘 소스 코드입니다. 동적 배열과 정점과 간선을 이용한 그래프를 구현하여 사용하였습니다. //Array.h#pragma oncetypedef void * Element;typedef struct _Array Array;struct _Array{ Element *base; int capacity; int usage;};typedef Element *Iterator; Array *New_Array();void Delete_Array(Array *arr);void Array_SetSize(Array *arr,int capacity,Element data);void Array_PushBack(Array *arr,Ele..

[C언어 알고리즘] 7.4.1 크루스칼 알고리즘 구현이제 크루스칼 알고리즘을 구현하기로 해요. 이 책에서는 크루스칼 알고리즘을 구현할 때 그래프를 인접행렬로 표현하지 않고 정점과 간선의 집합체로 정의할게요. 인접행렬로 표현한 소스 코드는 인터넷이나 다른 레퍼런스에 많이 나와있으니 이를 참고하세요. 그래프는 프림 알고리즘을 구현하면서 만든 것을 사용하세요. void SelectVertex(Graph *mstree,Graph *origin); Array *MakeSortedEdges(Array *edges); void SelectEdge(Array *graphs,Array *sorted_edges); Graph *Kruskal(Graph *origin) { Array *sorted_edges=0; Array..

7.4 크루스칼(Kruskal) 알고리즘(최소신장트리 알고리즘) 이번에는 크루스칼 알고리즘으로 최소신장트리를 만드는 방법을 알아봅시다. 프림 알고리즘은 최적의 정점을 선택하여 최소신장트리를 만드는 방법입니다. 반면 크루스칼 알고리즘은 최적의 간선을 선택하여 최소신장트리를 만드는 방법입니다. 크루스칼 알고리즘(graph:원본 그래프) 원본 그래프의 간선 집합을 복제 복제한 간선 집합을 비중 순으로 정렬 반복(선택한 간선 개수가 graph의 정점 개수-1 보다 작다면) 최적의 간선을 선택 최적의 간선은 비중이 작은 간선 중에 선택합니다. 그런데 선택한 간선을 현재까지 만들고 있는 그래프(최소신장트리)에 추가하였을 때 사이클이 발생하지 말아야 합니다. 이를 효과적으로 구현하기 위해 원본 그래프의 간선 집합을 ..

[C언어 알고리즘] 7.3.3 프림 알고리즘 소스 코드다음은 C언어로 작성한 프림(Prim) 알고리즘 소스 코드입니다. 동적 배열과 정점과 간선을 이용한 그래프를 구현하여 사용하고 있습니다. //Array.h#pragma oncetypedef void * Element;typedef struct _Array Array;struct _Array{ Element *base; int capacity; int usage;};typedef Element *Iterator; Array *New_Array();void Delete_Array(Array *arr);void Array_SetSize(Array *arr,int capacity,Element data);void Array_PushBack(Array *arr..

[C언어 알고리즘] 7.3.2 프림 알고리즘 구현이제 프림 알고리즘을 구현해 보아요. 프림 알고리즘에서는 최소 비용의 정점을 선택하는 내부 알고리즘이 필요해요. 프림 알고리즘에서 정점을 선택해 나갈 때 현재까지 선택한 정점에서 갈 수 있는 정점 목록에서 최소 비용의 정점을 선택해야겠죠. 이를 위해 다음과 같은 논리가 필요해요. 정점선택알고리즘(mstree:최소신장트리,graph:원본 그래프) selectedge:= NULL으로 초기화 seek:= graph의 시작 정점 위치 end:= graph의 마지막 정점 위치 반복(seek가 end가 아닐 때) edge:=seek에 있는 간선 조건(edge가 mstree에 선택한 정점을 하나만 포함하고 있을 때) 조건(selectedge가 있다면) 조건(select..

[C언어 알고리즘] 7.3.1 프림 알고리즘에 맞게 그래프 소스 코드 수정이 책에서는 프림 알고리즘을 구현할 때 그래프를 인접행렬로 표현하지 않고 정점과 간선의 집합체로 정의할게요. 인접행렬로 표현한 소스 코드는 인터넷이나 다른 레퍼런스에 많이 나와있으니 이를 참고하세요. 프림 알고리즘을 구현하기 전에 그래프 알고리즘에 몇 가지 함수를 추가하기로 해요. 먼저 정점의 개수를 구하는 함수를 제공하기로 해요. int Graph_GetVtCnt(Graph *graph); 그리고 그래프의 맨 앞에 있는 정점을 구하는 함수도 제공해요. Vertex Graph_GetFront(Graph *graph); 마지막으로 간선에 특정 정점을 끝점으로 하는지 판별하는 함수를 제공하기로 해요. int Edge_Include(Ed..

[C언어 알고리즘] 7.3 프림(Prim) 알고리즘(최소신장트리 알고리즘) 신장트리는 비중있는 그래프 상에서 정점과 정점 사이에 경로를 단일화한 트리를 말합니다. 그리고 최소신장트리는 정점과 정점 사이의 경로의 합이 최소인 신장트리를 말합니다. 그래프에서 최소신장트리를 만드는 여러가지 방법 중에 가장 많이 알려진 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 프림 알고리즘은 정점을 추가하면서 트리를 확장하는 방법이고 크루스칼 알고리즘은 간선을 추가하면서 최소신장트리를 만드는 방법입니다. 먼저 프림 알고리즘을 살펴봅시다. 프림 알고리즘(graph:원본 그래프) 하나의 정점을 선택한다. 반복(선택한 정점 개수가 graph의 정점 개수보다 작다면) 선택한 정점에서 갈 수 있는 모든 정점 중에 최소 ..

[C언어 알고리즘] 7.2 SJF(Shortest Job First) 알고리즘여러 개의 작업을 하나의 CPU에서 수행하는 순서를 결정하는 스케쥴링 알고리즘은 여러가지 방법이 있습니다. 그 중에서 작업을 수행 요청하고 실제 수행이 끝날 때까지 대기하는 평균 시간을 최소로 하는 알고리즘은 SJF(Shortest Job First)알고리즘입니다. SJF 알고리즘은 작업량이 작은 작업을 먼저 수행하는 알고리즘입니다. 동시에 n개의 작업을 수행 요청이 왔다가 가정합시다. n번째 수행할 작업의 길이를 An이라고 한다면 모든 작업을 수행하는데 걸리는 비용은 다음과 같습니다. A1 + (A1 + A2) + (A1 + A2 + A3) + ... + (A1+A2+A3+...+An) = nA1 + (n-1)A2 + (n-2..

[C언어 알고리즘] 7.1.1 거스름 돈 알고리즘 소스 코드 //거스름 돈 (탐욕 알고리즘) //Program.c #include typedef enum _MType MType; enum _MType { One=1, Five=5, Ten=10, Fifty=50,Hun=100, FHun=500,Thous=1000,FTh=5000, TenTh=10000, FTenTh=50000 }; void Calculate(MType money,int value) { int remain = money - value; int ftenth=0,tenth=0, fth=0, thous=0; int fhun=0,hun=0, fifty=0, ten=0, five=0, one=0; printf("가격:%d, 받은 돈:%d\n",mon..

[C언어 알고리즘] 7.1 거스름 돈 알고리즘 물건을 팔고 가장 적은 개수로 거스름 돈을 주려면 어떻게 해야 할까요? 큰 단위의 돈을 주는 것이 작은 단위로 주는 것보다 유리하겠죠. 탐욕 알고리즘으로 문제를 해결한다면 큰 단위부터 거스름돈을 주게 전개합니다. 큰 단위 화폐부터 작은 단위 화폐 순으로 다음의 알고르즘을 전개합니다. 만약 단위보다 거슬러 줘야 할 돈이 많으면 몇 개를 줄 것인지를 결정합니다. 그리고 남은 돈은 다음 단위 화폐로 넘어가서 계산합니다. 이러한 방법을 계속 수행하면 가장 적은 개수로 거스름 돈을 지불할 수 있습니다. #include 먼저 화폐 단위를 열거형으로 정의합시다. typedef enum _MType MType; enum _MType { One=1, Five=5, Ten=1..