반응형 우선순위큐7 백준 2109번 순회강연 - C++ 풀이 1. 시간 역순으로 매일 가장 강연료를 많이 받을 수 있는 강연을 고른다. 1. 시간 역순으로 매일 가장 강연료를 많이 받을 수 있는 강연을 고른다. 1781번 컵라면 문제와 동일한 문제이다. 13904번 과제 문제와도 동일하다. 1781번 게시글에 그리디 알고리즘에 관해 그림과 함께 설명해두었으니 참고. (강연료 = 컵라면이라고 생각하면 된다.) 백준 1781번 컵라면 - C++(cpp) 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있 please-amend.tistory.com #include #include #include usi.. 2022. 8. 24. 백준 13904번 과제 - C++ 풀이 1. 시간 역순으로 매일 가장 점수를 많이 받을 수 있는 과제를 고른다. 1. 시간 역순으로 매일 가장 점수를 많이 받을 수 있는 과제를 고른다. 1781번 컵라면 문제와 동일한 문제이다. 1781번 게시글에 그리디 알고리즘에 관해 그림과 함께 설명해두었으니 참고. (점수=컵라면이라고 생각하면 된다.) 백준 1781번 컵라면 - C++(cpp) 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있 please-amend.tistory.com #include #include using namespace std; typedef pair pii;.. 2022. 8. 22. 백준 1781번 컵라면 - C++ 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있는 문제는 데드라인이 day 이상인 문제들이다. 따라서 N일에 풀 수 있는 문제는 데드라인이 N인 문제들 밖에 없으므로, 그 중에서 가장 컵라면을 많이 주는 문제를 골라야 한다. (N-1)일에는 데드라인이 (N-1)일이거나 N일인 문제들을 풀 수 있다. 데드라인이 N일인 문제 중 가장 많은 컵라면을 주는 문제는 N일에 풀어야 하기 때문에, 이제 그 문제를 제외한 문제들 중에서 가장 많은 컵라면을 주는 문제를 고르면 된다. 같은 방식으로 N-2, N-3, ..., 1일까지 계속해서 가능한 문제 중 가장 많은 컵.. 2022. 7. 7. 백준 1655번 가운데를 말해요 - C++(cpp) 풀이 1. 새 수가 들어오면, 이전 중간값보다 작거나 같다면 최대우선순위큐에, 크다면 최소우선순위큐에 넣는다. 2. 최대우선순위큐에 담긴 수의 개수를 절반으로 유지시킨다. 3. 최대우선순위큐의 top을 출력한다. 1. 새 수가 들어오면, 이전 중간값보다 작거나 같다면 최대우선순위큐에, 크다면 최소우선순위큐에 넣는다. 현재까지 입력받은 수들을 오름차순 정렬했을 때 왼쪽 절반을 최대 우선순위큐에, 오른쪽 절반을 최소 우선순위큐에 보관하는 방식을 사용할 것이다. 그리고 최대 우선순위큐(작은 수들이 담긴 큐)에 담긴 숫자의 수는 항상 전체 개수의 절반으로 유지할 것이다. 이렇게 되면 항상 최대 우선순위큐의 top이 중간값이 된다. 새로 들어온 수가 왼쪽 절반에 속한다면, 즉 중간값(최대 우선순위큐의 top)보다 작거.. 2022. 2. 14. 백준 1766번 문제집 - C++(cpp) 풀이 1. 각 문제를 그래프의 정점으로 생각한다. 2. A번 문제를 B번 문제보다 먼저 푸는 것이 좋다면 A에서 B로 가는 방향 간선을 추가한다. 3. 우선순위 큐를 가지고 위상 정렬한다. 1. 각 문제를 그래프의 정점으로 생각한다. 선행 관계가 주어진 작업들의 작업 순서를 결정하는 것은 위상 정렬로 풀 수 있다. 먼저 주어진 상황을 그래프로 변환해야 한다. 각 문제를 정점으로 생각해준다. 2. A번 문제를 B번 문제보다 먼저 푸는 것이 좋다면 A에서 B로 가는 방향 간선을 추가한다. 그리고 A가 B보다 선행되어야 한다면, A에서 B로 가는 방향 간선을 추가한다. 3. 우선순위 큐를 가지고 위상 정렬한다. 완성된 그래프를 가지고 위상 정렬을 수행한다. 그런데 "가능하면 쉬운 문제부터 풀어야 한다."는 조건을 .. 2022. 2. 4. 이전 1 2 다음 반응형
