Algorithm

그리디 알고리즘

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 그리디 알고리즘이란? 그리디 알고리즘이란 탐욕법이라고도 하며 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 여러 경우 중 하나를 결정해야 할 때마다 그 순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 종합적으로 봤을땐 최적이라는 보장은 절대 없나는 것을 명심해야한다. 그리디 알고리즘을 적용하기 위한 조건 그리디 알고리즘을 적용하기 위한 조건으로는 탐욕스런 선택 조건과 최적 부분 구조 조건이 있으며, 이 두가지 조건이 만족되야 그리디 알고리즘이 잘 동작한다. 탐욕스런 선택 조건 -. 앞의 선..