greedy2 [C++] 백준 1931번: 회의실 배정 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거.. 2021. 11. 1. [알고리즘] 탐욕(그리디) 알고리즘 그리디 알고리즘이란? 탐욕적 알고리즘이라고도 하며, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. A에서 C까지 가는 최단 경로는? A에서 B로 갈 때 가장 적은 비용인 20을 고른다. B에서 C로 갈 때 가장 적은 비용인 8을 고른다. A에서 C로 가는 최단 경로는 20+8=28인 것을 알 수 있다! 이 문제는 선택의 순간마다 가장 적은 비용이 드는 길을 찾아가는 방법으로 풀 수 있었다. 아래의 문제도 위와 같이 그때그때 가장 최적의 값을 고르는 방법으로 풀어야 할까? 총 합이 최대의 값을 얻는 방법은? 위의 방법처럼 그때그때 최적의 값을 골라보자. start에서 시작하여 최대의 값을 얻어야 하니 15로 가보자. .. 2021. 11. 1. 이전 1 다음
