📝 Greedy(Tree, PQ)
⭕️ 1135번 : 뉴스 전하기 (골드2)
- 문제 유형 : greedy, sort, dp, tree
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 트리 정보를 인접리스트를 이용하여 저장
- 재귀를 이용해서 리프 노드부터 자신의 아래 위치에 뉴스가 전해지는 데 가장 오래 걸리는 시간을 구하여 리턴
- 자식 노드(직속 부하 직원)들의 직속 부하 직원 수를 배열에 저장하고 내림차순 정렬한 뒤 한 번에 한 사람에게만 전달 할 수 있기 때문에 배열의 앞에서부터 1씩 늘려가며 소요시간을 더함 (+1, +2, +3, ... , +n) (많은 부하 직원을 가진 부하 직원부터 가장 먼저 전달해야 시간 소요가 최소화)
- 배열을 오름차순 재정렬한 뒤에 가장 앞에 있는 시간(가장 오래 걸리는 시간)을 리턴
- 루트 노드(매니저)까지 진행 후 구해진 시간이 최소 시간
⭕️ 13975번 : 파일 합치기 3 (골드4)
- 문제 유형 : greedy, PriorityQueue
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 파일 크기를 기준으로 오름차순 정렬하는 우선순위 큐를 사용
- 우선순위 큐에 들어있는 파일 개수가 1개일 경우 파일을 합칠 필요가 없기 때문에 우선순위 큐의 크기가 2개 이상일 때만 앞에 있는 요소 두 개를 꺼내서 합친 후 우선순위 큐에 집어넣는 과정을 반복해서 모든 파일을 합치는 데에 필요한 최소비용을 구함
❌ 1374번 : 강의실 (골드5)
- 문제 유형 : greedy, PriorityQueue, sort
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 강의 시작시간 기준으로 오름차순 정렬하는 우선순위 큐, 강의 종료시간 기준으로 오르마순 정렬하는 우선순위 큐를 사용
- 강의 정보들을 입력 받아 첫 번째 우선순위 큐에 집어 넣은 뒤 가장 앞에 있는 강의(시작 시간이 가장 빠른 강의)를 빼내어 두 번째 우선순위 큐에 집어 넣는다
- 이후 첫 번째 우선순위 큐가 빌 때까지 맨 앞에 있는 강의를 빼내어 두 번째 우선순위 큐 맨 앞에 있는 강의의 종료시간과 비교하여 시작시간이 앞서면 무조건 강의실이 하나 더 필요한 것이기 때문에 두 번째 우선순위 큐에 집어넣고, 시작시간이 늦으면 현재 강의실을 이어서 사용하면 되기 때문에 두 번째 우선순위 큐의 맨 앞 강의를 빼내고 현재 강의를 집어 넣음
- 위의 과정 종료 후 두 번째 우선순위 큐의 사이즈(강의 시간이 겹쳐 추가적인 강의실이 필요하여 우선순위 큐에 넣어진 강의들)가 필요한 강의실에 개수
⭕️ 1826번 : 강의실 배정 (골드5)
- 문제 유형 : greedy, PriorityQueue, sort
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 1374번 강의실과 동일한 풀이
❌ 1202번 : 보석 도둑 (골드2)
- 문제 유형 : greedy, PriorityQueue, sort
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 보석 무게를 기준으로 오름차순 정렬하는 우선순위 큐, 보석 가격을 기준으로 내림차순 정렬하는 우선순위 큐를 사용
- 가방 배열을 오름차순으로 정렬한 뒤, 배열을 순회하며 현재 가방의 용량보다 무게가 적게 나가는 모든 보석들을 우선순위 큐에서 빼내어 두 번째 우선순위 큐에 집어넣음
- 하나의 가방을 체크할 때마다 두 번째 우선순위 큐의 맨 앞의 보석이 현재 가방에 담을 수 있는 가장 비싼 보석이 되기 때문에 하나를 빼서 총 보석값에 더함
❌ 13904번 : 제출 (골드3)
- 문제 유형 : greedy, PriorityQueue
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 점수를 많이 얻을 수 있는 과제를 최대한 마감일에 맞춰서 푸는 것이 포인트
- 점수 기준으로 내림차순 정렬하는 우선순위 큐, 과제별 완료 날짜를 체크하는 boolean 배열 check을 사용
- 모든 과제를 입력받아 우선순위 큐에 집어 넣음
- 우선순위 큐에서 과제를 하나씩 빼내어 check배열을 이용해 과제의 마감일부터 시작하여 1일차까지 비어있는 날짜가 있다면 해당 날짜에 과제를 해결 (현재 점수를 많이 얻을 수 있는 과제를 최대한 마감일에 맞춰서 해결하는 과정)
- 이 풀이방법은 케이스가 적은 문제이기 때문에 가능하며 케이스가 많은 경우의 풀이법은 1781번 컵라면 참고
⭕️ 1781번 : 컵라면 (골드2)
- 문제 유형 : greedy, PriorityQueue
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 컵라면을 많이 얻을 수 있는 문제를 최대한 데드라인에 맞춰서 푸는 것이 포인트
- 데드라인 기준으로 내림차순 정렬하는 우선순위 큐, 컵라면 수 기준으로 내림차순 정렬하는 우선순위 큐를 사용
- 모든 문제를 첫 번째 우선순위 큐에 집어넣어 정렬
- 최대 시간부터 해당 시간에 할 수 있는 문제들을 첫 번째 우선순위 큐로부터 모두 빼내어 두 번째 우선순위 큐에 집어넣고, 두 번째 우선순위 큐의 맨 앞 문제를 빼내어 얻을 수 있는 컵라면을 총 컵라면 수에 더함(해당 시간에 얻을 수 있는 최고 컵라면 수)
- 위의 과정을 데드라인 1시간까지 반복하여 받을 수 있는 최대 컵라면 수 출력
⭕️ 1826번 : 연료 채우기 (골드3)
- 문제 유형 : greedy, PriorityQueue, sort
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 주유소와의 거리를 기준으로 오름차순 정렬하는 우선순위 큐, 연료량 기준으로 내림차순 정렬하는 우선순위 큐를 사용
- 주유소들을 첫 번째 우선순위 큐에 집어넣고, 현재 트럭에 있는 연료로 갈 수 있는 주유소를 우선순위 큐에서 모두 빼내어 두 번째 우선순위 큐에 집어넣음
- 두 번째 우선순위 큐에서 맨 앞의 주유소(현재 들릴 수 있는 주유소중 연료를 가장 많이 가지고 있는 곳)을 빼내어 보유 연료량에 더함
- 위의 과정을 목적지를 지나갈 때까지 반복하며 만약 목적지에 도착하지 못 했는데 진행이 불가능하면 break하고 -1 출력
- 기존 풀이 방식은 현재 갈 수 있는 주유소 중 연료가 가장 많은 주유소로 위치를 이동하면서 다음 위치로 이동을 위해 들러야 할 주유소가 현재 위치의 이전에 있는지 이후에 있는지 경우를 나누어 진행함
- 간결화 된 풀이법은 가지고 출발한 연료와 중간에 들릴 수 있는 주유소의 연료량을 합쳐서 목적지까지 갈 수 있는지만 확인하면 됨 (즉, 기준을 무조건 시작점으로 잡음)