파이썬 Python | 알고리즘 | Greedy algorithm(그리디 알고리즘, 탐욕법)

⭕ 파이썬 Python | 알고리즘 | Greedy algorithm(그리디 알고리즘, 탐욕법)

• 현재 상황에서 가장 좋아 보이는 선택을 연속적으로 하여 최종적인 해결책에 도달하는 방식
• 문제를 해결하기 위해 순간마다 가장 최선의 선택을 해나가며, 각 단계에서의 선택이 그 이후의 선택들에게 제약을 주지 않는 방향으로 진행되어야 함
• 정당성 분석: 반드시 그 선택이 실제로 최적해에 도달할 수 있다는 것을 증명하는 정당성 분석이 필요함

 

➡️ 조건

1. 탐욕스러운 선택 조건(Greedy Choice Property): 우리가 한 선택이 다음 선택과 나머지 문제 해결에 영향을 주지 않고, 그 선택이 최종적으로 최적의 해결책을 가져다 줄 수 있다는 것
2. 최적 부분 구조 조건(Optimal Substructure): 큰 문제를 작은 문제로 나누고, 이 작은 문제들의 최적의 해결책들을 결합하여 전체 문제의 최적해를 도출할 수 있어야 함

 

⭕ 회의실 배정 - 1391.py

핵심: 최대한 많은 회의를 배정하기 위해 회의가 끝나는 시간을 기준으로 오름차순 정렬한 후, 순차적으로 회의를 선택하는 것

 

➡️ Think1: 가장 짧은 회의들을 먼저 진행

• 짧은 회의가 오랜 시간 동안 진행되는 회의와 시간이 겹칠 수 있으며, 이 경우 다른 회의를 배정할 기회를 잃을 수 있는 경우가 있음
• 따라서, 단순히 회의의 길이만을 고려하는 것이 아니라, 회의가 언제 끝나는지도 함께 고려하는 것이 중요함

 

➡️ Think2: 회의가 끝나는 시간을 기준으로 오름차순 정렬

• 회의가 끝난 직후 바로 다음 회의를 시작할 수 있는 최적의 선택을 할 수 있게 됨