짜리몽땅 매거진

그리디 알고리즘은 현재 시점에서 지금 당장 좋은 것만 고르는 방법으로 '탐욕법'이라고 부르기도 한다. 그리디 알고리즘은 다음과 같은 특징을 지니고 있다. - 일반적인 상황에서 최적의 해를 보장할 수 없다. - 코딩테스트에서 대부분의 그리디 문제는 그리디 알고리즘으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제된다. 코딩테스트에서는, - 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높다. - 정렬 라이브러리의 사용법이 필요하다. - 일반적으로는 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력만을 요구한다. - 정당성 분석이 중요하다. 탐욕법으로 문제를 풀어도 최적의 해를 구할 수 있는가? 그리디 알고리즘으로 분류되는 코딩테스트 문제를 백준 알고리즘 사이트에서 풀..