언제나 휴일

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

[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.6 깊이우선탐색(DFS) 알고리즘 경험 정보 구현 초기 경험 정보를 생성하는 함수를 작성합시다. Heuristic *MakeInitHeuristic(Graph *graph,Vertex start,Vertex goal) { Heuristic *heu = 0; 경험 정보 크기의 메모리를 할당합니다. heu = (Heuristic *)malloc(sizeof(Heuristic)); 이동 경로를 보관할 동적 배열을 생성합니다. heu->exprs = New_Array(); 그래프와 출발점, 도착점을 설정합니다. heu->graph = graph; heu->start = start; heu->goal = goal; 출발점을 이동 경로에 보관합니다. Array_PushBack(heu->e..

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

[C언어 알고리즘] 6.2.3 테스트(DFS 알고리즘에 사용할 그래프) 이제 작성한 그래프가 잘 동작하는지 테스트 코드를 작성합시다. [그림 6.4]는 앞으로 그래프를 사용하는 알고리즘에서 사용할 그래프의 논리적 모습입니다. [그림 6.4] 그래프 논리적 도식 int main() { 먼저 그래프를 동적으로 생성합니다. 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_A..

[C언어 알고리즘] 6.2.2 그래프 구현(DFS 알고리즘에 사용할 그래프) 동적으로 그래프를 생성하는 함수를 구현합시다. Graph *New_Graph() { Graph *graph = 0; 그래프 형식 크기의 메모리를 할당합니다. graph = (Graph *)malloc(sizeof(Graph)); 정점을 보관할 동적 배열과 간선을 보관할 동적 배열을 생성한 후에 그래프를 반환합니다. graph->vertexs = New_Array(); graph->edges = New_Array(); return graph; } 동적으로 생성한 그래프를 소멸하는 함수를 구현합시다. void Delete_Graph(Graph *graph) { 그래프 내부에서는 간선을 동적으로 생성하므로 그래프를 소멸하는 과정에서 ..

[C언어 알고리즘] 6.2.1 그래프 설계(DFS 알고리즘에 사용할 그래프) 그래프를 표현하는 방법은 다양합니다. 이차원 배열을 이용해서 인접 행렬로 표현하는 방법도 있고 정점과 간선의 집합으로 표현하는 방법도 있습니다. 이차원 배열을 이용해서 인접 행렬로 표현하는 방법은 정점의 개수가 n일 때 행과 열이 n인 이차원 배열을 만들고 두 개의 정점 사이의 거리를 배열의 항목 값으로 설정하는 형태로 작성합니다. 이 방법은 다른 책과 인터넷 검색 등을 통해 어렵지 않게 찾아볼 수 있을 것입니다. 하지만 그래프의 정점의 개수가 많으면 실제 정점과 정점 사이에 존재하지 않는 간선을 위한 부분이 전체의 많은 부분을 차지하여 메모리 효율과 수행 속도가 나빠질 수 있습니다. 이 책에서는 정점과 간선의 집합을 이용하여 ..

[C언어 알고리즘] 6.2 깊이우선탐색(DFS) 알고리즘 지도에서 출발지와 목적지 사이의 경로 찾는 방법은 매우 다양합니다. 여기에서는 경로 탐색 알고리즘 중에서 동적 알고리즘 방식의 깊이우선탐색(DFS, Depth First Search) 알고리즘을 소개할게요. 깊이우선탐색 알고리즘은 출발지에서 다음 지점 중에 한 점으로 이동하고 해당 지점에서 다시 다음 지점으로 이동하는 것을 반복합니다. 만약 더 이상 이동할 곳이 없으면 이전 지점으로 다시 돌아와서 가지 않은 다른 지점으로 이동합니다. 이를 목적지에 도달할 때까지 반복하는 것입니다. 이와 같은 방법으로 문제를 해결하기 위해서는 이동하다가 막혔을 때 다시 돌아와서 다음 경로로 이동해야 하는데 이를 위해 경험 정보를 자료구조에 보관해야 합니다. 여기서 ..