목록그리디 알고리즘 (1)

홍카나의 공부방

[Algorithm] 그리디 알고리즘 정리 + 백준 추천 문제

그리디 알고리즘(Greedy Algorithm)은 '탐욕(Greedy)'이라는 이름에 알맞게 지금 당장 가질 수 있는 최고의 이익을 따라가는 알고리즘을 의미한다. 모든 경우 최적해를 보장하지는 못하지만, 드물게 최적해를 결과로 내는 경우도 있다. 합리적인 시간 내로 최적에 가까운 해답을 찾을 수 있다는 점에서 유용한 알고리즘이다. 그리디 알고리즘이 잘 작동하는 문제들은 이전의 선택이 이후의 선택에 영향을 주지 않는 문제들이 많다. 물론 꼭 그렇지 않더라도 괜찮은 정답을 찾을 수 있는 알고리즘이다. 다이나믹 프로그래밍(DP)과는 최적 부분 구조 문제를 푼다는 점에서 약간 다른데, DP가 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이를 이용한 전역 최적 솔루션을 찾는 것이라면 그리디는 각 단계마다 지역 ..
Data Structure + Algorithm 2023. 2. 28. 21:57
이전 Prev 1 Next 다음