언제나 휴일

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

[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..

[C언어 알고리즘] 7. 탐욕(Greedy) 알고리즘 탐욕(Greedy) 알고리즘은 커다란 문제를 해결하기 위해 여러 단계를 나누어 해결하는 알고리즘의 하나입니다. 동적 알고리즘에서는 현 단계에서 다음 단계로 갈 수 있는 모든 경험을 수행하면서 문제를 해결하였습니다. 하지만 탐욕 알고리즘은 현 단계에서 갈 수 있는 다음 단계들 중에 최적이라고 판단하는 하나의 단계만 수행합니다. 따라서 현 단계에서 다음 단계로 갈 수 있는 모든 경험 중에 무엇을 선택할 것인지 결정하는 것이 중요합니다. 그런데 매 순간 최적이라고 판단하는 다음 단계를 선택하면서 전체 문제를 해결하였을 때 이 해결 방법이 전체 문제에 최적일 수도 있지만 최적이 아닐 수도 있습니다. 따라서 가치있는 탐욕 알고리즘은 매 순간 최적이라고 판단하면..

[C언어 알고리즘] 1. 다루는 내용출간일 2016년 11월 30일판매가 3000원형태 ebook학습에 도움이 되시면 ebook을 구입하여 소장하시면 감사하겠습니다.언제나 휴일 출판사의 수익금의 대부분은 아프리카에 기부하고 있습니다. 이 책은 프로그래머의 기초 지식인 알고리즘을 이론적인 접근과 구현을 다루고 있습니다. 알고리즘은 문제를 해결하기 위한 논리의 집합이예요. 문제 해결 방법으로 분류하면 반복 알고리즘, 재귀 알고리즘, 분할 정복, 동적 프로그래밍, 탐욕 알고리즘 등이 있죠. 컴퓨터 프로그래밍을 업무로 하는 이들에게 알고리즘은 실질적인 구현에서 필수적으로 필요합니다. 그리고 이들을 다루는 책은 매우 다양하죠. 이론으로 접근하는 책들은 다양한 알고리즘을 다루지만 실질적인 구현없이 추상적으로 소개할..

온라인 무료 공개 [디딤돌 자료구조와 알고리즘 C++]책 소개 이 책에서는 컴퓨터 프로그래머의 기초 지식인 알고리즘과 자료구조를 이론적인 접근과 실질적인 구현을 다루고 있어요.자료구조는 프로그램에 관라할 데이터를 어떠한 구조로 보관하고 접근할 것인가를 다루는 것입니다. 선형 자료구조인 배열이나 연결리스트, 스택, 큐와 비선형 자료구조인 트리, 그래프 등이 있습니다. “선형 자료구조에는배열, 연결리스트, 스택, 큐”“비선형 자료구조에는트리, 그래프” 알고리즘은 문제를 해결하기 위한 논리의 집합이예요. 문제 해결 방법으로 분류하면 반복 알고리즘, 재귀 알고리즘, 분할 정복, 동적 프로그래밍, 탐욕 알고리즘 등이 있죠.“반복 알고리즘, 재귀 알고리즘,분할 정복 알고리즘,동적 알고리즘,탐욕 알고리즘”컴퓨터 프로..

12.4.2 크루스칼 알고리즘 소스 코드다음은 앞에서 작성한 크루스칼 알고리즘 소스 코드입니다. //Edge.h#pragma once#include using namespace std;class Edge{ string vt1; string vt2; int weight;public: Edge(string vt1,string vt2,int height); bool Exist(string vt)const; bool Exist(string vt1, string vt2)const; string Other(string vt)const; void View()const; int GetWeight()const; string GetVt1()const; string GetVt2()const;}; //Edge.cpp#incl..

12.4.1 크루스칼 알고리즘 구현간선은 프림 알고리즘에서 구현한 것과 차이가 없습니다. 그래프도 대부분 비슷합니다. 여기에서는 차이가 있는 부분만 설명할게요. 이번에는 간선을 선택할 때 간선의 비중이 같을 때 그래프에 먼저 추가한 간선을 선택하게 합시다. 이를 위해 Graph에 간선을 추가하는 부분을 수정할게요.bool Graph::AddEdge(string vt1, string vt2,int weight)//간선 추가{ if(Exist(vt1)&&Exist(vt2)) { if(Exist(vt1,vt2)) { return false; } CEIter seek = edges.begin(); CEIter last = edges.end(); for( ;seek != last; ++seek) {프림 알고리즘에..

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

12.3.2 프림 알고리즘 소스 코드앞에서 작성한 프림 알고리즘 소스 코드입니다. //Edge.h#pragma once#include using namespace std;class Edge{ string vt1; string vt2; int weight;public: Edge(string vt1,string vt2,int height); bool Exist(string vt)const; bool Exist(string vt1, string vt2)const; string Other(string vt)const; void View()const; int GetWeight()const; string GetVt1()const; string GetVt2()const;}; //Edge.cpp#include "Edg..