[이것이 코딩테스트다 with 파이썬] 그리디 알고리즘

최근 보고 있는 책인  '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 책을 읽으면서 정리하고자 한다.

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만을 고르는 방법이다. 이는 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않는다.

 

'가장 큰 순서대로', '가장 작은 순서대로' 와 같이 표현되는 문제에 적합하다.

'가장 큰 화폐 단위부터' 돈을 거슬러주고 각 화폐단위는 배수 관계를 가지고 있다는 조건과 같이 탐욕적으로 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있다면 효과적이다. 하지만 문제의 해법을 찾은 경우 문제의 해법이 정당한지 또한 검토해야 한다.

 

 즉 문제를 풀 때, 문제 풀이를 위한 최소한의 아이디어를 떠올린 뒤, 정당한지 검토를 한 후 문제 풀이를 진행해야 한다.

 

 이를 염두하면서 문제 풀이를 수행해보자.