목록알고리즘/탐욕 알고리즘 (Greedy) (2)

프로그래밍에 대한 고찰 및 생각

[탐욕 알고리즘][2] - 회의실 배정 문제

유명한 Greedy 알고리즘 - 회의실 배정 문제 회의실 배정 문제는 그리디 알고리즘에서 빠지지 않고 등장하는 문제이다. 이문제는 각 회의마다 시작시간과 종료시간이 정해져있고 하나의 회의실에 대해 가장 많은 회의를 진행하게 하고 싶을때 그 개수를 구하는 문제이다. 이 문제에서의 최종 목표는 최대한 많은 회의를 진행시키는 것 이다. 여기서 조건은 회의마다 시작시간과 끝나는시간이 정해져있다는 것과, 두 회의간 겹쳐서는 안된다는 점이다. Think1. 가장 짧은 회의들 먼저 진행시키면 되지않을까? 굉장히 Greedy한 접근법이다. 최대한 많은 회의를 진행시키려면 결국 회의시간이 짧은 회의들을 골라서 넣는것이 최적의 해를 만들어 줄것같다. 과연 그럴까? 위와같이 a~g까지 7개의 회의들이 있다고 가정해보자. 여..
알고리즘/탐욕 알고리즘 (Greedy) 2021. 3. 17. 02:52
[탐욕 알고리즘][1] - 개요

탐욕 알고리즘(Greedy Algorithm) 탐욕 알고리즘(이하 그리디)은 어떤 문제를 해결할때 모든 경우의 수를 전부 고려하지 않고 항상 최적이 되는 것만 골라서 진행해나가는 알고리즘을 의미한다. 모든 경우의 수를 전부 고려해서 최적의 해를 계산해내는 dynamic programming과는 다르다. 그렇다면 두가지 의문이 들수있다. 1. 항상 최적의 해만 골라서 탐색하면 지금까지 왜 dynamic programming으로 모든 경우의 수를 분석했나? 왜냐하면 그리디 알고리즘으로 모든 문제를 해결할 수 있는것이 아니기때문이다. 현재 상황에서는 가장 최적의 해라고 생각했지만 이후에 상황에 따라 그때의 선택이 최선의 결과를 만들지 않을수도 있기때문이다. 2. 그렇다면 그리디 알고리즘은 최선일수도 있고 아닐..
알고리즘/탐욕 알고리즘 (Greedy) 2021. 3. 17. 02:06
이전 Prev 1 Next 다음