🐨그리디 알고리즘

그리디 알고리즘

그리디 알고리즘은 최적해 찾기에 사용되는 알고리즘으로, 각 단계에서 순간적으로 최적으로 보이는 선택을 하는 근시안적 방법을 사용한다. 이 방법은 선택을 수집해 전역적인 답을 만들어 내지만, 이 전역적인 답이 항상 전역적 최적해와 같다는 보장은 없다. 그리디 알고리즘은 주로 탐욕스런 선택 조건과 최적 부분 구조 조건을 만족할 때 잘 작동한다. 만약 이 조건들을 만족하지 않는다면, 근사 알고리즘으로서의 역할을 할 수 있다.

정의

탐욕스런 선택 조건 (Greedy Choice Property)

이전의 선택이 이후의 선택에 영향을 주지 않는다.

출처: https://newbie22.tistory.com/179

최적 부분 구조 조건 (Optimal Substructure)

문제의 최적해가 그 문제의 부분 문제에서도 최적해가 된다.

https://namu.wiki

잘 되는 예: 거스름돈 문제 (Coin Change Problem)

문제 상황

상점에서 물건을 구매한 후, 받게 되는 거스름돈을 가장 적은 수의 동전으로 줘야 한다. 사용할 수 있는 동전의 종류가 500원, 100원, 50원, 10원이라면, 이 문제는 어떻게 해결할 수 있을까?

해결 방법

1. 탐욕스런 선택 조건: 매 순간 거스름돈을 줄 때, 가장 가치가 큰 동전부터 준다. 이 방법은 이후의 선택에 영향을 주지 않으며, 남은 거스름돈에 대해서도 같은 방식으로 선택을 계속한다.
2. 최적 부분 구조 조건: 큰 문제의 최적해를 작은 문제의 최적해를 조합하여 얻을 수 있다. 예를 들어, 거스름돈이 800원일 때, 첫 선택으로 500원을 주고 남은 300원에 대해서도 최적의 방식으로 거스름돈을 준다.

예시

거스름돈이 860원일 경우, 500원 1개, 100원 3개, 50원 1개, 10원 1개를 줌으로써 총 6개의 동전으로 거스름돈을 줄 수 있다.

최적해를 보장하지 않는 예: 배낭 문제 (0/1 Knapsack)

문제 상황

물건을 쪼갤 수 없으며, 각 물건을 배낭에 넣거나 넣지 않는 선택만 할 수 있다. 이 문제에서 그리디 알고리즘을 적용하려고 할 때, 단위 무게당 가치가 높은 물건을 선택하는 방식으로 접근할 수 있지만, 이 방법은 항상 최적의 해를 보장하지 않는다.

예시

배낭의 무게 제한이 50kg이고, 물건 A(가치 60, 무게 10kg), 물건 B(가치 100, 무게 20kg), 물건 C(가치 120, 무게 30kg)가 있다고 할 때, 단위 무게당 가치를 기준으로 그리디 알고리즘을 적용하면 A와 B를 선택하는 것이 최적으로 보인다. 하지만 실제 최적의 해는 B와 C를 선택하는 것이며, 더 높은 가치를 얻을 수 있다.

그리디 알고리즘은 각 단계에서의 최적의 선택이 전체 문제의 최적해로 이어진다는 보장이 없는 경우, 최적해를 찾지 못할 수 있다. 그러므로 문제의 특성을 잘 이해하고 적용하는 것이 중요하다.

매트로이드(Matroid)는 수학적 구조 중 하나로, 그리디 알고리즘의 이론적 기반 중 하나입니다. 매트로이드를 이해하기 위해서는 두 가지 주요 개념을 알아야 합니다: 독립성과 기본 집합입니다. 매트로이드는 이러한 개념들을 통해, 어떤 문제에서 그리디 알고리즘이 최적의 해를 찾을 수 있는지를 판단하는 데 도움을 줍니다.

최적해를 보장하지 않는 예: 여행하는 세일즈맨 문제(Traveling Salesman Problem, TSP)

여행하는 세일즈맨 문제(Traveling Salesman Problem, TSP)는 그리디 알고리즘으로 풀기 어려운 대표적인 예시다. 이 문제는 모든 도시를 한 번씩 방문하고 시작점으로 돌아오는 최단 경로를 찾는 것이다. 여기서 최단 경로를 찾는 것이 주된 목표다.
그리디 알고리즘은 매 순간 최선의 선택을 하며 문제를 해결해 나간다. 하지만 TSP에서는 그리디 알고리즘이 항상 최적의 해를 찾지 못한다. 그 이유를 몇 가지 살펴보자.

1. 근시안적 선택

그리디 알고리즘은 근시안적으로만 최적의 선택을 한다. 예를 들어, 가장 가까운 다음 도시를 선택하는 방식(nearest neighbor)으로 TSP를 해결하려 하면, 초기에는 효율적으로 보일 수 있다. 하지만, 이러한 근시안적 선택이 최종적으로는 더 긴 경로를 초래할 수 있다.

2. 최적 부분 구조의 부재

TSP는 최적 부분 구조를 가지지 않는다. 최적 부분 구조란, 전체 문제의 최적해가 부분 문제의 최적해들로 구성되어야 한다는 것을 의미한다. 그러나 TSP에서는 어떤 경로가 부분 경로에서는 최적이었다 하더라도, 전체 경로에서 최적이라는 보장이 없다.

3. 탐욕스런 선택 조건의 위배

탐욕스런 선택 조건이란, 선택이 이후의 선택에 영향을 주지 않아야 한다는 것이다. 그러나 TSP에서는 한 번의 선택이 이후의 모든 선택에 영향을 미친다. 모든 도시를 방문해야 하며, 한 번 방문한 도시는 다시 방문할 수 없기 때문에, 초기 선택이 나중에 이용할 수 있는 선택지를 크게 제한한다.

결론

따라서 TSP는 그리디 알고리즘으로는 최적의 해를 보장할 수 없는 문제다. TSP를 해결하기 위한 접근 방법으로는 동적 계획법, 분기 한정법, 유전 알고리즘 등 다양한 방법이 연구되고 있다. 이러한 방법들은 그리디 알고리즘보다 더 복잡할 수 있지만, TSP 같은 NP-하드 문제에 대해 보다 나은 해결책을 제공한다.

매트로이드의 구성 요소

1. 유한 집합

매트로이드는 기본적으로 유한 집합 E를 가지고 시작합니다. 이 집합은 문제에서 고려해야 하는 모든 가능한 선택들의 집합입니다.

2. 독립성

유한 집합 E의 부분집합들 중 일부는 독립적인 부분집합으로 정의됩니다. 이 독립적인 부분집합들의 집합을 I라고 하며, 특정 조건(예: 조합이 가능하거나, 규칙을 만족시키는 등)을 만족하는 경우에만 독립적이라고 할 수 있습니다.

매트로이드에서는 다음과 같은 세 가지 중요한 성질이 있어야 합니다:

1. 공집합 성질: 공집합은 항상 독립적입니다.
2. 부분집합 성질: 집합 A가 독립적이라면, A의 모든 부분집합도 독립적입니다.
3. 교환 성질: 두 독립적인 집합 A와 B에 대해, A의 크기가 B보다 작으면, B에서 A에 포함되지 않은 원소를 추가하여 A의 크기를 늘릴 수 있으며, 이때 결과적으로 얻어진 집합도 독립적입니다.

3. 기본 집합

매트로이드에서 기본 집합은 최대 독립 집합을 의미합니다. 즉, 더 이상의 원소를 추가하면 독립성을 잃는 집합입니다. 모든 기본 집합은 동일한 크기를 가집니다.

매트로이드의 예

예: 그래프의 최소 신장 트리

주어진 연결 그래프에서 모든 정점을 연결하면서 가중치의 합이 최소가 되는 트리(최소 신장 트리)를 찾는 문제를 생각해 봅시다. 이 문제에서 그리디 알고리즘이 최적의 해를 찾을 수 있는 이유는, 그래프의 최소 신장 트리 문제가 매트로이드의 성질을 만족하기 때문입니다.

• 유한 집합 E: 그래프의 모든 간선들
• 독립적인 부분집합 I: 사이클을 형성하지 않는 간선들의 집합
• 기본 집합: 최소 신장 트리를 형성하는 간선들의 집합

이 예시에서, 각 단계에서 가장 작은 가중치를 가진 간선을 선택하는 그리디 방식은 매트로이드의 성질을 만족하므로 최적의 해를 보장합니다.

요약

매트로이드는 독립적인 부분집합들의 구조와 이러한 부분집합들의 성질을 통해 정의됩니다. 매트로이드의 개념은 그리디 알고리즘이 특정 문제에 대해 최적의 해를 보장할 수 있는지 여부를 판단하는 데 유용하며, 그래프 이론, 네트워크 설계, 최적화 문제 등 다양한 분야에서 응용됩니다.

정리

그리디 알고리즘은 문제를 해결할 때 매 순간 가장 좋아 보이는 선택을 하는 방법이다. 마치 사탕 가게에서 가장 큰 사탕만 골라 담는 것처럼. 하지만 항상 가장 큰 사탕만 고른다고 해서 가방에 가장 많은 사탕을 담을 수 있는 건 아니다. 이 방법이 잘 작동하려면 특별한 조건이 필요하다.

예를 들어, 거스름돈 문제에서는 가장 큰 동전부터 거슬러 주면 동전을 가장 적게 사용해 거슬러 줄 수 있다. 이런 문제는 그리디 알고리즘으로 잘 해결할 수 있다.

그리디 알고리즘은 언제 최고의 해결책을 줄 수 있는지 알아보는 데 매트로이드라는 수학적 아이디어가 도움을 준다. 매트로이드는 여러 선택지 중에서 독립적인 선택들을 모아 최고의 답을 찾는 방법을 알려준다. 예를 들어, 나무로 이루어진 숲에서 나무들을 연결해서 가장 짧은 다리를 만드는 문제가 있을 때, 가장 짧은 나무부터 하나씩 골라 연결하면 가장 짧은 다리를 만들 수 있다.

이렇게 매트로이드와 그리디 알고리즘은 문제를 해결하는데 아주 좋은 도구다. 하지만 모든 문제가 이 방법으로 해결될 수 있는 건 아니다. 문제를 잘 보고 이 방법이 잘 맞는지 확인해야 한다.

회의실 배정 문제

 

https://ggasoon2.tistory.com/38

백준 1931번: 회의실 배정 (실버1) python

https://source-sc.tistory.com/59

[탐욕 알고리즘][2] - 회의실 배정 문제

 

레퍼런스

https://source-sc.tistory.com/58?category=973666

[탐욕 알고리즘][1] - 개요

https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그리디 알고리즘

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

https://dad-rock.tistory.com/663

[Algorithms] Greedy Algorithms | 그리디 알고리즘, 탐욕 알고리즘

https://brilliant.org/wiki/greedy-algorithm/

Greedy Algorithms | Brilliant Math & Science Wiki