그리디 알고리즘 (Greedy Algorithm)

탐욕 알고리즘 또는 그리디 알고리즘(Greedy Algorithm)은 각 단계에서 지금까지의 선택이 최적이라고 가정하고 진행하여 최종적으로 최적해에 도달하는 것을 목표로 한다. 이는 현재 상황에서 가장 좋아보이는 선택을 수행함으로써 지역 최적해를 찾아 전역 최적해를 구하는 것을 말한다.

Baekjoon - Greedy

다음은 일반적으로 코딩 테스트에서 자주 출제되는 몇 가지 자료 구조와 관련된 문제 유형이다.

Fractional knapsack problem

분할 가능한 배낭 문제(Fractional knapsack problem)은 한 가방(또는 컨테이너)에 담을 수 있는 무게 제한이 있는 경우, 주어진 물건들의 가치와 무게를 고려하여 가장 큰 가치를 가진 물건들을 선택하는 문제이다. 이 문제에서는 물건들을 부분적으로 쪼갤 수 있으며, 부분적으로 쪼개진 물건은 비율에 따라 가치와 무게가 책정된다.

Baekjoon - Knapsack

---

Fractional knapsack problem은 다음과 같은 과정을 통해 해결된다:

1. 각 물건의 단위 가치 계산: 각 물건의 가치를 무게로 나누어 단위 가치를 계산한다. 단위 가치는 해당 물건의 무게 당 가치를 의미한다.
2. 물건들의 단위 가치를 기준으로 정렬: 물건들을 단위 가치에 따라 내림차순으로 정렬한다. 이렇게 되면 가장 높은 단위 가치를 가진 물건이 가장 앞에 위치하게 된다.
3. 가장 높은 단위 가치를 가진 물건부터 선택: 가방에 담을 수 있는 무게 내에서 가장 높은 단위 가치를 가진 물건을 선택한다. 만약 해당 물건을 모두 담을 수 없는 경우, 물건을 부분적으로 쪼개서 일부만 담는다.
4. 다음으로 높은 단위 가치를 가진 물건 선택: 이전 단계에서 선택한 물건을 제외한 나머지 물건들 중에서 다음으로 높은 단위 가치를 가진 물건을 선택한다. 선택한 물건을 가방에 담을 수 있는지 확인하고, 담을 수 있다면 담는다.
5. 담을 수 있는 물건이 없을 때까지 반복: 가방에 더 이상 담을 수 있는 물건이 없을 때까지 4단계를 반복한다. 각 단계에서 선택한 물건의 가치와 무게를 기록하고, 가방에 담긴 물건들의 총 가치를 계산한다.

def fractional_knapsack(values, weights, capacity):
    # 물건 당 가치를 계산
    value_per_weight = [(v / w, w, v, i) for i, (v, w) in enumerate(zip(values, weights))]

    # 가치 대비 무게로 정렬
    value_per_weight.sort(reverse=True)

    total_value = 0
    fractions = [0] * len(values)

    for _, w, v, i in value_per_weight:
        if capacity >= w: # 배낭에 물건을 전부 넣을 수 있는 경우
            fractions[i] = 1
            total_value += v
            capacity -= w
        else: # 배낭에 물건을 일부분만 넣을 수 있는 경우
            fractions[i] = capacity / w
            total_value += fractions[i] * v
            break  # 물건이 다 차면 종료

    return total_value, fractions

# 물건의 가치와 무게
values = [120, 100, 60]
weights = [30, 20, 10]
knapsack_capacity = 50

max_value, fractions_taken = fractional_knapsack(values, weights, knapsack_capacity) # 240.0, [0.6666666666666666, 1, 1]

Activity Selection Problem

활동 선택 문제(Activity Selection Problem)은 여러 개의 활동 중에서 최대한 많은 수의 활동을 선택하는 문제로, 각 활동은 시작 시간과 끝 시간을 가지고 있다. 하지만 활동들이 서로 겹치지 않고, 같은 시간에 두 개 이상의 활동을 수행할 수 없다는 전제 조건이 있다. 따라서 활동들을 서로 겹치지 않게 선택하여 최대한 많은 활동을 선택하는 것이 목표이다.

Baekjoon - 회의실 배정

---

Activity Selection Problem은 다음과 같은 과정을 통해 해결된다:

1. 활동들을 종료 시간을 기준으로 정렬한다.
2. 첫 번째 활동은 선택된 것으로 시작한다.
3. 선택된 활동의 종료 시간보다 다음 활동의 시작 시간이 더 늦는 경우, 해당 활동을 선택한다.
4. 이를 가능한 많이 반복하여 최대한 많은 활동을 선택한다.

def activity_selection(start_time, finish_time):
    activities = sorted(zip(start_time, finish_time), key=lambda x: x[1])  # 종료 시간을 기준으로 정렬
    selected_activities = [activities[0]]  # 첫 번째 활동은 선택

    for i in range(1, len(activities)):
        # 현재 활동의 시작 시간이 이전에 선택한 활동의 종료 시간보다 늦으면 선택
        if activities[i][0] >= selected_activities[-1][1]:
            selected_activities.append(activities[i])

    return selected_activities

# 활동의 시작 시간과 종료 시간
start_time = [1, 3, 0, 5, 8, 5]
finish_time = [2, 4, 6, 7, 9, 9]

selected_activities = activity_selection(start_time, finish_time) # [(1, 2), (3, 4), (5, 7), (8, 9)]

Huffman Code

허프만 코드(Huffman code)는 데이터를 효율적으로 압축하기 위한 인코딩 방식 중 하나이다. 이 방식은 빈도가 높은 문자 또는 기호에 짧은 이진 코드를 할당하고, 낮은 빈도를 가진 문자에는 긴 이진 코드를 할당하여 전체 데이터의 평균 비트 수를 줄인다.

허프만 코드는 무손실 압축 방식으로, 원본 데이터를 완벽하게 복원할 수 있다. 주로 파일 압축이나 데이터 전송에서 사용되며, 예를 들어 텍스트 파일에서 각 문자에 대한 허프만 코드를 사용하여 파일 크기를 줄일 수 있다.

허프만 코드를 생성하기 위해 사용되는 알고리즘은 주어진 데이터의 문자 빈도를 분석하여 최적의 이진 코드를 만들어낸다. 이를 위해 보통 허프만 트리라고 불리는 이진 트리를 생성하고, 이를 기반으로 각 문자에 대한 이진 코드를 생성한다.

Baekjoon - 허프만 트리

from collections import Counter
import heapq

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

class HuffmanTree:
    def __init__(self, text):
        self.root = self._build_tree(text)
        self.codes = self._build_codes()

    def _build_tree(self, text):
        frequency = Counter(text)
        priority_queue = [Node(char, freq) for char, freq in frequency.items()]
        heapq.heapify(priority_queue)

        while len(priority_queue) > 1:
            left = heapq.heappop(priority_queue)
            right = heapq.heappop(priority_queue)
            merge = Node(None, left.freq + right.freq)
            merge.left = left
            merge.right = right
            heapq.heappush(priority_queue, merge)

        return priority_queue[0]

    def _build_codes(self):
        codes = {}
        self._build_codes_recursive(self.root, "", codes)
        return codes

    def _build_codes_recursive(self, node, current_code, huffman_codes):
        if node is None:
            return

        if node.char is not None:
            huffman_codes[node.char] = current_code
            return

        self._build_codes_recursive(node.left, current_code + "0", huffman_codes)
        self._build_codes_recursive(node.right, current_code + "1", huffman_codes)

    def encode(self, text):
        encoded_text = ""
        for char in text:
            encoded_text += self.codes[char]
        return encoded_text

    def decode(self, encoded_text):
        decoded_text = ""
        current_node = self.root
        for bit in encoded_text:
            if bit == "0":
                current_node = current_node.left
            else:
                current_node = current_node.right

            if current_node.char is not None:
                decoded_text += current_node.char
                current_node = self.root

        return decoded_text

    def get_codes(self):
        return self.codes

text = "hello world"

# 허프만 트리 생성
huffman_tree = HuffmanTree(text)

# 문자열 인코딩
encoded_text = huffman_tree.encode(text) # 11100001010110111101111001010001

# 문자열 디코딩
decoded_text = huffman_tree.decode(encoded_text) # hello world

# 허프만 코드 확인
huffman_codes = huffman_tree.get_codes() # {'e': '000', 'd': '001', 'r': '010', 'w': '011', 'l': '10', 'o': '110', 'h': '1110', ' ': '1111'}

Prim Algorithm

프림 알고리즘(Prim Algorithm)은 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 데 사용되는 그래프 알고리즘이다. 최소 신장 트리란, 가중치가 있는 그래프에서 모든 노드를 포함하면서 가중치의 합이 최소인 트리를 말한다. 이때, 트리는 사이클이 없고 모든 노드가 연결되어 있어야 한다.

프림 알고리즘은 시작 노드에서부터 시작하여, 아직 트리에 포함되지 않은 노드들 중에서 가장 작은 가중치의 간선을 선택하며 최소 신장 트리를 구축해 나간다. 이 과정을 모든 노드가 포함될 때까지 반복한다. 일반적으로 시간 복잡도는 O(E log V)인데, 여기서 V는 노드의 수이고, E는 간선의 수를 나타낸다.

Baekjoon - Minimum Spanning Tree

---

아래는 프림 알고리즘의 동작 예시이다:

1. 시작 정점을 선택한다.
2. 해당 정점과 연결된 간선들을 우선순위 큐에 넣는다.
3. 우선순위 큐에서 가장 작은 가중치를 가진 간선을 선택한다.
4. 선택한 간선의 반대쪽 정점을 트리에 추가한다.
5. 새로운 정점과 연결된 간선들 중에서 아직 트리에 포함되지 않은 정점과의 간선들을 우선순위 큐에 넣는다.
6. 위의 과정을 반복하여 최소 신장 트리를 완성한다.

import heapq

'''
edge 정보를 담은 graph
key는 node1, value는 모든 (weight, node1, node2) 정보가 있는 리스트
양방향의 graph만 고려하며, 한 edge에 연결된 두 node(key)에 모두 edge(value) 정보를 넣음
'''
graph = {1: [(1, 1, 2), (3, 1, 4), (8, 1, 3)],
         2: [(1, 2, 1), (2, 2, 4), (7, 2, 5)],
         3: [(8, 3, 1), (4, 3, 4), (5, 3, 5)],
         4: [(3, 4, 1), (2, 4, 2), (4, 4, 3), (6, 4, 5)],
         5: [(7, 5, 2), (5, 5, 3), (6, 5, 4)]}

root = 1 # 시작 node

def prim(graph, root):

    visited = [False] * (len(graph) + 1) # node 방문 정보
    total_weight = 0 # MST의 총 weight
    mst = [] # MST를 구성하기 위한 edge 리스트 [edge1, edge2, ...], edge는 (node1, node2)로 표현됨

    visited[root] = True
    candidate = graph[root]
    heapq.heapify(candidate)

    while candidate:
        weight, u, v = heapq.heappop(candidate)
        if visited[v] == False:
            visited[v] = True
            mst.append((u, v))
            total_weight += weight

            for edge in graph[v]:
                if visited[edge[2]] == False:
                    heapq.heappush(candidate, edge)

    return total_weight, mst

total_weight, mst = prim(graph, root) # 12, [(1, 2), (2, 4), (4, 3), (3, 5)]

Kruskal Algorithm

크루스칼 알고리즘(Kruskal Algorithm)은 가중치가 있는 그래프에서 최소 신장 트리를 구하는 알고리즘으로, 탐욕적인 방식을 사용하여 간선을 선택하고 사이클을 피해 최적해를 찾는다. 시간 복잡도는 O(E log E)이며, 모든 노드를 포함하고 간선 가중치의 합이 최소인 트리를 생성한다.

Baekjoon - Minimum Spanning Tree

---

아래는 크루스칼 알고리즘의 동작 과정이다:

1. 초기화: 모든 노드를 독립적인 집합으로 간주하고, 그래프의 간선들을 가중치에 따라 오름차순으로 정렬한다.
2. 간선 선택: 가중치가 가장 낮은 간선부터 순서대로 선택하면서, 해당 간선의 양 끝 노드가 서로 다른 집합에 속해 있다면 선택한다. 이 선택은 사이클을 만들지 않도록 한다.
3. 집합 합치기: 선택한 간선을 통해 두 개의 집합을 하나로 합친다. 즉, 선택한 간선의 두 노드를 같은 집합으로 만든다.
4. 모든 노드가 하나의 집합에 속할 때까지 2번과 3번 단계를 반복한다.

'''
edge 즉, (weight, node1, node2) 정보를 담은 graph
양방향의 graph만 고려하며, 중복된 edge는 없음
'''
graph = [(1, 1, 2), (3, 1, 4), (8, 1, 3), (2, 2, 4),
         (7, 2, 5), (4, 3, 4), (5, 3, 5), (6, 4, 5)]

N = 5 # node 개수
root = list(range(N + 1)) # 각 node의 root 정보

def find(v, root):

    if v != root[v]:
        root[v] = find(root[v], root)

    return root[v]

def union(u, v, root):

    u = find(u, root)
    v = find(v, root)

    if u < v:
        root[v] = u
    else:
        root[u] = v

def kruskal(graph, root):

    graph.sort()
    total_weight = 0  # MST의 총 weight
    mst = [] # MST를 구성하기 위한 edge 리스트 [edge1, edge2, ...], edge는 (node1, node2)로 표현됨

    for weight, u, v in graph:
        if find(u, root) != find(v, root):
            total_weight += weight
            mst.append((u, v))
            union(u, v, root)

    return total_weight, mst

total_weight, mst = kruskal(graph, root) # 12, [(1, 2), (2, 4), (4, 3), (3, 5)]

Dijkstra Algorithm

다익스트라 알고리즘 (Dijkstra Algorithm)은 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 그래프 알고리즘이다. 이 알고리즘은 음의 가중치를 가진 간선이 없는 경우에 사용되며, 가장 짧은 경로를 찾는 문제에 적용된다. 시간 복잡도는 최악의 경우 O((V+E)logV)로 갖는다.

Baekjoon - Dijkstra's

---

다익스트라 알고리즘의 동작은 다음과 같다:

1. 출발 정점을 지정한다.
2. 출발 정점으로부터 각 정점까지의 최단 거리를 저장할 배열을 초기화한다. 출발 정점은 0으로 초기화하고 나머지 정점들은 무한대(또는 매우 큰 값)로 초기화한다.
3. 현재 정점에서 인접한 모든 정점들에 대해 최단 거리를 업데이트한다. 즉, 현재까지 알려진 최단 거리보다 더 짧은 경로를 찾으면 해당 정점까지의 거리를 업데이트한다.
4. 방문하지 않은 정점 중에서 최단 거리가 가장 짧은 정점을 선택하여 해당 정점을 현재 정점으로 설정한다.
5. 모든 정점을 방문할 때까지 3-4 단계를 반복한다.

import heapq

'''
edge 정보를 담은 graph
key는 node1, value는 모든 (weight, node2) 정보가 있는 리스트
단,양방향의 graph 모두 고려하며, 한 edge에 연결된 두 node(key)에 모두 edge(value) 정보를 넣음
'''
graph = {
    1: {(8, 2), (1, 3), (2, 4)},
    2: {},
    3: {(5, 2), (2, 4)},
    4: {(3, 5), (5, 6)},
    5: {(1, 6)},
    6: {(5, 1)}
}

start = 1 # 시작 node
end = 6

def dijkstra(graph, start, end = None):

    distances = [float('inf') for _ in range(len(graph) + 1)] # start node로부터의 거리
    distances[start] = 0
    queue = [] # 가장 작은 distance를 얻기 위한 queue
    parents = [0 for _ in range(len(graph) + 1)] # 이전 node 정보
    path = [] # end - start까지 이동하는 최단 경로

    heapq.heappush(queue, (distances[start], start))

    while queue:

        current_distance, current_node = heapq.heappop(queue)

        if distances[current_node] < current_distance:
            continue

        for new_distance, next_node in graph[current_node]:
            distance = current_distance + new_distance
            if distance < distances[next_node]:
                distances[next_node] = distance
                parents[next_node] = current_node
                heapq.heappush(queue, [distance, next_node])

    while end:
        path.append(end)
        end = parents[end]

    return distances[1:], path[::-1]

distances, path = dijkstra(graph, start, end) # ([0, 6, 1, 2, 5, 6], [1, 4, 5, 6])