언제나 휴일

[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) 알고리즘을 소개할게요. 깊이우선탐색 알고리즘은 출발지에서 다음 지점 중에 한 점으로 이동하고 해당 지점에서 다시 다음 지점으로 이동하는 것을 반복합니다. 만약 더 이상 이동할 곳이 없으면 이전 지점으로 다시 돌아와서 가지 않은 다른 지점으로 이동합니다. 이를 목적지에 도달할 때까지 반복하는 것입니다. 이와 같은 방법으로 문제를 해결하기 위해서는 이동하다가 막혔을 때 다시 돌아와서 다음 경로로 이동해야 하는데 이를 위해 경험 정보를 자료구조에 보관해야 합니다. 여기서 ..

[에디트 피아프(Edith Piaf)] 빠담 빠담안녕하세요. 언제나 휴일, 언휴예요. 프랑스인이 가장 사랑하는 샹송 가수라면 누구나 에디트 피아프를 생각할 거예요. 에디트 피아프의 사랑받은 곡들을 한 번 살펴보기로 해요. 이번에는 그녀의 곡 중에서도 올레 CM 송으로 "빠름~ 빠름~"으로 알려진 빠담 빠담을 알아보기로 해요. 나는 전설이다: 샹송 (The Legend Of Chanson)음반아티스트 : Various Artist출시 : 2011.09.27상세보기 노르베르 글랑즈 베르가 작곡한 곡으로 에디트 피아프가 우연히 멜로디를 듣고 빠담 빠담 흥얼 거리죠. 그리고 이를 앙리 콩테가 가사를 입혀 탄생한 곳이예요. 에디트 피아프가 사랑(노래와 남자 모두)하는 것은 아주 오래전부터 자신을 따라다니는 것이라..

[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.1 순열 알고리즘 바구니에 있는 여러 개의 공을 꺼내는 순서의 조합을 찾는 것은 대표적인 순열 문제입니다. 그리고 확률과 통계를 얘기할 때도 순열 문제는 자주 등장합니다. 바구니에서 공을 꺼내는 문제에서는 바구니에 남아있는 공과 꺼낸 공의 조합이 경험정보입니다. 이러한 경험 정보를 스택을 이용하여 동적 알고리즘으로 해결하면 어렵지 않게 문제를 해결할 수 있습니다. 하지만 모든 경험을 수행해야 하기 때문에 단계가 많고 현재 단계에서 다음 단계로 진행할 수 있는 가지 수가 많을 때 수행 속도가 무리하게 커질 수 있는 문제점도 갖고 있습니다. 여기에서 구현할 예는 바구니에 서로 다른 숫자가 써 있는 공이 있을 때 n개의 공을 하나씩 꺼내는 예로 할게요. 이 때 꺼낸 순서를 포함하여 나올..

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