7. 그리디

7.1 그리디 알고리즘

• 그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

그리디 알고리즘의 핵심 이론

• 그리디 알고리즘은 다음과 같은 3단계를 반복하면서 문제를 해결한다.

그리디 알고리즘 수행 과정

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택

2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.

3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

문제 035: 동전 개수의 최솟값 구하기

풀이

import java.util.*;
import java.io.*;

public class Main {
	public static int N, result;
	public static long K, now, rest;
	public static int[] A;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Long.parseLong(st.nextToken());
		A = new int[N];
		now = 0;
		rest = K;
		result = 0;
		
		for(int i=0; i<N; i++) {
			A[i] = Integer.parseInt(br.readLine());
		}
		
		greedy(now, N-1, rest);
		
		System.out.println(result);
	}
	
	static void greedy(long now, int idx, long rest) {
		if (rest == 0) return;
		if (idx < 0) return;
		
		if (rest / A[idx] == 0) {
			while (idx >= 0 && rest / A[idx] == 0) {
				idx--;
			}
			greedy(now, idx, rest);
		} else {
			now += A[idx] * (rest / A[idx]);
			result += rest / A[idx];
			rest = rest - (A[idx] * (rest / A[idx]));
			idx--;
			greedy(now, idx, rest);
		}
	}
}

더 간단한 풀이 ••

import java.util.Scanner;

public class Main
{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 동전 "종류"의 수, 동전의 개수는 무한.
		int K = sc.nextInt(); // 만드려고 하는 동전의 가치의 합
		int[] A = new int[N]; // 각각의 동전의 가치 배열 (오름차순)
		int result = 0; // K원을 만드는데 필요한 동전 개수의 최솟값
		
		for(int i = 0; i < N; i++) {
		    A[i] = sc.nextInt();
		}
		
		for(int i = N - 1; i >= 0; i--) {
		    
		    // 현재 동전의 가치가 K보다 작거나 같으면
		    if(A[i] <= K) {
		        result += (K / A[i]);
		        K = K % A[i];
		    }
		}
		
		System.out.println(result);
		
	}
}

문제 036 : 카드 정렬하기

틀린 풀이

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		int result = 0;
		
		for(int i=0; i<N; i++) {
			num[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(num);

		if (N == 1) result = num[0];
		if (N >= 2) result = num[0] + num[1];
		if (N > 3) {
			for(int i=2; i<N; i++) {
				result = result + (result + num[i]);
			}
		}
		
		System.out.println(result);
	}
}

• 매번 가장 작은 두 묶음을 뽑아서 합치고, 그 합을 다시 묶음으로 넣어야 하는데 지금 코드는 다음에 합칠 2개를 고정해버림. → 합한 값에 따라 그때 그때 가장 작은 2개가 달라진다는 점 인지 못함

책에서의 풀이

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		for(int i=0; i<N; i++) {
			int num = Integer.parseInt(br.readLine());
			pq.add(num);
		}
		
		int data1=0;
		int data2=0;
		int sum=0;

		while(pq.size() != 1) {
			data1 = pq.remove();
			data2 = pq.remove();
			sum += data1+data2;
			pq.add(data1+data2);
		}
		
		System.out.println(sum);
	}
}

문제 037 : 수를 묶어서 최댓값 만들기

아이디어

• 수의 집합을 1보다 큰 수, 1, 0, 음수 이렇게 4가지 유형으로 나눠 저장한다.
• 1보다 큰 수의 집합을 정렬해 최댓값부터 차례대로 곱한 후에 더한다. 원소의 개수가 홀수일 때 마지막 남은 수는 그대로 더한다.
• 음수의 집합을 정렬해 최솟값부터 차례대로 곱한 후에 더한다. 원소의 개수가 홀수일 때 수열에 0이 있다면 1개 남는 음수를 0과 곱해 0을 만들고, 수열에 0이 없다면 그대로 더한다.
• 과정 2~3에서 구한 값을 더하고, 그 값에 숫자 1의 개수를 더한다.

풀이

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 수열의 크기
		
		PriorityQueue<Integer> plusPq = new PriorityQueue<>(Collections.reverseOrder());
		PriorityQueue<Integer> minusPq = new PriorityQueue<>();
		int one = 0;
		int zero = 0;
		
		for(int i=0; i<N; i++) {
			int data = Integer.parseInt(br.readLine());
			if (data > 1) {
				plusPq.add(data);
			} else if (data == 1) {
				one++;
			} else if (data == 0) {
				zero++;
			} else {
				minusPq.add(data);
			}
		}
		int sum = 0;
		
		// 양수 처리하기
		while(plusPq.size() > 1) {
			int first = plusPq.remove();
			int second = plusPq.remove();
			sum = sum + first * second;
		}
		if (!plusPq.isEmpty()) {
			sum = sum + plusPq.remove();
		}
		
		// 음수 처리하기
		while(minusPq.size() > 1) {
			int first = minusPq.remove();
			int second = minusPq.remove();
			sum = sum + first * second;
		}
		if (!minusPq.isEmpty()) {
			if (zero == 0) {
				sum = sum + minusPq.remove();
			}
		}
		
		// 1 처리하기
		sum = sum + one;
		System.out.println(sum);
	}
}

문제 038 : 회의실 배정하기

풀이

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] A = new int[N][2];
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			A[i][0] = Integer.parseInt(st.nextToken());
			A[i][1] = Integer.parseInt(st.nextToken());
		}
		 
		Arrays.sort(A, new Comparator<int[]>(){
			@Override
			public int compare(int[] S, int[] E) {
				if (S[1] == E[1]) {
					return S[0] - E[0];
					/*
						첫번째 값(index 0) 기준 오름차순
						- 음수: S가 앞
						- 0: 동일
						- 양수: E가 앞
					*/
				}
				return S[1] - E[1];
				/*
					두번째 값(index 1) 기준 오름차순
					- 음수: S가 앞
					- 0: 동일
					- 양수: E가 앞
				*/
			}
		});
		
		int count = 0;
		int end = -1;
		for (int i=0; i<N; i++) {
			if(A[i][0] >= end) { // 겹치지 않는 다음 회의가 나온 경우
				end = A[i][1]; // 종료시간 업데이트 하기
				count++;
			}
		}
		System.out.println(count);
	}
}

• 겹치지 않게 최대한 많은 회의를 배정해야 한다. → 회의의 종료시간이 빠를 수록 유리하다.
  • 종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의를 적절하게 선택하면 문제 해결
  • 종료시간이 같으면 시작 시간이 빠른 순서로 정렬하는 로직도 추가.
    • (2,2)가 먼저 등장하면, (1,2)가 불가능해지는 문제 방지

문제 039 : 최솟값을 만드는 괄호 배치 찾기

풀이

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String ex = br.readLine();
		String[] str = ex.split("-");
		int answer = 0;
		
		for(int i=0; i < str.length; i++) {
			int temp = mySum(str[i]);
			if (i==0) answer = answer + temp; // 가장 앞에 있는 값만 더함
			else answer = answer - temp; // 뒷부분은 더한 값들을 뺌
		}
		
		System.out.println(answer);
		
	}
	
	static int mySum(String a) {
		int sum = 0;
		String temp[] = a.split("[+]");
		for(int i=0; i<temp.length; i++) {
			sum += Integer.parseInt(temp[i]);
		}
		return sum;
	}
}