[Python] 그리디 알고리즘

슈·2024년 7월 2일

코딩테스트 개념

목록 보기

11/17

그리디 알고리즘

그리디 알고리즘(Greedy Algorithm)은 문제 해결 과정에서 매 단계마다 가장 최적이라고 생각되는 선택을 하는 알고리즘이다. 각 단계에서 이루어진 선택은 이후의 선택에 영향을 주지 않으며, 현재 상태에서 가장 좋은 선택을 계속해서 함으로써 전체 최적해를 도출하려고 시도한다.

일반적으로 다음 두 가지 조건을 만족할 때 유용하다.

탐욕적 선택 속성 (Greedy Choice Property)
각 단계에서 내린 탐욕적 선택이 이후의 선택에 영향을 주지 않으며, 전체 문제의 최적해로 이어질 수 있습니다.

최적 부분 구조 (Optimal Substructure)
문제에 대한 최적해가 부분 문제의 최적해들로 구성될 수 있습니다.

💡 특징

특정 상황에서 매우 유용하지만, 문제의 특성에 따라 다른 알고리즘(예: 동적 계획법, 백트래킹 등)을 사용하는 것이 더 적절할 수도 있다.

🙆‍♀️ 장점

구현이 간단하고 이해하기 쉽다.
많은 경우에 대해 효율적인 해법을 제공한다.
특정 문제에 대해 최적해를 빠르게 도출할 수 있다.

🙅‍♀️ 단점

모든 경우에 대해 최적해를 보장하지 않는다.
일부 문제에서는 잘못된 선택을 할 가능성이 있다.

🔍 단계

문제의 최적해 구조를 결정한다.
문제의 구조에 맞게 선택 절차를 정의한다
→ 선택 절차(Selection Procedure)

📌 선택 절차(Selection Procedure)
이 단계에서는 ‘현재 상태’에서 ‘최적인 선택’을 한다.
이 선택은 이후에는 바뀌지 않는다.

선택 절차에 따라 선택을 수행한다.
선택된 해가 문제의 조건을 만족하는지 검사한다.
→ 적절성 검사(Feasibility Check)

📌 적절성 검사(Feasibility Check)
이 단계에서는 선택한 항목이 ‘문제의 조건’을 만족시키는지 확인한다.
조건을 만족시키지 않으면 해당 항목은 제외된다.

조건을 만족하지 않으면 해당 해를 제외한다.
모든 선택이 완료되면 해답을 검사한다.
→ 해답 검사(Solution Check)

📌 해답 검사(Solution Check)
이 단계에서는 모든 선택이 완료되면, ‘최종 선택’이 ‘문제의 조건을 만족’시키는지 확인한다.
조건을 만족시키면 해답으로 인정된다.

조건을 만족하지 않으면 해답으로 인정되지 않는다.

💻 빈출 예제

1. 거스름돈

문제: 최소한의 동전으로 특정 금액을 거슬러 줘야 한다.

예를 들어, 동전의 단위가 1원, 5원, 10원, 50원, 100원인 경우, 472원을 거슬러 줄 때 그리디 알고리즘을 사용하면 다음과 같이 풀이할 수 있다.

가장 큰 단위의 동전으로 최대한 많이 거슬러 준다.
100원짜리 동전 4개 -> 472 - 400 = 72
남은 금액에 대해 다시 가장 큰 단위의 동전으로 최대한 많이 거슬러 준다.
50원짜리 동전 1개 -> 72 - 50 = 22
이를 반복한다.
10원짜리 동전 2개 -> 22 - 20 = 2
1원짜리 동전 2개 -> 2 - 2 = 0

이 결과로, 총 4 + 1 + 2 + 2 = 9개의 동전으로 472원을 거슬러 줄 수 있다.

2. 회의실 배정 문제

문제: 한 개의 회의실을 사용하고자 하는 여러 회의들의 시간표가 주어질 때, 가능한 한 많은 회의를 배정하는 것.

각 회의를 종료 시간 기준으로 정렬한다.
가장 먼저 끝나는 회의를 선택하고, 이 회의가 끝나기 전까지 시작하지 않는 회의들 중 가장 먼저 끝나는 회의를 선택한다.
이를 반복한다.

💻 그리디 알고리즘과 동적 계획법 비교

구분	그리디 알고리즘	동적 계획법
기본 개념	각 단계에서 가장 최적의 선택을 함	문제를 작은 부분 문제로 나누어 해결함
접근 방식	현재 상태에서 최적의 선택을 반복함	부분 문제의 해를 이용해 전체 문제 해결
문제 유형	탐욕적 선택 속성과 최적 부분 구조를 가질 때 유리함	최적 부분 구조와 중복 부분 문제를 가질 때 유리함
복잡도	일반적으로 더 적은 시간 복잡도를 가짐	더 높은 시간 및 공간 복잡도를 가질 수 있음
해결 과정	단순하고 직관적	비교적 복잡하고 체계적
재사용 가능성	부분 해를 재사용하지 않음	부분 해를 저장하고 재사용함
구현 난이도	구현이 상대적으로 간단함	구현이 상대적으로 복잡함
적용 예시	거스름돈 문제, 회의실 배정 문제 등	피보나치 수열, 배낭 문제, 최단 경로 문제 등
결과	항상 최적해를 보장하지 않음	최적해를 보장함