섹션 2. 코딩테스트 - 06. 그리디 알고리즘

섹션 2. 코딩테스트 - 06. 그리디

⬛ 06. 그리디 알고리즘

⬛ 06-1. 그리디 알고리즘

🟦 그리디(Greedy) 알고리즘

• 현재 상태에서 볼 수 있는 최적해가 전체의 최적해라고 가정하며 근시안적으로 보는 알고리즘
• 전체를 보지 않고, 근시안적 선택(현 상황에서의 부분적 최적해)가 최종 문제의 최적해를 얻는 일이라고 가정하며 답을 찾아가는 알고리즘
• 항상 최적해를 보장하지는 못한다.

🟧 그리디 알고리즘 수행 과정

1) 해 선택 : 현재 상태의 부분적 최적해 선택

2) 적절성 검사 : 그 최적해가 전체 문제 제약 조건 벗어나지 않는지 검사

3) 해 검사 : 현재까지 선택한 해 집합들이 전체 문제 해결 가능한지 검사.

• 만약 전체 문제 해결 못한다면 다시 1)로 돌아가 이 과정을 반복

---

🟦 백준 11047번. 동전 개수의 최솟값 구하기

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

풀이 - 그리디 알고리즘

• 어쨋든 최소 동전 개수로 K원을 만드는 게 목표이다 보니, 큰 동전부터 역순으로 확인해야 한다.
• 1) K보다 작거나 같은 동전 값 발견 시,
• 2) K /arr[i] 해당 동전으로 나눈 ‘몫’은 동전개수++ 누적시키고
• 3) K % arr[i] 해당 동전 나누고 남은 ‘나머지’ 금액은 K원 갱신시키고
• 4) 반복하고 탈출한 동전개수를 최종 출력시킨다.

package to_0614_1;

import java.util.Scanner;

/* 11047번. 동저 개수 최솟값 - 그리디 알고리즘 
 * */
public class Main {

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb =new Scanner(System.in);

        int N = kb.nextInt();//동전 개수
        int K = kb.nextInt(); //목표 금액 

        int arr[] = new int[N];//동전 묶음
        //입력 받기 
        for(int i=0; i<N; i++) arr[i] = kb.nextInt();

        int answer = 0;//최소 동전 개수 저장용 
        //그리디 알고리즘 
        //일단 최소 동전 쓰려면 역순 큰 값부터 대조
        for(int i=N-1; i>=0; i--) {
            if(arr[i] <= K) { // 각 동전값이 K보다 작거나 같다 == 만들 수 있다이므로 
                answer += K/arr[i];//그 나눈 몫은 동전 개수로 누적
                K = K%arr[i];//나머지는 K값으로 갱신 처리 
            }
        }
        //정답 출력 
        System.out.println(answer);
    }
}

---

🟦 백준 1715번. 카드 정렬하기

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

풀이 - 그리디 알고리즘

• 카드 묶음의 카드 개수가 ‘작은 순서대로’ 먼저 합치는 것이 전체 비교횟수를 줄일 수 있는 방법이다.
• 따라서 그리디로 풀려면, 현재 데이터 중 가장 작은 카드 개수 묶음 2개를 뽑고, 그 2개를 합친 새 카드 묶음을 다시 데이터에 넣은 뒤 정렬시키는 과정을 반복해야 한다.
• ‘우선순위 큐’도 사용해야 한다.
• while(pq.size()≠1) ,즉. 우선순위 큐 사이즈 1이 아닌 동안 반복하는 이유는 : 두 개 카드 묶음끼리 비교하는 건데 1개가 됐다는 것은 더 이상 비교할 카드 없다는 뜻이므로.

import java.util.PriorityQueue;
import java.util.Scanner;

/* 1715번. 카드 정렬하기 */
public class Main {
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb= new Scanner(System.in);

        int N = kb.nextInt();//최초 카드 묶음의 개수
        //데이터값 자동 오름차순 정렬될 우선순위 큐에 값 저장시킬 것 
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0; i<N; i++) {
            int data = kb.nextInt();
            pq.add(data);
        }        
        int sum = 0;//비교 횟수 합 더할 것 
        while(pq.size()!=1) { //내부 카드묶음 1개 되면 더이상 비교 불가하므로
            int a = pq.poll();//첫 데이터 뽑고
            int b = pq.poll();//다음 데이터 뽑고 
            sum += a+b;//두 데이터 묶음을 sum에 누적 
            //합친 카드묶음은 새 데이터로 우선순위큐에 저장
            pq.add(a+b);
        }
        //탈출한 sum 이 최종 답
        System.out.println(sum);
    }
}

---

⬛ 우선순위 큐 | Priority Queue

• 큐(Queue)는 FIFO 의 형태로 데이터를 처리한다.
• Priority Queue 는 우선순위를 먼저 결정한 뒤, 그 우선순위가 높은 요소부터 먼저 나가는 자료구조이다.
• 기본적으로 오름차순 (작은→큰) 값의 순서로 우선순위 배정된다.

import java.util.PriorityQueue;//import//int형 priorityQueue 선언 (우선순위가 내부 값 오름차순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 내부 값 내림차순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (우선순위가 내부 값 오름차순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>();

//String형 priorityQueue 선언 (우선순위가 내부 값 내림차순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

---

🟦 백준 1744번. 수 묶어서 최대 만들기

문제

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(23)+(45) = 27이 되어 최대가 된다. (== 묶는 순서에 따라서 결과가 달라진다.)

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

풀이 - 그리디 알고리즘

양수의 경우 가능한 큰 수들끼리 우선적으로 묶어야 결과값이 커진다는 것.

음수 간의 곱은 양수가 되므로 (음수는 작은값 우선으로 묶어야) 결과값이 커진다는 것을 이용하여 풀어야 한다.

일단 이 문제는 수의 유형을 4가지로 분리해서 저장해야 힘

1) 1보다 큰 양의 정수 : PQ에 큰 값 우선(내림차순) 정렬

2) 음의 정수 : PQ에 작은값 우선(오름차순) 정렬,

3) 0과 1은 카운팅

그리고, while()문으로 pQ사이즈가 1보다 클때까지 두 개의 수를 뽑아 곱해서 sum에 누적하되, 만약 크기 1이 되어 탈출했다면(즉, 그 개수가 홀수개 였다면).

(1) 양수는 isEmpty() 될때까지 sum에 누적하면 되고

(2) 음수는

1) 0 카운팅이 존재하면. 남은 음수와 0을 곱한 값을, 어차피 0 더하니 0 카운팅이 존재하지 않을 경우만 생각하면 된다.

2) 0카운팅이 존재하지 않으면 그냥 남은 음수를 sum에 누적시킨다.

마지막에는 one 카운팅한 값을 그대로 sum에 더하고 출력한다.

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

/*1744번. 수 묶어서 최대 만들기 */
public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);

        int N = kb.nextInt();
        //유형별 수 나눔
        //양수는 큰수 우선 -> 역순(내림차순)
        PriorityQueue<Integer> plusQ = new PriorityQueue<>(Collections.reverseOrder());
        //음수는 작은 수 우선 -> 더 작은 수 끼리 곱이 더 크므로 (오름차순)
        PriorityQueue<Integer> minusQ = new PriorityQueue<>();

        //0과 1은 카운팅
        int zero =0;
        int one =0;

        //입력 받기 
        for(int i=0; i<N; i++) {
            int input = kb.nextInt();
            if(input == 1) one++;
            else if(input ==0) zero++;
            else if(input > 1) plusQ.add(input);
            else if(input <0) minusQ.add(input);
        }

        int sum = 0;//얘가 최대가 되어야 함
        //1) 양수들은 최댓값 우선 뽑아서 곱한 뒤 해결 

        while(plusQ.size() > 1) { //짝수이면 지들끼리 곱한 뒤 합하면 됨
            int a = plusQ.poll();
            int b = plusQ.poll();
            sum += (a*b);
        }
        //만약 홀수개라 마지막에 1개 남은 경우 
        if(!plusQ.isEmpty()) {
            int x = plusQ.poll();
            sum += x;
        }

        //2) 음수 처리 
        while(minusQ.size() > 1 ) {
            int a = minusQ.poll();
            int b = minusQ.poll();
            sum += (a*b);
        }
        if(!minusQ.isEmpty()) {
            int x = minusQ.poll();
            if(zero >= 1) {
                sum += (0 * x);
                zero--;
            }else {
                sum += x;
            }
        }
        //3) 남은 1 처리 
        sum += one;

        //최종 최댓값 출력 
        System.out.println(sum);
    }
}

---

🟦 백준 1931번. 회의실 배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

풀이 1) - 그리디 알고리즘 & Time 클래스 생성

• 1개의 회의실에 회의가 겹치지 않게 최대한 많은 회의를 배정해야 하는 문제이다.
• 현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는 게 유리하다.
• 그러므로 종료 시간 빠른 순으로 우선 정렬하고, 만약 종료시간이 같은 회의의 경우 시작 시간 빠른 것 우선으로 정렬하도록 조건을 설정한다.
• 그런 뒤, 차례로 순회하면서 현재 회의 종료시간과 같거나 큰 시작 시간 발견 시 카운팅++ 후, 종료 시간을 해당 회의의 종료 시간으로 갱신처리한다.

---

🏓첫 번째 풀이는 Comparable

을 implements한 Time 클래스를 새롭게 정의한 뒤, 정렬 조건을 내부의 compareTo() 메소드에 재정의하여 푸는 방식이다.

package to_0614_4;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/* 1931번. 회의실 배정하기 */
class Time implements Comparable<Time>{
    int s; //시작 시간 
    int e; //끝 시간 
    Time(int s, int e ){
        this.s = s;
        this.e = e;
    }
    @Override
    public int compareTo(Time o) {
        // TODO Auto-generated method stub
        if(this.e == o.e){//만약 종료시간이 두 객체 모두 같다면.
            return this.s - o.s;//빠른 시작 시간 우선 
        }
        return this.e - o.e; //기본적으로 빠르종료 시간 우선 정렬 
    }
}
public class Main {
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);
        int N = kb.nextInt(); //회의실 개수 
        ArrayList<Time> arr = new ArrayList<>();

        for(int i=0; i<N; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            arr.add(new Time(a, b)); //객체에 담고 
        }
        int cnt =0;
        //재정의한 기준으로 정렬
        Collections.sort(arr);
        //기본 종료 시간은 0 으로 세팅해놓고 
        int et = 0;

        for(Time x : arr) {
            if(x.s >= et) { //종료시간 기준 정렬된 상태에서 가장 먼저 나타난 시작시간 회의를 발견시 
                cnt++;//회의 배정++
                et = x.e;//현재 선택한 회의의 종료시간으로 et를 갱신
            }        
        }
        System.out.println(cnt);        
    }
}

---

🏓두 번째 풀이는 2차원 배열을 활용하여 정렬하는 방식이다.

- int[][]A = new int[N][2] ;에 저장한 다음, A[i][0]은 시작, A[i][1]은 종료 시간을 담아둔다.

    Arras.sort(A, new Comparator<int[]>() {

            @override 

            public int compare(int[] A, int[] B){

            //만약 종료 시간이 같을 경우 , 시작시간 오름차순 정렬 

               if(A[1] == B[1] ) return A[0] - B[0];

               return A[1]-B[1]; //기본  종료 시간 빠른 순 정렬 오름차순  

            }
    });

풀이 2) - 그리디 알고리즘 & 2차원 배열

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

/*1931번. 회의실 배정 */
public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb= new Scanner(System.in);
        int N = kb.nextInt();
        int[][] A = new int[N][2];
        //입력받고
        for(int i=0; i<N; i++) {
            int s = kb.nextInt();
            int e = kb.nextInt();
            A[i][0] = s; //시작
            A[i][1] = e; //종료 
        }
        //정렬
        Arrays.sort(A, new Comparator <int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // TODO Auto-generated method stub
                if(o1[1] == o2[1]) {//종료시간 같다면 
                    return o1[0] - o2[0];//시작 시간 빠르 순 
                }
                //기본적으로 종료시간 우선 정렬
                return o1[1] - o2[1];
            }
        });

        int et = 0;
        int cnt = 0;//카운팅 

        for(int i=0; i<N; i++) {
            if(et <= A[i][0]) {
                //현재 종료시간 보다 크거나 같은 시작시간 회의 발견ㅅ ㅣ
                cnt++;
                et = A[i][1];//종료시간을 해당 회의의 종료시간으로 갱신 
            }
        }        
        System.out.println(cnt);
    }
}

---

🟦 백준 1541번. 잃어버린 괄호

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. (== 묶는 순서에 따라서 결과가 달라진다.)

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

풀이 - 그리디 알고리즘

• 가장 작은 최솟값을 만들려면 가능한 큰 수를 빼야한다.
• (-) 를 기준으로 분리해서 괄호로 합친 각자 값들을 모두 더한 뒤, 빼기를 실행하면 최솟값이 만들어진다.
• ex) 100 - (40+50) - (31+32+90)

package to_0614_6;

import java.util.Scanner;

public class Main {

    static int mySum(String x) {
        int sum = 0;
        for(String a : x.split("[+]")) {
            sum += Integer.parseInt(a);
        }
        return sum;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb =new Scanner(System.in);

        String x = kb.next();
        //- 기준으로 구분해놓고 
        String[] sArr = x.split("-");
        int sum =0;
        for(int i=0; i<sArr.length; i++) {
            int tmp = mySum(sArr[i]);
            if(i ==0) {
                sum += tmp;
            }else {
                sum -= tmp;
            }
        }

        System.out.println(sum);
    }
}