탐욕법

문제 설명민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.오민식의 사원 번호..

. 문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발..

탐욕 법을 이용하여 풀이해야 하는 문제이다. 최대한 많이 회의실을 사용해야 하기 때문에 종료시간이 빠른 일정을 처리하는 게 유리하다. 그렇기 때문에, 입력을 종료시간을 우선으로 정렬하되 만약 종료시간이 같다면 시작시간이 이른 일정을 우선으로 정렬한다. 그 후, 차례로 비교해가며 종료시간이 가장 빠른 일정을 우선으로 처리하면서, 그 일정의 종료시간보다 크거나 같은 일정을 다음 일정으로 처리하며 나가면 된다. 다음은 Java로 작성한 코드이다. import java.util.PriorityQueue; import java.util.Scanner; public class MeetingRoom { public static void main(String[] args) { //Pair class 정의 class P..

동전의 종류와 목표금액을 입력받은 뒤 동전들을 이용하여 가장 적은 수의 동전으로 목표금액을 만드는 문제이다. 동전의 종류에 따라 무엇을 선택하는지에 따라 개수가 달라지지만, 이런 문제에는 항상 탐욕법이 정답이 되지는 않는다. 하지만, 이 예제는 그러한 상황은 배제한 문제인 것 같다. 문제 풀이는 간단하다. 목표금액과 동일하거나 넘지 않는 동전 중 가장 큰 동전을 선택하여 목표금액을 줄여 나가면 되는 문제이다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class Coin { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int count = 0; int n ..

대기 인원을 입력받고 각 인원들의 대기 시간을 최소한으로 만드는 문제이다. 생각해보면 간단한 문제이다. 대기시간의 합을 최소한으로 만들기 위해서는 자신의 앞사람들의 인출하는데 필요한 시간이 적게 만들면 된다. 즉, 시간이 적게 걸리는 사람들을 우선으로 처리하면 된다. 운영체제에서 배웠던 스케줄링 방식 중, SJF(Shortest Job First)방식을 떠올릴 수 있다. 입력을 받을 때, 우선순위 큐를 이용하여 저장한 뒤 하나씩 out 시키며 배열에 저장한다. 그러면 시간이 적은 순서대로 배열에 저장 할 수 있다. 그 후, 마지막 요소부터 자신 전까지의 요소를 모두 더해나가면 답을 구해낼 수 있다. 다음은 Java로 작성한 코드이다. import java.util.PriorityQueue; import ..

동적 계획법이란? 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 하위 문제의 해결책이 다른 하위 문제의 해결책과 같은 경우 유용하다. 탐욕 알고리즘과의 비교 탐욕 알고리즘은 문제가 발생하면 그 상황에서의 최적의 해를 선택하는 방식의 알고리즘을 말한다. 순간적으로 볼 때는 최적의 해를 반환하지만 전체적으로 보았을 때 그렇지만은 않은 상황이 존재한다. 예를 들어, 길을 찾는 문제가 주어졌다면 출발지부터 목적지까지 가는 중, 갈림길과 마주했을 때 그 순간 가장 짧은 길로 가는 것이다. 하지만 동적 계획법은 모든 갈림길을 살펴본 후 최적의 길을 탐색하게 된다. 동적 계획법은 모든 경우의 수를 살펴봐야 하기 때문에 시작시 조금의 시간이 걸릴..