언제나 휴일

[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.1.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.1.3 순열 알고리즘 테스트 코드 작성 먼저 시뮬레이션에 사용할 초기 바구니에 넣을 공의 집합을 생성하는 함수를 작성할게요. Array * InitSimulation() { int ball = 0; Array *bucket = 0; 먼저 동적 배열을 생성합니다. bucket = New_Array(); 0번 공부터 9번 공까지 순차적으로 이동하면서 배열에 순차 보관합니다. for(ball = 0; ball> 뒤에 명시한 파일로 출력합니다. 결과 파일을 더블 클릭하여 원하는 모든 결과를 출력하는지 확인해 보세요.

[C언어 알고리즘] 6.1.2 순열 알고리즘의 경험 정보 구현 초기 경험 정보를 생성하는 함수를 작성합시다. Heuristic *MakeInitHeuristic(Array *bucket) { Heuristic *heu = 0; 입력 인자로 전달받은 바구니에 있는 공을 순차적으로 접근하기 위해 반복자 변수를 두 개 선언할게요. Iterator seek=0, end=0; Heuristic 크기의 메모리를 할당합니다. heu = (Heuristic *)malloc(sizeof(Heuristic)); 꺼내지 않은 공을 보관할 동적 배열과 꺼낸 공을 보관할 동적 배열을 생성합니다. heu->ori_bucket = New_Array(); heu->out_bucket = New_Array(); 입력 인자로 전달받은 ..

[C언어 알고리즘] 6.1.1 순열 알고리즘의 경험(Heuristic)정보 설계 바구니에서 공을 꺼내는 순열 문제의 경험 정보는 꺼내지 않은 공의 집합과 꺼낸 공의 집합이라 할 수 있습니다. 여기에서는 동적 배열을 이용하여 꺼낸 공과 꺼내지 않은 공의 집합을 표현할게요. 동적 배열과 연결리스트, 스택에 관한 코드 설명은 이 책에서는 하지 않습니다. 디딤돌 자료구조 (C언어)를 참고하세요. 이에 관한 소스 코드는 6.1.4 순열 알고리즘 소스 코드에 있습니다. typedef struct _Heuristic Heuristic; struct _Heuristic { Array *ori_bucket; Array *out_bucket; }; 초기 경험 정보를 생성하는 함수를 제공합시다. 이 함수에는 초기 바구니에 ..

[C언어 알고리즘] 6.동적 프로그래밍 커다란 문제를 해결하는 과정을 여러 단계로 나누어 해결하는 알고리즘들이 있어요. 그 중에 동적 프로그래밍은 현재 단계에서 다음 단계로 진행하면서 알 수 있는 정보를 학습해요. 그리고 이 학습 정보를 이용하여 다음 단계로 진행하여 전체 문제를 해결하는 알고리즘이예요. 이전 단계에서 다음 단계로 진행할 수 있는 경우의 수가 고정일 때는 간단하게 문제를 해결할 수 있어요. 하지만 이전 단계에서 다음 단계로 진행할 수 있는 경우의 수가 많을 때는 스택을 이용해서 문제를 해결하여 비교적 간단하게 만들 수 있어요. 하지만 수행 성능은 떨어질 수 있어요. 먼저 이전 단계에서 다음 단계로 진행할 수 있는 경우의 수가 고정인 문제로 대표적인 것이 피보나치 수열을 구 문제예요. 여기..

[C언어 알고리즘] 5.4 인접 행렬로 표현한 그래프 소스 코드//Program.c #include #include #include typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 } Graph; Graph *NewGraph(int max_vertex);//그래프 동적 생성 void DeleteGraph(Graph *graph);//그래프 소멸 void AddEdge(Graph *graph, int start, int goal);//간선 추가 void ViewGraph(Graph *graph);//그래프 정보 출력 void ViewIndegree(Graph *g);//진입차수 확인 void ViewOutdegree(Graph *g)..

[C언어 알고리즘] 5.3 진입 차수, 진출 차수이번에는 그래프에서 중요하게 생각하는 특징 중에 진입 차수와 진출 차수를 알아보아요. 특정 점정으로 갈 수 있는 간선의 수를 해당 정점의 진입차수(In degree)라고 불러요. 그리고 특정 정점에서 갈 수 있는 간선의 수를 진출차수(Out degree)라고 부르죠. 이번에는 그래프의 이와 같은 정보를 확인하는 기능을 구현해 보아요. 그래프 구현은 앞에서 소개한 것을 참고하세요. 이번에 추가할 기능은 진입 차수와 진출 차수를 확인하는 기능이예요. void ViewIndegree(Graph *g);//진입차수 확인 void ViewOutdegree(Graph *g);//진출차수 확인 먼저 진입 차수를 구하는 기능을 작성하기로 해요. 진입 차수는 상대 정점에서..

[C언어 알고리즘] 5.2.1 인접 행렬로 방향성 있는 그래프 소스 코드//Program.c #include #include #include typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 } Graph; Graph *NewGraph(int max_vertex);//그래프 동적 생성 void DeleteGraph(Graph *graph);//그래프 소멸 void AddEdge(Graph *graph, int start, int goal);//간선 추가 void ViewGraph(Graph *graph);//그래프 정보 출력 int main(void) { Graph *graph; graph = NewGraph(6);//그래프 동적 생..