[Do it! 알고리즘 코딩테스트 - 자바 편] 07. 그리디

07. 그리디

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

 

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

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

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

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

---

[11047번: 동전 0] / 실4

동전을 최소로 사용해 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.

import java.util.Scanner;

public class Main {
    public static void solution() throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int count = 0;
        int[] coins = new int[n];

        for (int i = 0; i < n; i++) {
            coins[i] = sc.nextInt();
        }
        for (int i = n - 1; i >= 0; i--) {
            if (k == 0)
                break;
            count += k / coins[i];
            k %= coins[i];
        }
        System.out.print(count);
    }

    public static void main(String[] args) throws Exception {
        solution();
    }
}

 

 

[1715번: 카드 정렬하기] / 골5

카드 묶음의 카드의 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법이다.

현재 데이터 중 가장 작은 카드의 개수를 가진 묶음 2개를 뽑아야 하고, 이 2개를 기준으로 합친 새로운 카드 묶음을 다시 데이터에 넣고 정렬해야 한다. -> 데이터의 삽입 삭제 정렬이 자주 일어남 -> 우선순위 큐를 이용.

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

public class Main {
    public static void main(String[] args) throws Exception {
        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++) {
            pq.add(Integer.parseInt(br.readLine()));
        }
        int sum=0;
        while(pq.size() >= 2){
            int a = pq.poll();
            int b = pq.poll();
            pq.add(a+b);
            sum += (a+b);
        }
        System.out.println(sum);
    }
}

 

 

[1744번: 수 묶기]

절댓값이 큰 것들부터 서로 곱해야 결과값이 커지고, 음수의 갯수가 홀수 개일 때 0이 있다면 곱해서 없애주어야 한다.

양수/음수 큐를 따로 만들어야 했는데 이 부분을 놓쳤다..!

=> 음수를 오름차순으로 양수를 내림차순으로 정렬하는 큐에 넣은 뒤 절댓값이 큰 것부터 소모시키기. 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> plus = new PriorityQueue<>(Collections.reverseOrder()); // 양수는 내림차순 정렬
        PriorityQueue<Integer> minus = new PriorityQueue<>(); // 음수는 오름차순 정렬
        int oneCount = 0;
        int zeroCount = 0;
        int result = 0;

        for (int i = 0; i < n; i++) {
            int k = Integer.parseInt(br.readLine());
            if (k > 1) plus.add(k);
            else if (k == 1) oneCount++;
            else if (k == 0) zeroCount++;
            else minus.add(k);
        }
        
        // 양수 처리 (내림차순)
        while (plus.size() > 1) {
            int a = plus.poll();
            int b = plus.poll();
            result += a * b;
        }
        if (!plus.isEmpty())
            result += plus.poll();

        // 음수 처리 (오름차순)
        while (minus.size() > 1) {
            int a = minus.poll();
            int b = minus.poll();
            result += a * b;
        }
        if (!minus.isEmpty()) { // 음수 하나 남은 경우
            if (zeroCount == 0)
                result += minus.poll(); // 0 없으면 더함
        }

        // 1은 전부 더하기
        result += oneCount;

        System.out.println(result);
    }
}

 

 

[1931번: 회의실 배정] / 골5

정렬을 사용해, 무조건 빨리 끝나는 회의를 선택하는 것이 이득이다.

https://hereishyun.tistory.com/209

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[][] meetings = new int[n][2];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            meetings[i][0] = Integer.parseInt(st.nextToken());
            meetings[i][1] = Integer.parseInt(st.nextToken());
        }
        // 끝나는 시간이 작은 것부터 오름차순 정렬
        Arrays.sort(meetings, (a, b) -> {
            if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
            return Integer.compare(a[0], b[0]);
        });
        
        int count = 0, prevEnd = 0;
        for (int i=0; i<meetings.length; i++) {
            if (meetings[i][0] >= prevEnd) {
                prevEnd = meetings[i][1];
                count++;
            }
        }
        System.out.println(count);
    }
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}
}

 

[1541번: 잃어버린 괄호] / 실2

괄호를 적절히 쳐서 식의 값을 최소로 만드려 한다.

-를 기준으로 식을 분리(->그룹), 첫번째 그룹(숫자합)을 구하고 나머지 그룹(숫자합)들을 뺀다.

 

Python

expr = input().strip()

parts = expr.split('-')

initial = sum(map(int, parts[0].split('+')))

rest = 0
for part in parts[1:]:
    rest += sum(map(int, part.split('+')))

print(initial - rest)

 

Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String expr = br.readLine();
        String[] minusSplit = expr.split("-");
        int result = 0;
        for (int i = 0; i < minusSplit.length; i++) {
            int groupSum = 0;
            // '+'로 나눈 부분을 모두 더하기
            String[] plusSplit = minusSplit[i].split("\\+");
            for (String num : plusSplit) {
                groupSum += Integer.parseInt(num);
            }
            // 첫 그룹은 더하고, 이후 그룹들은 모두 빼기
            if (i == 0) result = groupSum;
            else result -= groupSum;
        }

        System.out.println(result);
    }
}