본문 바로가기
CS/알고리즘

[Algorithm/알고리즘] Greedy - 그리디 알고리즘(탐욕법) 이해하기

MayQ 2025. 5. 21. 22:40

그리디(Greedy) 알고리즘, 탐욕법

그리디 알고리즘(Greedy Algorithm)은 각 단계에서 최적의 선택을 반복하여 문제를 해결하는 알고리즘입니다. 이 알고리즘은 매 순간 최선의 선택을 하기 때문에 단기적인 최적화를 목표로 합니다. 그러나 항상 전체 문제에 대한 최적해를 보장하지는 않습니다.

그리디 알고리즘의 특징

  1. 탐욕적 선택 속성(Greedy Choice Property): 각 단계에서 현재 상태에서 최적의 선택을 합니다.
  2. 최적 부분 구조(Opimal Substructure): 문제의 최적해가 부분 문제의 최적해로 구성될 수 있습니다.

그리디 알고리즘의 예

1. 동전 거스름돈 문제

예를 들어, 1원, 5원, 10원, 50원 동전이 있을 때 63원을 거슬러 주는 문제입니다. 그리디 알고리즘은 가장 큰 단위의 동전부터 사용하여 50원 1개, 10원 1개, 1원 3개로 해결합니다.

2. 활동 선택 문제(Activity Selection Problem)

여러 활동 중에서 서로 겹치지 않게 최대한 많은 활동을 선택하는 문제입니다. 각 활동을 종료 시간이 빠른 순서대로 선택합니다. 다음은 Python 코드 예제입니다:

# 활동의 시작 시간과 종료 시간을 튜플로 묶어서 리스트로 정의
activities = [(0, 6), (1, 4), (3, 5), (3, 8), (4, 7), (5, 9), (6, 10), (8, 11)]

# 종료 시간을 기준으로 활동을 정렬
# sorted() 함수와 lambda 함수를 사용하여 두 번째 요소(종료 시간)를 기준으로 정렬
activities.sort(key=lambda x: x[1])

# 선택된 활동을 저장할 리스트를 초기화
selected_activities = []

# 마지막으로 선택된 활동의 종료 시간을 저장할 변수 초기화
last_end_time = 0

# 모든 활동을 순회하면서
for start, end in activities:
    # 현재 활동의 시작 시간이 마지막으로 선택된 활동의 종료 시간보다 크거나 같으면
    if start >= last_end_time:
        # 현재 활동을 선택된 활동 리스트에 추가
        selected_activities.append((start, end))
        # 마지막으로 선택된 활동의 종료 시간을 현재 활동의 종료 시간으로 업데이트
        last_end_time = end

# 선택된 활동들을 출력
print("선택된 활동:", selected_activities)

코드 설명

활동 정의:

activities = [(0, 6), (1, 4), (3, 5), (3, 8), (4, 7), (5, 9), (6, 10), (8, 11)]
  • activities 리스트에는 각 활동의 시작 시간과 종료 시간을 튜플로 묶어서 저장합니다.

활동 정렬:

activities.sort(key=lambda x: x[1])
  • sorted() 함수와 lambda 함수를 사용하여 활동들을 종료 시간을 기준으로 오름차순으로 정렬합니다. 이는 활동 선택 문제의 그리디 알고리즘에서 중요한 단계입니다.

선택된 활동 리스트 초기화:

selected_activities = []
  • 최종적으로 선택된 활동들을 저장할 빈 리스트를 초기화합니다.

마지막 종료 시간 초기화:

last_end_time = 0
  • 마지막으로 선택된 활동의 종료 시간을 저장할 변수를 초기화합니다. 처음에는 0으로 설정하여 모든 활동의 시작 시간이 이보다 크거나 같게 만듭니다.

활동 순회:

for start, end in activities:
  • 정렬된 활동 리스트를 순회합니다.

활동 선택 조건 검사:

if start >= last_end_time:
  • 현재 활동의 시작 시간이 마지막으로 선택된 활동의 종료 시간보다 크거나 같으면 현재 활동을 선택합니다.

활동 선택 및 종료 시간 업데이트:

selected_activities.append((start, end))
last_end_time = end
  • 현재 활동을 selected_activities 리스트에 추가하고, 마지막 종료 시간을 현재 활동의 종료 시간으로 업데이트합니다.

선택된 활동 출력:

print("선택된 활동:", selected_activities)
  • 선택된 활동들을 출력합니다.

3. 크루스칼 알고리즘 예제

다음은 크루스칼 알고리즘을 사용하여 최소 신장 트리를 찾는 Python 코드입니다. 각 줄마다 상세한 설명을 포함하여 주석을 추가했습니다.

from collections import defaultdict

# 그래프 클래스를 정의
class Graph:
    def __init__(self, vertices):
        # 정점 수를 저장
        self.V = vertices
        # 그래프를 빈 리스트로 초기화
        self.graph = []

    # 간선을 그래프에 추가하는 메서드
    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    # 특정 원소의 부모를 찾는 메서드
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    # 두 원소를 합치는 메서드
    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    # 크루스칼 알고리즘을 구현한 메서드
    def kruskal(self):
        result = []
        i, e = 0, 0

        # 간선을 가중치 기준으로 정렬
        self.graph = sorted(self.graph, key=lambda item: item[2])

        parent = []
        rank = []

        # 부모와 랭크 초기화
        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        # 정렬된 간선을 순회하며 최소 신장 트리를 구성
        while e < self.V - 1:
            u, v, w = self.graph[i]
            i += 1
            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                e += 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result

# 그래프 초기화
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)

# 크루스칼 알고리즘을 실행하고 결과 출력
print("최소 신장 트리의 간선들:")
for u, v, weight in g.kruskal():
    print(f"{u} - {v}: {weight}")

코드 설명

  1. 그래프 클래스 정의
    • Graph 클래스 정의 및 초기화: 정점 수와 그래프를 초기화합니다.
from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []
  1. 간선 추가 메서드
    • 간선 추가 메서드 정의: 간선을 그래프에 추가하는 메서드를 정의합니다.
    • 각 간선은 시작 정점 u, 끝 정점 v, 가중치 w를 포함하는 리스트로 저장됩니다.
def add_edge(self, u, v, w):
    self.graph.append([u, v, w])
  1. 부모 찾기 메서드
    • 부모 찾기 메서드 정의: 특정 원소의 부모를 재귀적으로 찾는 메서드를 정의합니다.
def find(self, parent, i):
    if parent[i] == i:
        return i
    return self.find(parent, parent[i])
  1. 합집합 연산 메서드
    • 합집합 연산 메서드 정의: 두 원소를 합치는 메서드를 정의합니다.
    • 부모와 랭크를 사용하여 트리의 높이를 최소화합니다.
def union(self, parent, rank, x, y):
    xroot = self.find(parent, x)
    yroot = self.find(parent, y)
    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1
  1. 크루스칼 알고리즘 메서드
    • 크루스칼 알고리즘 메서드 정의: 크루스칼 알고리즘을 구현한 메서드입니다.
    • 간선을 가중치 기준으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 최소 신장 트리를 구성합니다.
def kruskal(self):
    result = []
    i, e = 0, 0

    self.graph = sorted(self.graph, key=lambda item: item[2])

    parent = []
    rank = []

    for node in range(self.V):
        parent.append(node)
        rank.append(0)

    while e < self.V - 1:
        u, v, w = self.graph[i]
        i += 1
        x = self.find(parent, u)
        y = self.find(parent, v)
        if x != y:
            e += 1
            result.append([u, v, w])
            self.union(parent, rank, x, y)

    return result
  1. 그래프 초기화 및 결과 출력
    • 그래프 초기화 및 간선 추가: 그래프를 초기화하고, 간선을 추가합니다.
    • 크루스칼 알고리즘 실행 및 결과 출력: 크루스칼 알고리즘을 실행하여 최소 신장 트리의 간선을 출력합니다.
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)

print("최소 신장 트리의 간선들:")
for u, v, weight in g.kruskal():
    print(f"{u} - {v}: {weight}")

그리디 알고리즘의 장점과 단점

  • 장점:
    • 간단하고 이해하기 쉽습니다.
    • 많은 문제에서 효율적인 해결책을 제공합니다.
  • 단점:
    • 항상 최적해를 보장하지 않습니다.
    • 문제의 성질에 따라 적용할 수 없는 경우가 있습니다.

마무리

그리디 알고리즘은 많은 문제에서 빠르고 효율적인 해결책을 제공합니다. 특히, 탐욕적 선택 속성과 최적 부분 구조를 가진 문제에서 그리디 알고리즘은 매우 효과적입니다. 그리디 알고리즘은 매 순간 최선의 선택을 함으로써 전체 문제를 해결하는 접근 방식을 사용하며, 이는 복잡한 문제를 단순화하고 빠르게 해결할 수 있는 방법을 제공합니다.

예를 들어, 동전 거스름돈 문제나 활동 선택 문제와 같은 간단한 문제뿐만 아니라, 크루스칼 알고리즘을 통한 최소 신장 트리 찾기, 다익스트라 알고리즘을 통한 최단 경로 찾기 등 복잡한 그래프 문제에서도 그리디 알고리즘은 유용하게 사용됩니다.

그러나 그리디 알고리즘이 항상 최적의 결과를 보장하지 않는다는 점을 이해하는 것이 중요합니다. 그리디 알고리즘은 단기적인 최적 선택을 반복함으로써 전체 최적해를 찾으려 하지만, 일부 문제에서는 이 접근 방식이 전체 최적해를 보장하지 못할 수 있습니다. 예를 들어, 배낭 문제에서 그리디 알고리즘은 분할 가능한 항목에 대해서는 최적해를 제공할 수 있지만, 분할 불가능한 항목에 대해서는 최적해를 보장하지 못합니다.

또한, 그리디 알고리즘은 문제의 특성에 따라 적용할 수 있는지 여부가 결정됩니다. 문제의 특성을 잘 이해하고 그리디 알고리즘을 적용할 수 있는 문제인지 판단하는 것이 중요합니다. 이는 문제의 최적 부분 구조와 탐욕적 선택 속성이 충족되는지 확인하는 과정입니다.

결론적으로, 그리디 알고리즘은 다양한 문제에서 빠르고 효율적으로 적용될 수 있는 강력한 도구이지만, 문제의 특성을 잘 이해하고, 그리디 알고리즘이 최적해를 보장할 수 있는지 여부를 신중하게 평가하는 것이 중요합니다. 이러한 이해를 바탕으로 그리디 알고리즘을 적절히 적용하면, 많은 문제에서 효과적인 해결책을 도출할 수 있습니다.

'CS > 알고리즘' 카테고리의 다른 글

[Algorithm] Dijkstra - 다익스트라 알고리즘 이해하기  (0) 2025.05.21
[Algorithm] 투 포인터(Two Pointer) 알고리즘 이해하기  (0) 2025.05.21
[Algorithm/알고리즘] Trie - 트라이 자료구조 이해하기  (1) 2025.05.21
[Algorithm/알고리즘] LCA - 최소 공통 조상 알고리즘 이해하기  (0) 2025.05.21
[Algorithm/알고리즘] DFS - 깊이 우선 탐색 알고리즘 이해하기  (0) 2025.05.21

'CS/알고리즘' Related Articles

티스토리툴바