그리디 알고리즘

문제: 신입 사원(백준 1946번)문제 분석이 코드는 신입 사원 선발 문제를 해결하기 위한 코드다.주어진 t개의 테스트 케이스에 대해 각 지원자의 서류 성적과 면접 성적이 주어진다.이 중 두 성적 중 하나라도 다른 지원자보다 나은 경우에만 선발한다.즉, 어떤 지원자가 다른 지원자들에 의해 완전히 밀리지 않는 경우를 찾는 문제다.알고리즘 설명입력받기각 테스트 케이스마다 n명의 지원자 정보(서류 성적, 면접 성적)를 입력받는다.정렬서류 성적 기준으로 오름차순 정렬한다.이로 인해 서류 성적이 앞서는 지원자만 비교하면 된다.최소 면접 성적 추적서류 성적이 낮은 순서로 순회하면서,이전까지의 최소 면접 성적(minVal)보다 현재 지원자의 면접 성적이 더 낮다면,해당 지원자는 선발 가능하다. 이 경우, answer..

문제: 보석 도둑 (백준 1202번)문제 분석이 문제는 풀이법이 바로 떠오른다면 쉽게 해결할 수 있지만, 그렇지 않다면 접근법을 찾기 어려운 웰메이드 문제이다.알고리즘 자체는 복잡하지 않으나, 핵심 아이디어를 도출하는 것이 도전 과제다.핵심 아이디어정렬가방과 보석을 무게 순으로 오름차순 정렬한다.작은 가방부터 차례로 탐색하며 해당 가방에 들어갈 수 있는 보석들을 선택한다.우선순위 큐현재 가방에 들어갈 수 있는 보석들을 모두 우선순위 큐에 삽입한다.이때, 우선순위 큐는 보석의 가치를 기준으로 내림차순 정렬되도록 설정한다.우선순위 큐의 맨 앞에 있는 보석은 현재 가방이 담을 수 있는 최고 가치의 보석이다.탐욕적 선택작은 가방부터 순서대로 처리하며, 현재 가방이 담을 수 있는 최고 가치의 보석을 선택한다.이를..