언제나 휴일

12.3.1 프림 알고리즘 구현이제 프림 알고리즘을 구체적으로 구현해 보아요. 앞에서 작성했던 그래프 부분까지는 매우 비슷합니다. 먼저 간선을 정의합시다.class Edge{두 개의 정점과 간선의 비용이 필요하죠. string vt1; string vt2; int weight;public:생성자는 두 개의 정점과 간선의 비용을 입력 인자로 받습니다. Edge(string vt1,string vt2,int height);특정 정점이 존재하는지 판별하는 메서드를 제공하세요. bool Exist(string vt)const;두 개의 정점을 잇는 간선인지 판별하는 메서드를 제공하세요. bool Exist(string vt1, string vt2)const;하나의 정점을 입력 인자로 받아 다른 나머지 정점을 구하..

12.3 프림 알고리즘신장트리는 비중있는 그래프 상에서 정점과 정점 사이에 경로를 단일화한 트리를 말합니다. 그리고 최소신장트리는 정점과 정점 사이의 경로의 합이 최소인 신장트리를 말합니다. 그래프에서 최소신장트리를 만드는 여러가지 방법 중에 가장 많이 알려진 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있어요. 프림 알고리즘은 정점을 추가하면서 트리를 확장하는 방법이고 크루스칼 알고리즘은 간선을 추가하면서 최소신장트리를 만드는 방법이예요. 먼저 프림 알고리즘을 살펴볼게요.프림 알고리즘(graph:원본 그래프)하나의 정점을 선택한다.반복(선택한 정점 개수가 graph의 정점 개수보다 작다면) 선택한 정점에서 갈 수 있는 모든 정점 중에 최소 비중의 간선으로 이어지는 정점을 선택*정점을 선택할 때 이미 ..

12.2 SJF 알고리즘 여러 개의 작업을 하나의 CPU에서 수행하는 순서를 결정하는 스케쥴링 알고리즘은 여러가지 방법이 있습니다. 그 중에서 작업을 수행 요청하고 실제 수행이 끝날 때까지 대기하는 평균 시간을 최소로 하는 알고리즘은 SJF(Shortest Job First)알고리즘입니다. SJF 알고리즘은 작업량이 작은 작업을 먼저 수행하는 알고리즘입니다. 동시에 n개의 작업을 수행 요청이 왔다가 가정합시다. n번째 수행할 작업의 길이를 An이라고 한다면 모든 작업을 수행하는데 걸리는 비용은 다음과 같습니다.A1 + (A1 + A2) + (A1 + A2 + A3) + ... + (A1+A2+A3+...+An) = nA1 + (n-1)A2 + (n-2)A3 + ... +An 그리고 대기 시간의 합은 다음..

12.1 거스름 돈 물건을 팔고 가장 적은 개수로 거스름 돈을 주려면 어떻게 해야 할까요? 큰 단위의 돈을 주는 것이 작은 단위로 주는 것보다 유리하겠죠. 탐욕 알고리즘으로 문제를 해결한다면 큰 단위부터 거스름돈을 주게 전개합니다. 큰 단위 화폐부터 작은 단위 화폐 순으로 다음의 알고르즘을 전개합니다. 만약 화폐 단위보다 거슬러 줘야 할 돈이 많으면 몇 개를 줄 것인지를 결정합니다. 그리고 남은 돈은 다음 단위 화폐로 넘어가서 계산합니다. 이러한 방법을 계속 수행하면 가장 적은 개수로 거스름 돈을 지불할 수 있습니다. 예를 들어 만원을 받고 1723원의 상품을 구입한다고 가정합시다. 거슬러 주어야 할 돈은 8277원입니다. 5000원8277원이므로 5000원 화폐가 1개 필요합니다. 나머지는 3277원입..

12. 탐욕 알고리즘 탐욕(Greedy) 알고리즘은 커다란 문제를 해결하기 위해 여러 단계를 나누어 해결하는 알고리즘의 하나입니다. 동적 알고리즘도 탐욕 알고리즘처럼 커다란 문제를 해결하기 위해 여러 단계로 나누어 해결할 수 있습니다. 그런데 동적 알고리즘은 현 단계에서 다음 단계로 수행할 수 있는 모든 경험을 맹목적으로 수행하는 알고리즘입니다. 이러한 이유로 단계의 깊이가 깊어지고 한 단계에서 다음 단계로 넘어갈 수 있는 경우에 동적 알고리즘은 매우 나쁜 성능을 보입니다. 하지만 탐욕 알고리즘은 현 단계에서 갈 수 있는 다음 단계들 중에 최적이라고 판단하는 하나의 단계만 수행합니다. 따라서 탐욕 알고리즘에서는 현 단계에서 다음 단계로 갈 수 있는 모든 경험 중에 선택하는 기준을 결정하는 것이 중요합니다..