목록탐욕 (1)

개발아 담하자

[Algorithm] 그리디 알고리즘이란? (활동 선택 문제, 분할 가능 배낭 문제)

Greedy Algorithm 이란? 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 탐욕 알고리즘, 욕심쟁이 알고리즘 으로도 불린다. 매 순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하 최종적인 최적해에 도달하는 기법이다. 활동 선택 문제 (Activity Selection Problem) 한 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우를 고르는 것이다. Si는 시작시간, Fi는 종료시간이다. (서로 수업 시간이 겹치면 안 된다.) 직관적으로 생각하면, 최적의 해를 구하기 위해서는 첫 번째 활동이 최대한 일찍 끝나면 된다. 그래야 다른 활동을 더 많이 선택할 수 있기 때문이다. 위의 경우 첫 선택으로 가장 ..
🌟 자료구조+알고리즘 2020. 3. 30. 01:11
이전 Prev 1 Next 다음