알고리즘/탐욕법

동전의 종류와 목표금액을 입력받은 뒤 동전들을 이용하여 가장 적은 수의 동전으로 목표금액을 만드는 문제이다. 동전의 종류에 따라 무엇을 선택하는지에 따라 개수가 달라지지만, 이런 문제에는 항상 탐욕법이 정답이 되지는 않는다. 하지만, 이 예제는 그러한 상황은 배제한 문제인 것 같다. 문제 풀이는 간단하다. 목표금액과 동일하거나 넘지 않는 동전 중 가장 큰 동전을 선택하여 목표금액을 줄여 나가면 되는 문제이다. 다음은 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 ..