[Problem Solving Paradigms] Greedy

Greedy

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

• 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

 

# 동작하기 위한 조건

• Logical oprimum의 존재
• greedy한 방법으로 global optimal solution에 도달 가능하다는 것을 증명 가능해야 함
• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

# 문제 해결 방법

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

 

# 활용 꿀팁

• 대부분의 문제들에서 greedy를 사용하여 global optimal solution을 구할 수 있다는 것을 대회 중에 증명하는 것은 상당히 어렵다.
• 입력 사이즈가 작은경우 complete search나 DP를 우선적으로 고려하지만 입력사이즈가 너무 커서 다른 방법들이 통하지 않을 것처럼 보인다면 greedy를 우선적으로 고려해보자.
• 문제에서 greedy를 사용할 수 있는지 애매한 경우에는 보통 입력 데이터를 sorting 하면 더욱 명확하게 파악 가능하다.

 

 

 

아리아나 그란데가 부릅니다 그리데~~~ 훠우

https://www.youtube.com/watch?v=Nwa3Ud_VRVU