그리디(greedy) 알고리즘 탐욕법

그리디 알고리즘이란?

➡️현재 상태에서 보는 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

 

그리디 알고리즘 3단계

• 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택
• 작잘상 감시 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
• 해 검사 : 현재까지 선텍힌 해 집합이 전체 문제를 해결할 수 있는지 검사
  ➡️전체 문제 해결 못할시 다시 1단계로 가서 같은 과정 반복

그리디 알고리즘의 장점

• 단순성: 그리디 알고리즘은 직관적이고 이해하기 쉬워서 구현이 간단합니다.
• 속도: 매 단계에서 최적의 선택을 하므로 계산 속도가 빠릅니다.
• 효율성: 많은 문제에서 그리디 알고리즘은 적절한 해를 빠르게 제공합니다.

그리디 알고리즘의 단점

• 최적해 보장 불가: 그리디 알고리즘은 항상 최적해를 보장하지 않습니다. 즉, 그리디 알고리즘으로 풀 수 없는 문제가 존재합니다.
• 문제 특성: 그리디 알고리즘이 최적해를 보장하려면 문제 자체가 그리디 특성을 가져야 합니다.

 

<우선순위 큐 : 그리디 알고리즘에서 자주 사용하는 자료구조>

[PriorityQueue]

from queue import PriorityQueue

#생성방법
myqueue = PriorityQueue()

put(data) #원소 추가하기
get() #큐에서 데이터 꺼내기
qsize() #큐 사이즈 가져오기
empty() #큐가 비어있는지 확인하기