언제나 휴일

７. 공배수와 최대공배수의 관계 공배수와 최소공배수의 관계 공배수는 최소공배수의 배수입니다. 예제) 8과 12의 공배수와 최소공배수의 관계 확인하기 8의 배수는 8, 16, 24, 32, 40, 48, 56, 64, 72, …입니다. 12의 배수는 12, 24, 36, 48, 60, 72, 84, …입니다. 8과 12의 공배수는 24, 48, 72, …입니다. 8과 12의 최소공배수는 24입니다. 따라서 8과 12의 공배수는 최소공배수인 24의 배수입니다. 문제 예시 1) 어떤 두 수의 최소공배수는 ８입니다. 다음 중 두 수의 공배수가 아닌 것을 고르시오． ① ８ ② 12 ③ 16 ④ 24 ⑤ 48 풀이) 공배수는 최소공배수의 배수입니다．따라서 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 순열 문제 바구니에 있는 여러 개의 공을 꺼내는 순서의 조합을 찾는 것은 대표적인 순열 문제입니다. 그리고 확률과 통계를 얘기할 때도 순열 문제는 자주 등장합니다. 바구니에서 공을 꺼내는 문제에서는 바구니에 남아있는 공과 꺼낸 공의 조합이 경험정보입니다. 이러한 경험 정보를 스택을 이용하여 동적 알고리즘으로 해결하면 어렵지 않게 문제를 해결할 수 있습니다. 다음은 이처럼 여러 단계로 나누어 문제를 해결하고 이전 단계에서 다음 단계로 진행할 수 있는 모든 경우의 수를 경험하는 방법으로 해결하는 동적 프로그래밍의 의사 코드입니다.초기 경험 정보를 생성스택에 보관반복(스택이 비어 있지 않다면) 스택에서 경험 정보 꺼내옮 스택에서 꺼내온 경험 정보에서 다음 경험 목록 조사 반복(다음 경험 목록을 순차..

10.1 피보나치 수열 피보나치 수열은 재귀적인 방법으로 해결하는 대표적인 알고리즘입니다. 하지만 피보나치 수열에서는 내부적으로 두 번의 재귀를 수행하여 재귀 호출 횟수는 2의 n승으로 수행 비용이 많이 들어갑니다. 만약 한 번 구한 항의 값을 기억해 두었다가 다시 호출할 때 이를 이용하면 비용은 줄어들어요. 이와 같이 경험한 정보를 이용하여 문제를 해결하는 것을 동적 프로그래밍 기법이라 말합니다. 여기에서는 피보나치 수열을 재귀적인 방법과 동적 프로그래밍 방법으로 해결하는 것을 비교해 볼게요. 다음은 피보나치 수열을 재귀적인 방법으로 구현한 코드입니다.unsigned long long Fibonacci(unsigned int n){ long long result = 1; if(n