[Do it!_Algorithm with Python] 3. Greedy Algorithm

https://devowen.com/260

백준 2109 / 그리디(Greedy) 알고리즘 / JAVA

이 포스팅을 참고하여 공부하였다.

 

 

탐욕 알고리즘이란, 현재 상태에서 가장 최선의 선택지를 선택하다보면, 전체 선택지 중에 가장 최적의 선택지를 얻어낼 것이라고 가정하고 풀어가는 방법이다.

즉, 지금 상태에서 할 수 있는 최선의 길로 가다보면 내 인생에서 최고의 길로 가게 될 거라는...그런 가정..🥲 (난 이렇게 믿고 살고있는데엑)

 

 

하지만, 이 알고리즘의 최대 단점은, 이 값이 전체를 총 아울렀을 때 최적의 해가 될 것이라는 걸 보장하지 않는다는 것이다.

위 그림에서 보면 실제 최대값은 99이지만, greedy 알고리즘을 사용했을 때 12에 도달하는 것을 볼 수 있다.

 

따라서 greedy algorithm은 최적의 해를 도출할 수도 있고~ 아닐 수도 있다.

 

 

▪️과정

1) 해를 선택한다 : 현재 상태에서 가장 최선이라고 여겨지는 해를 선택

2) 적절성을 검사한다 : 현재 선택한 해가, 전체 문제의 제약 조건에 벗어나지 않는지 검사

3) 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 만약 해결하지 못하면 다시 1)로 돌아가서 반복

 

 

 

더 자세한 예시와 설명은 위에 링크한 포스팅을 참고하길 바랍니다.

저는 이만 코드로 구현하러 가보겠습니다.