[이것이 취업을 위한 코딩 테스트다] Ch03. 그리디 알고리즘 자바

그리디 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 

특정한 문제를 만났을때 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀수 있는지를 파악할 수 있어야함.
그리디 알고리즘은 문제에서 '가장 큰 순서대로' '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해줌. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬수 있으므로 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됨.

예제 3-1) 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정. 손님에게 거슬러 줘야 할 돈이 n원일때 거슬러줘야 하는 돈전의 최소 개수를 구하라.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 예제31 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n  = Integer.parseInt(br.readLine());
        int ans =0;
        ans += n/500;
        n = n%500;
        ans+= n/100;
        n= n%100;
        ans += n/50;
        n = n%50;
        ans += n/10;

        System.out.println(ans);
    }
}

 

예제 2 큰 수의 법칙) 다양한 수로 이뤄진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙. 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 구할수 있는 큰 수 결과를 출력하라.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;

public class 큰수의법칙 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        int k = Integer.parseInt(s[2]);
        String[] str = br.readLine().split(" ");
        int[] arr = new int[n];

        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(str[i]);
        }
        Arrays.sort(arr);
        int biggest1 = arr[n-1];
        int biggest2 = arr[n-2];

        int c = m/(k+1)*k;
        c+=m%(k+1);

        int ans = c*biggest1;
        ans+=(m-c)*biggest2;

        System.out.println(ans);
    }
}

 

예시 3 숫자 카드 게임)  숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.
단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.
1. 숫자가 쓰인 카드들이 N × M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class 숫자카드게임 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int y = Integer.parseInt(br.readLine());
        int x = Integer.parseInt(br.readLine());
        int map[][] = new int[y][x];
        int biggest = 0;
        for(int i=0;i<y;i++){
            String s = br.readLine();
            int smallest = 987654321;
            for(int j=0;j<x;j++){
                map[i][j] = s.charAt(x)-'0';
                if(map[i][j]<smallest) smallest = map[i][j];
            }
            if(biggest<smallest) biggest = smallest;
        }
        System.out.println(biggest);
    }
}