Hello, Freakin world!

www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성�� www.acmicpc.net 문제 풀이 모든 지원자 중 자신보다 면접, 서류 분야 점수가 더 낮은 사람이 존재하는 경우 탈락하게 됩니다. 입력이 크기 때문에 N^2 로는 통과할 수 없습니다. 아래의 그림을 살펴보면 힌트를 얻을 수 있습니다. 빨간색으로 체크 친 지원자가 떨어지게 되는데, 해당 포인트는 점선으로 이뤄진 영역에 임의의 포인트를 포함합니다. 먼저 x축으로 입력을 정렬한 후 어떤 포인트를 포함하는 경우는 ..

www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이들을 보면서 왜 끝나는 시간에 대해 정렬하는가? 일찍 끝나는 회의부터 배정하는 방법이 최적해가 될 것임을 어떻게 증명할 것인가? 라는 생각들이 들었습니다. 답을 얻으면서 그리디 알고리즘에 대해 깊이 생각해 볼 수 있었습니다. 왜 먼저 끝나는 시간에 대해 정렬하는가? 위에 대한 답은 '탐욕법을 적용할 최적의 부분 구조를 만들기 위해서' 라는 결론을 얻었습니다. 이를 이해하기 위해서는 회의실을 배정한다는 행위에 대한 이해도 필요합니다. 회의실을 배정받기 위해서는 기본적으로 이전의 회의가 없거나 끝나 있어야 합니다. 만약 회의실을..