| 작성자 | 장원준 |
| 일 시 | 2024. 11. 05 (화) 18:00 ~ 21:00 |
| 장 소 | 미래관 429호 자율주행스튜디오 |
| 참가자 명단 | 임혜진, 장원준, 이재영, 성창민, 김명원 |
| 사 진 |  |
Greedy Algorithm의 이해와 활용 예제
알고리즘은 문제를 해결하는 방법을 체계화한 논리적인 절차를 의미합니다. 대표적인 알고리즘의 패러다임으로는 Brute-force, Divide and Conquer, Dynamic Programming, 그리고 오늘의 주제인 Greedy Algorithm이 있습니다. 각 패러다임은 문제의 성격에 맞는 접근 방법을 제시하며, 각기 다른 상황에 최적화된 솔루션을 제공합니다.
알고리즘 패러다임 개요
- Brute-force: 가능한 모든 경우를 하나하나 살펴보는 방식입니다. 최적의 결과를 보장하지만, 경우의 수가 많을 경우 비효율적일 수 있습니다.
- Divide and Conquer: 문제를 작은 하위 문제로 나누고, 각 하위 문제를 재귀적으로 해결한 뒤 이를 합쳐서 전체 문제를 해결하는 방법입니다.
- Dynamic Programming: 작은 문제의 결과를 메모해두고 이를 재활용하여 전체 문제를 해결하는 방식입니다. 반복적인 계산을 줄여 효율을 높입니다.
Greedy Algorithm이란?
Greedy Algorithm (탐욕 알고리즘)은 현재 상황에서 가장 좋아 보이는 것을 선택하는 전략입니다. 이는 미래의 상황은 고려하지 않고, 현재 순간의 선택이 최적의 해를 도출할 것이라고 가정합니다. 하지만 이 접근법은 항상 최적해를 보장하지 않으며, **Local Optimum (지역 최적해)가 Global Optimum (전역 최적해)으로 이어지지 않을 수도 있습니다.
Greedy Algorithm을 사용해야 하는 두 가지 조건
- Greedy-choice property (탐욕적 선택 속성): 현재의 최선의 선택이 전체 최적해의 일부가 되어야 합니다.
- Optimal sub-structure property (최적 부분 구조 속성): 작은 문제의 최적해가 큰 문제의 최적해에 포함되어야 합니다.
위 두 가지 조건을 만족하는 경우 Greedy Algorithm은 최적해를 보장할 수 있습니다.
Greedy Algorithm을 적용할 수 있는 문제들
1. 거스름돈 문제
문제 링크: 백준 5585번
거스름돈 문제에서는 여러 종류의 동전이 충분히 주어졌을 때, 최소한의 동전 개수로 잔돈을 줄 수 있도록 해야 합니다. Greedy Algorithm을 사용해 아래와 같이 해결할 수 있습니다:
- 남은 잔돈보다 가치가 낮은 동전 중 가장 큰 동전을 사용합니다. (Greedy Choice)
- 남은 잔돈에서 사용한 동전의 값을 빼고, 이를 반복합니다.
이 문제는 Greedy-choice property와 Optimal sub-structure property를 모두 만족하여 최적해를 보장합니다. 하지만 동전의 단위가 배수 형태를 갖지 않는 경우 Greedy Algorithm은 최적해를 보장할 수 없습니다. 예를 들어, 동전이 500원, 300원, 70원, 30원인 경우 600원을 만들기 위해 Greedy Algorithm을 적용하면 500원 + 70원 + 30원 = 3개의 동전을 사용하게 되지만, 최적해는 300원 + 300원 = 2개의 동전입니다.
2. 회의실 배정 문제
문제 링크: 백준 1931번
회의실 배정 문제는 가능한 많은 회의를 배정할 수 있는 방법을 찾는 문제입니다. 가능한 모든 경우를 조사하면 경우의 수가 2^N이 되어 비현실적이므로 Greedy Algorithm을 통해 해결할 수 있습니다.
여러 전략 중 최적의 선택:
- 종료 시간이 빠른 회의부터 선택하는 것이 최적해를 보장합니다.
Greedy-choice property와 Optimal sub-structure property를 만족하므로, 종료 시간이 빠른 순서로 회의를 선택하면 최적의 회의 배정 방법을 구할 수 있습니다.
Greedy Algorithm은 현재의 최선의 선택이 전체 최적해에 포함될 수 있을 때 효과적이라는 것을 느꼈습니다.. 하지만 이러한 속성이 없는 문제에서는 Greedy Algorithm이 최적해를 보장하지 않으므로 Dynamic Programming이나 다른 알고리즘을 고려하는 것이 효율적이라는 것도 알게되었습니다.