greedy algorithm

[Algorithm] 탐욕(Greedy) 알고리즘이란

안녕하세요. Harry입니다. 본 포스팅의 목적은, 코딩테스트를 준비함에 있어 스스로 공부한 지식을 정리하고자 합니다. - 무슨 개념인지? - 개념이 나오게 된 배경은? - 그 개념은 왜 쓰는지? - 장점/단점은 무엇인지? - (유사한 것이 있다면) 서로 차이는 무엇인지? 를 최대한 고려하여 정리해보겠습니다. 1. 그리디 알고리즘이란?(what?) 그리디 알고리즘은, 당장 좋은 것만을 고르는 알고리즘이다. 즉, 당장 주어진 선택지 중에서 눈앞에 보이는 가장 최적의 상황을 고르는 것으로, 그 이후에 발생할 상황을 고려하지 않는다는 것이다. 그러므로 직관적이지만 국소적(local)이므로 결과론적(global)으로 봤을 때 항상 최적의 해답을 보장하지 않는다. 예를 들어, 현재 선택할 수 있는 선택지 중에서 ..