언제나 휴일

[온라인 무료 공개] 디딤돌 알고리즘 C언어 출간 서문 이 책은 컴퓨터 프로그래머의 기초 지식인 알고리즘을 이론적인 접근과 실질적인 구현을 다루고 있습니다. 컴퓨터 프로그래밍을 업무로 하는 이들에게 알고리즘은 실질적인 구현에서 필수적으로 필요한 것임은 누구나 알고 있습니다. 그리고 이들을 다루는 책은 매우 다양합니다. 알고리즘을 이론적으로 접근하는 책들은 다양한 알고리즘을 다루고 있지만 실제적인 구현은 추상적으로 소개합니다. 그리고 실질적인 구현을 다루는 책들은 아주 기초적인 알고리즘을 중심으로 다루고 있어 이론으로 다루는 책의 내용을 표현하는데 한계가 있습니다. 이 책에서는 C언어 문법을 익히고 프로그래밍을 학습하는 초보자들에게 보다 깊이있는 알고리즘을 이해하고 구현하는데 도움을 주기 위해 집필하였습니..

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

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

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

[C언어 알고리즘] 6.2.8 깊이우선탐색(DFS) 알고리즘 소스 코드//common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Array.h #pragma once typedef void * Element; typedef struct _Array Array; struct _Array { Element *base; int capacity; int usage; }; typedef Element *Iterator; Array *New_Array(); void Delete_Ar..

[C언어 알고리즘] 6.2.7 깊이우선탐색(DFS) 테스트 코드 작성 먼저 알고리즘에 사용할 그래프를 생성하여 구성하는 함수를 작성합시다. Graph * InitSimulation() { Graph *graph = New_Graph(); Graph_AddVertex(graph,"A"); Graph_AddVertex(graph,"B"); Graph_AddVertex(graph,"C"); Graph_AddVertex(graph,"D"); Graph_AddVertex(graph,"E"); Graph_AddVertex(graph,"F"); Graph_AddVertex(graph,"G"); Graph_AddVertex(graph,"H"); Graph_AddEdge(graph,"A","B",5); Graph_Add..

[C언어 알고리즘] 6.2.5 깊이우선탐색(DFS) 알고리즘의 경험(Heuristic) 정보 설계 동적 알고리즘에서는 경험 정보를 설계하는 것이 매우 중요합니다. DFS 알고리즘에서의 경험 정보는 그래프에서 출발점과 도착점 사이에 이동 경로를 기억하고 있어야 합니다. 여기에서는 이동 경로를 배열을 이용하여 보관하기로 할게요. 그리고 총 이동 거리도 멤버로 구성합시다. typedef struct _Heuristic Heuristic; struct _Heuristic { Array *exprs; Graph *graph; Vertex start; Vertex goal; int total_weight; }; 초기 경험 정보를 생성하는 함수를 제공합시다. 초기 경험 정보를 생성하려면 그래프와 출발지, 도착점을 알..

[C언어 알고리즘] 6.2.4 그래프 테스트 소스 코드//common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Array.h #pragma once typedef void * Element; typedef struct _Array Array; struct _Array { Element *base; int capacity; int usage; }; typedef Element *Iterator; Array *New_Array(); void Delete_Array(Array..