언제나 휴일

11.1 너비 우선 탐색(인접 행렬) 구현 제일 먼저 인접 행렬로 너비 우선 탐색을 구현해 보아요. 그래프와 Heuristic에 관한 코드는 10.3.3 깊이 우선 탐색(인접 행렬) 코드와 같으니 참고하세요. 먼저 깊이 우선 탐색하는 순서를 이해하기 쉽게 구현한 코드를 구현합시다. int main(){먼저 그래프를 생성하고 간선을 추가하세요. Graph *graph = new Graph(9);//그래프 동적 생성 graph->AddEdge(0, 1);//간선 추가 graph->AddEdge(0, 2);//간선 추가 graph->AddEdge(1, 2);//간선 추가 graph->AddEdge(1, 3);//간선 추가 graph->AddEdge(2, 4);//간선 추가 graph->AddEdge(3, 6)..

11. 너비 우선 탐색(Breath First Search) 이번에는 그래프에서 최단 경로를 찾는 너비 우선 탬색(Breath First Search) 알고리즘을 알아보아요. 앞에서 다룬 깊이 우선 탐색(Depth First Search)알고리즘은 그래프 상에서 두 정점 사이에 경로를 찾는 알고리즘이었습니다. 한 정점에서 갈 수 있는 다음 정점으로 이동하고 다시 다음 정점으로 이동하면서 경로를 찾는 것을 반복하였습니다. 만약 더 이상 이동할 곳이 없다면 이전에 이동했었던 곳에서 다시 찾는 형태로 경로를 찾는 알고리즘입니다. 위 그래프에서 0에서 8로 가는 정점을 예로 들어 볼게요. 여기에서는 한 정점에서 다음 정점으로 갈 때 높은 수를 갖는 정점을 우선 방문하는 예로 설명할게요. 깊이 우선 탐색 알고리즘..

10.4 깊이 우선 탐색(정점과 간선 그래프) 이번에는 그래프를 정점(Vertex)과 간선(Edge) 집합으로 표현한 후에 깊이 우선 탐색을 구현해 보아요. 먼저 간선을 정의합시다. 여기에서는 방향성 없는 그래프로 표현할게요.class Edge{간선의 두 정점을 멤버 필드로 추가하세요. int vt1; int vt2;public:생성할 때 두 개의 정점을 입력 인자로 받습니다. Edge(int vt1,int vt2);특정 점정을 포함하는지 판별하는 메서드를 제공하세요. bool Exist(int vt)const;두 개의 정점을 포함하는지 판별하는 메서드도 제공하세요. bool Exist(int vt1, int vt2)const;하나의 정점을 입력 인자로 받은 후에 나머지 정점을 반환하는 메서드도 제공하세..

10.3.3 깊이 우선 탐색(인접 행렬) 코드 다음은 앞에서 작성한 인접 행렬로 구현한 그래프와 이를 이용한 깊이 우선 탐색 소스 코드입니다. 여기에서는 방향성 없는 그래프를 소개할게요. //Graph.h#pragma once#include #include using namespace std;typedef vector Neighbors;class Graph{ const int vn;//정점의 개수 int **matrix;//인접 행렬 public: Graph(int vn); ~Graph(void); void AddEdge(int start, int goal);//간선 추가 void ViewNeighbors()const; void ViewNeighbor(int vt)const; Neighbors FindN..

10.3.2 깊이 우선 탐색(인접 행렬) 구현 이번에는 인접행렬로 구현한 그래프를 이용하여 깊이 우선 탐색 알고리즘을 구현해 봅시다. 깊이 우선 탐색은 한 정점에서 갈 수 있는 이웃 정점으로 이동한 후에 다시 이웃 정점으로 이동하는 것을 반복합니다. 단 이미 방문한 정점은 방문하지 않으면서 목적지까지 경로를 찾는 알고리즘입니다. 그런데 깊이 우선 탐색에서 이동하다가 더 이상 갈 곳이 없으면 이전 갈림길에서 다른 길을 선택할 수 있어야 합니다. 이를 위해 현재까지 이동한 경로를 경험 정보로 관리하고 한 정점에서 갈 수 있는 이웃 정점을 추가한 다음 경험 정보를 스택에 보관해 두었다가 더 이상 갈 곳이 없으면 스택에서 꺼내와서 다른 경로를 찾게 구현할 거예요. 다음은 스택을 이용한 깊이 우선 탐색 알고리즘의..

10.3.1 그래프 구현 그래프는 방향성 없는 그래프와 방향성 있는 그래프가 있습니다. 먼저 방향성 없는 그래프를 살펴보아요. 방향성 없는 그래프는 정점 A에서 정점 B로 이동할 수 있으면 언제나 정정 B에서 정정 B로 이동할 수 있음을 보장하는 그래프예요. 방향성 없는 그래프를 표현하는 방법 중에 간단한 그래프에는 인접 행렬을 많이 사용해요. 인접 행렬로 방향성 없는 그래프를 표현하면 좌상단에서 우하단으로 이어지는 대각선에 대칭 형태죠. 먼저 그래프 형식을 정의하기로 해요. 인접 행렬로 그래프를 표현할 때 그래프에는 정점 개수와 인접 행렬이 필요하겠죠. 이제 방향성 없는 그래프를 구현해 봅시다. 정점을 보관하는 벡터를 이웃이라고 정합시다.typedef vector Neighbors;class Graph..

10.3 인접 행렬을 이용한 깊이 우선 탐색 깊이 우선 탐색(Depth First Search)은 그래프의 한 정점에서 다른 정점으로 갈 수 있는 경로를 찾는 방법 중에 하나입니다. 하나의 정점에서 갈 수 있는 이웃 정점을 방문하고 다시 방문한 정점에서 이웃 정점을 방문하면서 원하는 목적 지점까지 방문하는 방법이예요. 이 때 방문했었던 정점을 다시 방문하지 말아야 합니다. 깊이 우선 탐색처럼 그래프에서 어떠한 문제를 해결하기 위해서는 그래프를 먼저 표현할 수 있어야 합니다. 정점의 개수가 비교적 적을 때는 인접행렬로 표현할 수 있습니다. 만약 정점의 개수가 많다면 인접 행렬은 이웃하지 않는 간선을 위한 영역도 포함하여 메모리 및 성능이 나빠집니다. 이럴 때는 정점과 간선의 집합으로 그래프를 표현하여 문제..

10.2.2 순열 문제 소스 코드 다음은 앞에서 작성한 순열 문제의 소스 코드입니다. //Heuristic.h#pragma once#include #include using namespace std;typedef vector Bucket;typedef Bucket::iterator BIter;typedef Bucket::const_iterator CBIter; class Heuristic;typedef vector Heues;typedef Heues::iterator HIter;typedef Heues::const_iterator CHIter; class Heuristic{ Bucket original; Bucket out;public: Heuristic(Bucket bucket); Heues EnumN..

10.2.1 순열 문제 구현 순열 문제를 구현합시다. 0~9까지 공을 보관한 초기 경험 정보를 생성스택에 보관반복(스택이 비어 있지 않다면) 스택에서 경험 정보 꺼내옮 스택에서 꺼내온 경험 정보에서 다음 경험(공을 하나 더 꺼내는) 목록 조사 반복(다음 경험 목록을 순차적으로 반복) 바구니에 공이 비면 결과 출력 그렇지 않다면 스택에 보관 먼저 공을 보관한 바구니를 공의 번호를 보관하는 벡터로 표현할게요.typedef vector Bucket;typedef Bucket::iterator BIter;typedef Bucket::const_iterator CBIter;그리고 경험 정보를 벡터에 보관한 형식을 Heues로 정의할게요.class Heuristic;typedef vector Heues;typede..

10. 2 순열 문제 바구니에 있는 여러 개의 공을 꺼내는 순서의 조합을 찾는 것은 대표적인 순열 문제입니다. 그리고 확률과 통계를 얘기할 때도 순열 문제는 자주 등장합니다. 바구니에서 공을 꺼내는 문제에서는 바구니에 남아있는 공과 꺼낸 공의 조합이 경험정보입니다. 이러한 경험 정보를 스택을 이용하여 동적 알고리즘으로 해결하면 어렵지 않게 문제를 해결할 수 있습니다. 다음은 이처럼 여러 단계로 나누어 문제를 해결하고 이전 단계에서 다음 단계로 진행할 수 있는 모든 경우의 수를 경험하는 방법으로 해결하는 동적 프로그래밍의 의사 코드입니다.초기 경험 정보를 생성스택에 보관반복(스택이 비어 있지 않다면) 스택에서 경험 정보 꺼내옮 스택에서 꺼내온 경험 정보에서 다음 경험 목록 조사 반복(다음 경험 목록을 순차..