반응형
그리디 알고리즘
-
알고리즘: 그리디 알고리즘(Greedy Algorithm) 공부하고 예제 한번 풀어보자!알고리즘 2020. 7. 13. 13:51
그리디 알고리즘이란(Greedy Algorithm)이란? 뜻 그대로 탐욕스런 알고리즘이라고 생각하면 쉽다. 미래를 내다 보지 않고 당장 눈 앞에 보이는 최적의 선택을 하는 방식이다. 그리디 알고리즘은 간단하고 빠르지만, 항상 최적의 답이 보장되지는 않는다. 그래서 보통 최적의 답이 필요 없는 경우에 사용하지만 그리디 알고리즘이 최적의 답을 보장해 주는 문제도 있다. 그리디 알고리즘은 다음과 같은 조건을 만족할때 최적의 답을 보장한다. (다음과 같은 조건이 없어도 그리디 알고리즘을 사용할 수는 있다.) → 최적 부분 구조가 있을 때 문제를 부분 문제로 나누어 해결하여 기존 문제의 답을 찾아낼 수 있는 경우 → 탐욕적 선택 속성을 갖고 있을 때 다이나믹 프로그래밍처럼 답의 모든 부분을 고려하지 않고 탐욕적 ..