Algorithm(코딩테스트)/코딩테스트 문제 풀이 | 그리디 알고리즘(Greedy)2 [백준] 13458 : 시험 감독 (C++) 문제 문제 분석 - 문제를 꼼꼼히 잘 읽고 예외 케이스를 잘 파악해야 되는 문제이다. - 특히 시험장의 개수가 최대 100만개이고, 각 시험에 있는 응시자 수가 100만명이며, 감독관이 한 시험장에서 감시할 수 있는 수도 모두 1 (B=1, C=1) 이라고 가정했을 때 시간 초과와 자료형에 유의해야 되는 문제이다. [시간 초과] - 아래 코드와 같이 while 문을 돌릴 경우, 시험장의 개수가 100만개이고 각 시험에 있는 응시자 수가 100만명이면서, 총감독관, 부감독관 모두 한 시험장에서 감시할 수 있는 응시자의 수가 1명일 때, 최악의 경우 100만 * 100만 번의 연산이 필요하게 된다. - C++은 1초당 3억~5억번의 연산을 할 수 있고 이 문제의 경우 제한 시간이 2초이므로 적어도 6억번의 .. 2024. 2. 9. [C++ 백준 1931번] 회의실 배정 (그리디) 문제 문제 분석 문제를 읽고 아이디어가 필요한 문제이다. N이 10만이므로 O(n^2)을 넘기면 안되고 다소 아이디어가 필요할 수 있다는걸 생각해볼 수 있었다. 최소 회의수를 구하기 위해 정렬을 해야될 것 같은 느낌이 들었고 정렬과 연결되어 하나의 최적해가 문제를 푸는데 일반화될 수 있다면 그리디 알고리즘에 해당될 수 있다는 것을 눈치챌 수 있었다. 문제를 풀기 위한 아이디어는 먼저 시작 시간을 내림차순으로 정렬하고, 해당 미팅의 종료 시간 p2.first; // 1순위 :시작 시간을 기준으로 내림차순 return p1.second > p2.second; // 2순위 : 시작 시간이 같은 경우 끝 시간을 기준으로 내림차순 } int main(void) { ios_base::sync_with_stdio(f.. 2024. 2. 2. 이전 1 다음
