Hello World

백준 1931 : 회의실 배정 문제 링크: www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 내용: 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. Idea: 이 문제..

탐욕 알고리즘 Greedy Algorithm 탐욕 알고리즘이란? 최적화 문제를 해결하는 알고리즘으로 근시안적인 방법이다. 그 순간이 최적이라고 생각되는 것을 선택해 나가는 방식이다. 각 결정은 지역(local)적으로는 최적이나, 전체(global)적으로 봤을 때 최적이라는 보장은 없다. 대표 문제 동전 문제 배낭 문제 활동 선택 문제(회의실 배정) ... 동전 문제 Q. 어떻게 거스름돈의 개수를 최소한으로 줄일 수 있을까? [접근방법] 그 당시 거슬러줄 수 있는 가장 큰 액수의 동전을 선택한다. coin = 0 이면 종료 coin > 0 이면, coin보다 작거나 같은 동전 중 가장 큰 동전(m)을 선택 coin = coin - m 1~3 반복 *그러나 이 방법은 모든 coin system에서 동작한다는..