4th Meet - 코독하구만

Daily Object

    - Greedy 알고리즘을 복습하고 예제를 통해 적용한다.

Review

    - 코드 시간복잡도를 줄이느라 애썼다. 코드의 간결화도 노력이 필요하다. 

 

Greedy Algorithm

     매 순간마다 최적의 해를 찾아 진행하는 알고리즘

         -> 전체적인 문제로 보았을 때 최적의 답이 아닐 수 있다.

 

 

이번 시간에 풀어본 예제

 

11000번: 강의실 배정

 

처음 생각한 풀이방법 

 

  1 ) N개의 수업 시작과 종료시각을 2차원 배열 time[][]에 저장

  2 ) 단순화하기위해 time을 시작시각을 기준으로 오름차순으로 정렬

  3 ) Worst Case인 N개의 강의실의 종료시각을 endtime[]을 배열로 생성

  4 ) 사용중인 강의실을 비교하며 넣을 공간이 있으면 추가배정하고, 없다면 새로운 강의실에 배정

  -> 시간초과로 오답처리

    Solution

        사용가능한 강의실을 찾을 때 시간복잡도를 줄여야함

 

다시 생각한 풀이방법

 

  1 ) N개의 수업 시작과 종료시각을 2차원 배열 time[][]에 저장

  2 ) 단순화하기위해 time을 시작시각을 기준으로 오름차순으로 정렬

  3 ) 우선순위큐를 생성 -> 종료시각을 기준으로 정렬 ( 큐 = 사용될 강의실 )

  4 ) 모든 강의를 비교하며 같은 강의실에

           추가가 가능하면 큐의 top을 제거하고 새로운 종료시각을 offer하여 추가

           불가능하면 종료시각을 offer하여 추가 ( 새로운 강의실 )

  5 ) 모든 강의를 비교했다면 , 큐의 size를 출력하여 사용될 강의실 개수를 출력한다.

 

백준 11000 - 강의실 배정

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	private static Scanner sc;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		sc = new Scanner(System.in);
		int N = sc.nextInt();
		int time[][] = new int[N][2];
		for (int i = 0; i < N; i++) {
			time[i][0] = sc.nextInt(); // start
			time[i][1] = sc.nextInt(); // end
		}
		Arrays.sort(time, new Comparator<int[]>() { // 시작시각 오름차순 정렬

			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0]) {
					return o1[1] - o2[1];
				} else {
					return o1[0] - o2[0];
				}
			}

		});

		PriorityQueue<Integer> q = new PriorityQueue<Integer>();

		for (int i = 0; i < N; i++) {
			int end = time[i][1];
			if (!q.isEmpty() && q.peek() <= time[i][0]) // 연강 가능
				q.poll(); // 강의정보 삭제
			q.offer(end); // 종료시각 업뎃
		}
		System.out.println(q.size());
	}
}

 

 

 

 

11047번: 동전 0

 

처음 생각한 풀이방법 

 

  1 ) 입력 N 개의 동전 금액을 1차원 배열에 저장한다.

  2 ) 큰 금액부터 맞춰야할 금액과 비교한다.

         작다 -> 금액을 깔 수 있다. -> 맞춰야할 금액을 감산하고 출력 동전 개수를 +1 한다.

         크다 -> 금액을 깔 수 없다. -> 다음 동전으로 Pass

  3 ) 모든 동전에 대해 비교를 마치면 동전의 개수를 출력하고 종료한다.

 

     -> 문제점 : 주어지는 동전이 1, 5, 10, 50, 100 ... 과 같이 최소값이 1이라면 어떠한 금액이 오더라도 맞출 수 있다.

                     그렇지 않을 경우 금액을 못 맞출 수 도 있다.   

               -> 위 알고리즘으로 통과한 것을 보니 해당 문제에서 주어진 동전 금액은 고정되어있는 듯 하다.

 

 

백준 11047 - 동전 0

import java.util.Scanner;

public class Main {
	private static Scanner sc;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		sc = new Scanner(System.in);
		int N = sc.nextInt(); // 주어진 동전 개수
		int K = sc.nextInt(); // 맞출 금액
		int needs = 0; // 필요 동전 개수
		int value[] = new int[N]; // 동전 금액을 저장할 배열
		for (int i = 0; i < N; i++) { 
			value[i] = sc.nextInt(); // 입력
		}

		for (int i = N-1; i >= 0; i--) { // 큰 금액부터
			int coin = value[i];
			while (coin <= K) { // K보다 작다면
				K = K - coin; // K는 coin을 감산
				needs++; // 동전 개수 + 1
			}
		}
		System.out.println(needs); // 출력
	}
}