[알고리즘] 5. Greedy Method 내용 정리

1. Brute force

2. Divide and conquer
3. Decrease and conquer
4. Transform and conquer
5. Greedy Method
6. Dynamic Programming
7. Backtracking
8. Branch and Bound

여기서는 Greedy Method 에 대해 다룬다.

 

 

 

---

Greedy method란

그리디 알고리즘이란 미래에 대한 생각 없이 그 순간에 가장 최선인 선택을 하는 알고리즘이다. 그 당시에는 최적이지만 최종적으로 최적인지는 보장이 되지 않아 최적의 해를 주는지 검증해야 한다. 

---

Greedy Method 예시

1. 거스름돈 문제
2. Huffman codes
3. Dijkstra's Algorithm: 최단거리
4. Mimum spanning Tree 
   
   • Prim’s Algorithm: 최소신장트리
   • Kruskal’sAlgorithm: 최소신장트리
5. Scheduling Problem
   • 스케줄링문제(to check running time)
   • Task Scheduling 문제(최소요구되는machine수 계산)

---

거스름돈 문제

#include <iostream>
using namespace std;

void calculate_change(int change) {
    int coins[] = {10000, 5000, 1000, 500, 100, 50, 10};
    int coin_count[7] = {0};  // 각 화폐 단위별로 필요한 개수를 저장할 배열
    
    for (int i = 0; i < 7; i++) {
        coin_count[i] = change / coins[i];  // 해당 화폐 단위로 몇 개 필요한지 계산
        change %= coins[i];  // 나머지 금액 계산
    }

    // 결과 출력
    for (int i = 0; i < 7; i++) {
        if (coin_count[i] > 0) {
            cout << coins[i] << "원: " << coin_count[i] << "개" << endl;
        }
    }
}

int main() {
    int change;
    cout << "거스름돈 가격을 입력하세요: ";
    cin >> change;
    calculate_change(change);  // 거스름돈을 화폐 단위로 나누어 출력
    return 0;
}

 

• 그리디 알고리즘의 대표적인 문제 거스름돈 이다.
• 거슬러 주는 돈의 목표를 가장 적게 하는 것을 목표로 하므로, 돈이 큰 액수부터 채워서 주면 된다. 

 

---

Huffman coding

import heapq
from collections import defaultdict

# 노드를 나타내는 클래스
class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    
    # 비교 연산자 정의 (우선순위 큐에서 비교하기 위해)
    def __lt__(self, other):
        return self.freq < other.freq


def huffman_coding(text):
    # 1. 문자 빈도 계산
    freq = defaultdict(int)
    for char in text:
        freq[char] += 1
    # 2. 우선순위 큐에 빈도수로 노드를 삽입
    heap = []
    for char, f in freq.items():
        heapq.heappush(heap, Node(char, f))
    # 3. 트리 생성
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        # 새로운 내부 노드를 생성
        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)
    
    # 4. 트리에서 각 문자에 대한 코드 추출
    root = heap[0]
    codes = {}
    def generate_codes(node, current_code):
        if node is None:
            return
        if node.char is not None:
            codes[node.char] = current_code
        generate_codes(node.left, current_code + '0')
        generate_codes(node.right, current_code + '1')
    generate_codes(root, '')
    return codes

# 테스트할 텍스트
text = "Fuzzy Wuzzy was a bear. Fuzzy Wuzzy had no hair. Fuzzy Wuzzy wasn’t very fuzzy, was he?"
codes = huffman_coding(text)

# 결과 출력
print("Huffman Codes:")
for char, code in codes.items():
    print(f"{char}: {code}")

 

• Huffman coding은 자주나오는 글자일수록 더 적은 부호로 encoding 하여 최대한 길이를 줄이는 알고리즘이다.
• 이를 구현하기 위한 순서는 다음과 같다.

1. 우선 글자별로 빈도가 낮은 순서대로 나열한다.
2. 그리고 빈도가 가장 낮은 앞의 둘의 가중치를 합쳐 자식노드를 2개 가진 트리로 만든다.
3. 그 트리는 가중치에 맞게 우선순위 큐에 재배열 한다.
4. 이 과정을 계속 반복하면 트리끼리도 합쳐져 하나의 힙이 완성된다.
5. 왼쪽 자식은 0 오른쪽 자식은 1을 부여해가며 글자당 부여한 것을 완성해 간다.

• 그렇다면 왜 그냥 빈도수대로 정렬이 아닌 트리를 만드는 과정이 필요한 것일까?  그건 바로 1과 0으로 코딩하는 과정에서 모호성을 막기 위해서이다. 즉 10이 들어왔을때 이게 1과 0으로 이루어진 2개의 문자인지 아니면 10이라는 하나의 문자인지 헷갈리는 상황을 막을 수 있다.

---

Dijkstra's algorithm

import heapq  # 힙큐(우선순위 큐)를 사용하기 위한 라이브러리 임포트

def dijkstra(graph, start):
    # 거리 초기화: 모든 정점의 거리를 무한대로 설정
    distances = {vertex: float('inf') for vertex in graph}  # 각 정점의 거리를 무한대로 설정
    distances[start] = 0  # 시작 정점은 자기 자신으로부터의 거리 0
    
    # 우선순위 큐 (heapq 사용): (거리, 정점)의 형태로 저장
    pq = [(0, start)]  # 시작 정점의 거리와 정점을 큐에 삽입 (거리, 정점)
    
    while pq:
        # 우선순위 큐에서 가장 작은 거리 값을 가진 정점을 꺼냄
        current_distance, current_vertex = heapq.heappop(pq)
        
        # 현재 정점의 거리가 이미 기록된 거리보다 크면 무시 (이미 더 짧은 경로가 존재)
        if current_distance > distances[current_vertex]:
            continue
        
        # 현재 정점에 인접한 모든 노드들에 대해 확인
        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight  # 현재 정점까지의 거리 + 인접 정점까지의 가중치
            
            # 만약 새로 계산된 거리가 기존의 거리보다 짧으면 거리 갱신
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                # 갱신된 거리와 정점을 우선순위 큐에 추가
                heapq.heappush(pq, (distance, neighbor))
    
    # 모든 정점에 대한 최단 거리 계산 후 리턴
    return distances

# 예시 그래프 (인접 리스트로 표현된 그래프)
graph = {
    'A': [('B', 3), ('C', 5), ('D', 9)],  
    'B': [('A', 3), ('C', 3), ('D', 4)],  
    'C': [('A', 5), ('B', 3), ('D', 2), ('E', 6)], 
    'D': [('A', 9), ('B', 4), ('C', 2), ('E', 2), ('F', 2)],  
    'E': [('B', 7), ('C', 6), ('D', 2), ('F', 5)], 
    'F': [('C', 8), ('D', 2), ('C', 5)]  
}

start_vertex = 'A'  # 시작 정점
result = dijkstra(graph, start_vertex)  # 다익스트라 알고리즘 실행
print(result)  # 각 정점에 대한 최단 거리 출력

• 다익스트라 알고리즘은 출발점이 정해져 있고, 간선 가중치가 음수가 아닌 상황의 그래프에서 다른 정점까지의 최단경로를 구한다. 
• 무방향이든 방향이든 상관 없다.

순서는 다음과 같다.

1. 시작점을 정하고, 시작점까지의 거리는 0으로 다른 점들은 무한대로 정한다.
2. 시작점에서 갈수 있는 정점들을 선택하고, 무한대에서 더 빨리 갈 수 있는 작은 값으로 갱신한다.
3. 가장 짧은 거리가 기록된 정점을 선택한다. 그래서 그 정점을 시작 경로로 삼아 다시 그 점에서 이미 탐색한 시작점을 제외하고 인접 경로들을 갱신한다. 
4. 모든 정점이 처리될때까지 현재까지 구한 가장 최단거리인 정점을 꺼내고 그 연결된 정점으리 거리를 갱신한다. 
5. 그후 탐색이 안 된 점 중 가장 가중치가 적은 점으로 가 반복한다.

---

Minimum-cost Spanning Tree : Prim's Algorithm

import heapq

def prim(graph, start):
    # 우선순위 큐 (힙)
    min_heap = []
    # 트리에서 연결된 정점들 (방문한 정점들)
    visited = set()
    # 시작점에서의 간선들을 큐에 넣음
    heapq.heappush(min_heap, (0, start))  # (가중치, 정점)
    
    total_weight = 0  # 최소 신장 트리의 가중치 합
    
    while min_heap:
        # 가장 작은 가중치 간선 꺼내기
        weight, vertex = heapq.heappop(min_heap)
        
        if vertex not in visited:
            visited.add(vertex)
            total_weight += weight  # 해당 간선의 가중치 더하기
            
            # 연결된 인접 노드들 큐에 삽입
            for neighbor, edge_weight in graph[vertex]:
                if neighbor not in visited:
                    heapq.heappush(min_heap, (edge_weight, neighbor))
    
    return total_weight

# 예시 그래프 (인접 리스트로 표현)
graph = {
    'A': [('B', 2), ('C', 4)],
    'B': [('A', 2), ('C', 3), ('D', 9), ('G', 4),('H', 2)],
    'C': [('A', 4), ('B', 3), ('D', 1), ('E', 3)],
    'D': [('B', 9), ('C', 1), ('E', 3), ('F', 3),('G', 1)],
    'E': [('C', 3), ('D', 3), ('F', 2)],
    'F': [('D', 3), ('E', 2), ('G', 6)],
    'G': [('B', 4), ('D', 1), ('F', 6), ('H', 14)],
    'H': [('B', 2), ('G', 14)]
}

start_vertex = 'A'
result = prim(graph, start_vertex)
print(f"최소 신장 트리의 가중치 합: {result}")

 

• prim 알고리즘은 최소 신장 트리를 구하는 알고리즘 중 하나로 그래프의 모든 정점을 연결하는 트리 중 가중치의 합이 최소인 트리를 말한다. 순서는 다음과 같다.

1. 임의의 시작 정점을 고르고 인접한 모든 간선의 가중치를 기록한다.
2. 시작 정점의 인접 정점들을 우선순위큐에 먼저 넣고 최소값을 선택한다. 
3. 그렇게 우선순위 큐에서 선택한 정점의 간선들을 다시 트리에 추가하고, 새로운 정점의 인접 간섭을 큐에 넣는다.
4. 모든 정점이 트리에 포함될때까지 반복한다.

• 이 방식은 어떤 정점을 선택하든 간에 항상 그 정점을 지나기에 최적의 해를 보장한다. 어떤 정점이든 간에 인접한 간선 중 가장 가중치가 낮은 선은 어떻게해서도 쓰인다. 

 

---

Minimum-cost Spanning Tree : Kruskal's Algorithm

class UnionFind:
    def __init__(self, n):
        # 부모 노드 배열
        self.parent = list(range(n))
        # 트리의 크기 배열 (Union by Rank)
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX != rootY:
            # Union by rank (합치기)
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True
        return False

def kruskal(vertices, edges):
    # Union-Find 초기화 (정점의 수만큼 생성)
    uf = UnionFind(len(vertices))

    # 간선을 가중치 기준으로 오름차순 정렬
    edges.sort(key=lambda edge: edge[2])  # (u, v, weight)

    mst = []  # 최소 신장 트리를 저장할 리스트
    total_weight = 0  # 최소 신장 트리의 총 가중치

    for u, v, weight in edges:
        # 간선 (u, v)를 추가할 수 있다면
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight

    return mst, total_weight

# 주어진 그래프 (인접 리스트로 표현)
graph = {
    'A': [('B', 2), ('C', 4)],
    'B': [('A', 2), ('C', 3), ('D', 9), ('G', 4), ('H', 2)],
    'C': [('A', 4), ('B', 3), ('D', 1), ('E', 3)],
    'D': [('B', 9), ('C', 1), ('E', 3), ('F', 3), ('G', 1)],
    'E': [('C', 3), ('D', 3), ('F', 2)],
    'F': [('D', 3), ('E', 2), ('G', 6)],
    'G': [('B', 4), ('D', 1), ('F', 6), ('H', 14)],
    'H': [('B', 2), ('G', 14)]
}

# 정점에 대한 인덱스 매핑 (딕셔너리 사용)
vertex_index = {v: i for i, v in enumerate(graph.keys())}

# 간선 리스트 변환 (정점 이름 -> 인덱스 변환)
edges = [(vertex_index[u], vertex_index[v], weight) for u in graph for v, weight in graph[u]]

# Kruskal's Algorithm 실행
mst, total_weight = kruskal(list(vertex_index.keys()), edges)

# 결과 출력
print("최소 신장 트리 (간선, 가중치):")
for u, v, weight in mst:
    print(f"({list(vertex_index.keys())[u]}, {list(vertex_index.keys())[v]}), 가중치: {weight}")

print(f"최소 신장 트리의 총 가중치: {total_weight}")

• Kruskal의 알고리즘은 반면 MST를 간선중심으로 구한다. 가중치가 낮은 간선을 순서대로 정렬하고 사이클을 형성하지 않는다면 추가하는 방식이다.
• 이 간선이 사이클을 형성하는지 알기 위해서 Union-Find라는 자료구조를 사용한다. 같은 집합에 속해있는가? 로 연결되었는지 확인하고 싸이클을 형성하는지 보는 것이다. 만약 이미 같은 집합안에 들어가있는 두 원소를 연결한다면 싸이클이 형성된 것이다.

---

 

Job Scheduling : Minimum Time

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

void scheduleJobs(vector<int> jobs, int processors, string method) {
    // 정렬 기준에 따라 작업 정렬
    if (method == "shortest") {
        sort(jobs.begin(), jobs.end()); // 오름차순 정렬 (SJF)
    } else if (method == "longest") {
        sort(jobs.rbegin(), jobs.rend()); // 내림차순 정렬 (LJF)
    } else {
        cout << "Invalid method! Use 'shortest' or 'longest'." << endl;
        return;
    }
    // 프로세서 초기화
    vector<vector<int>> processorQueues(processors);
    vector<int> processorLoads(processors, 0);
    // 작업 분배
    for (int job : jobs) {
        // 가장 적은 작업량을 가진 프로세서에 추가
        int minProcessor = min_element(processorLoads.begin(), processorLoads.end()) - processorLoads.begin();
        processorQueues[minProcessor].push_back(job);
        processorLoads[minProcessor] += job;
    }
    // 결과 출력
    cout << (method == "shortest" ? "Shortest Job First (SJF):" : "Longest Job First (LJF):") << endl;
    for (int i = 0; i < processors; ++i) {
        cout << "Processor " << i + 1 << ": Jobs = [";
        for (size_t j = 0; j < processorQueues[i].size(); ++j) {
            cout << processorQueues[i][j];
            if (j < processorQueues[i].size() - 1) cout << ", ";
        }
        cout << "], Total Load = " << processorLoads[i] << endl;
    }
    cout << endl;
}

int main() {
    // 작업 리스트
    vector<int> jobs = {7, 12, 15, 9, 14, 6, 8, 10, 18, 11, 20, 13, 5, 16, 22, 4, 19, 25, 17, 21};
    int processors = 3;
    scheduleJobs(jobs, processors, "shortest");
    scheduleJobs(jobs, processors, "longest");

    return 0;
}

 

• 스케쥴러를 주어진 프로세서에 짧은시간 먼저 할당할지 긴 시간 먼저 할당할지 정하는 것으로, 전체로 보아 최적의 해를 보장하지는 않는다.
• 주어진 프로세서에서 가장 스케쥴을 적게 할당받은 곳에 정렬된 순서대로 작업을 넣는다. 

---

Job Scheduling : Minimum Processors

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

// 최소 프로세서를 계산하고 스케줄러별 작업을 출력
int minimumProcessors(const vector<pair<int, int>>& jobs) {
    vector<pair<int, int>> events;

    // 시작과 종료 이벤트로 변환
    for (int i = 0; i < jobs.size(); i++) {
        events.emplace_back(jobs[i].first, i + 1);  // 시작 이벤트, i+1은 Job ID
        events.emplace_back(jobs[i].second, -(i + 1));  // 종료 이벤트, 음수로 Job ID 표시
    }

    // 이벤트 정렬: 시간 기준 정렬, 종료(-)가 시작(+)보다 우선
    sort(events.begin(), events.end(), [](const auto& a, const auto& b) {
        return (a.first < b.first) || (a.first == b.first && a.second < b.second);
    });

    priority_queue<int, vector<int>, greater<int>> available; // 사용 가능한 프로세서 번호
    map<int, vector<int>> schedulerJobs;                     // 스케줄러별로 작업 기록
    int maxProcessors = 0;                                   // 필요한 최대 프로세서 수

    for (int i = 1; i <= jobs.size(); i++) {
        available.push(i);  // 초기화: 프로세서 번호를 모두 추가
    }

    map<int, int> jobToProcessor;  // 각 작업이 어느 프로세서에서 처리되는지 기록

    for (const auto& event : events) {
        int time = event.first;
        int jobId = abs(event.second);
        if (event.second > 0) {  // 작업 시작
            int processor = available.top(); // 가장 작은 번호의 프로세서를 선택
            available.pop();                 // 해당 프로세서를 사용 중으로 표시
            schedulerJobs[processor].push_back(jobId); // 해당 프로세서에 작업 추가
            jobToProcessor[jobId] = processor;         // 작업-프로세서 매핑 기록
            maxProcessors = max(maxProcessors, (int)schedulerJobs.size());
        } else {  // 작업 종료
            int processor = jobToProcessor[jobId];
            available.push(processor); // 프로세서를 다시 사용 가능 상태로 변경
        }
    }

    // 결과 출력
    cout << "Scheduler Tasks:\n";
    for (const auto& [processor, tasks] : schedulerJobs) {
        cout << "Processor " << processor << ": ";
        for (int job : tasks) {
            cout << "Job_" << job << " ";
        }
        cout << endl;
    }

    return maxProcessors;
}

int main() {
    // 시작 시간, 종료 시간 (Job 목록)
    vector<pair<int, int>> jobs = {
        {38, 49}, {28, 38}, {14, 23}, {10, 20}, {21, 33},
        {22, 31}, {47, 59}, {13, 24}, {25, 34}, {35, 46},
        {41, 50}, {3, 17}, {17, 28}, {5, 19}, {26, 39},
        {37, 46}, {8, 22}, {32, 42}, {24, 37}, {40, 54}
    };

    int processors = minimumProcessors(jobs);
    cout << "\n최소 필요한 프로세서 수: " << processors << endl;

    return 0;
}

• 이건 반대로 시작시간과 종료시간이 주어졌을때 최소로 필요한 프로세서 개수를 계산하는 알고리즘이다.
• 겹치는 시간이 최고로 많을때, 몇개나 겹치는지 기록하는 방식이다. 
• (시작시간, +1), (끝나는 시간, -1)을 mapping 하여 앞의 시간을 순서대로 오름차순으로 정렬 후 계산한다.

 

---

결론

Greedy method에 관한 내용이었다.