[이것이 코딩 테스트다 with Java] 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘(Greedy Algorithm)

 

개요

greedy
형용사 - 1. 탐욕스러운 2.욕심 많은 

사전 상 Greedy는 위와 같은 의미를 가지고 있는 영어 단어이다. 그렇다면 그리디 알고리즘은 무엇일까?
국내에서 탐욕법, 욕심쟁이 알고리즘이라고도 부르는 그리디 알고리즘은 이름에서 유출할 수 있듯이 어떤 문제에 대해서 탐욕적으로 즉 "현재 상황에서 지금 당장 좋은 것만 고르는 방법"으로 문제를 해결하는 방법이다. 

•  코딩테스트에서 만날 경우 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형
  다익스트라 알고리즘의 경우 그리디 알고리즘이지만 암기가 필요한 유형
  문제 출제 유형의 폭이 넓기 때문에 특이 케이스를 제외하고는 단수 암기를 통해 모든 문제를 대체하긴 어려움
• 창의력(문제를 풀기 위한 최소한의 아이디어)을 요구하는 문제 유형
• 대표적인 알고리즘으로는 " 거스름돈" 문제가 있음

 

예제 1 - 거스름돈

마트에서 계산을 하는 점원이 되었다. 
손님에게 거슬러줘야할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 이때 
거스름돈으로 사용할 동전은 500원, 100원, 50원, 10원으로 무한히 존재하고, N은 10의 배수로 가정

 

입력/출력 예시

입력 예시	출력 예시
1,460	8
1,890	11

 

요점

• 최소 개수를 구하기 위해서는 "가장 큰 화폐 단위부터" 돈을 거슬러 준다

 

소스코드

import java.util.Scanner;

public class Main
{
	public static void main(String[] args) {
	    Scanner scan = new Scanner(System.in);
	    int total = scan.nextInt();
	    int minCoinCnt = 0;
	    int coins[] = {500, 100, 50, 10};
	    
	    for (int coin : coins){
	        minCoinCnt += (total/coin);
	        total %= coin;
	    }
		
		System.out.println("result = " + minCoinCnt);
	}
}

 

예제 2 - 큰 수의 법칙

난이도 ●○○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB | 기출 2019 국가 교육기관 코딩 테스트

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 큰 수의 법칙에 따른 결과를 출력하시오.

 

입력 조건

• 첫째 줄에 N(2 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다.각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

출력 조건

• 첫째 줄에 큰 수의 법칙에 따라 더해진 답을 출력한다.

 

입력/출력 예시

입력 예시	출력 예시
5 8 3 2 4 5 4 6	46
5 7 2 3 4 3 4 3	28

요점

• 가장 큰 수와 두 번째로 큰 수를 구해 조건에 맞게 배치한다.
• 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 패턴을 반복한다.

 

소스 코드

import java.util.*;

public class Main
{
	public static void main(String[] args) {
	    Scanner scan = new Scanner(System.in);
	    
	    // 조건 값들 입력 받기
	    int n = scan.nextInt();
	    int m = scan.nextInt();
	    int k = scan.nextInt();
	    int numArr[] = new int[n];
	 
	    for(int i = 0; i < n; i++){
	        numArr[i] = scan.nextInt();
	    }
	    
	    // 배열 내림차순 정렬
	    numArr = Arrays.stream(numArr)
                	    .boxed()
                	    .sorted(Comparator.reverseOrder())
                	    .mapToInt(i -> i)
                	    .toArray();
	    
	    //첫번재 값이 더해지는 횟수 계산
	    int first = (m / (k+1) * k) + (m % (k+1));
	    int second = m - first;
	    int result = (numArr[0] * first) + (numArr[1] * second);
	 
        System.out.println("result =" + result);
	}
}

 

예제 3 - 숫자 카드 게임

난이도 ●○○ | 시간 제한 1초 | 메모리 제한 128MB | 기출 2019 국가 교육기관 코딩 테스트

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

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

카드들이 N X M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

 

입력 조건

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 ≤ N, M ≤ 100)
• 둘째 줄에 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

 

출력 조건

•  첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

 

입력/출력 예시

입력 예시	출력 예시
3 3 3 1 2 4 1 4 2 2 2	2
2 4 7 3 1 8 3 3 3 4	3

 

요점

• 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는다.

 

소스 코드

import java.util.*;

public class Main
{
	public static void main(String[] args) {
	    Scanner scan = new Scanner(System.in);
	    
	    // 조건 값들 입력 받기
	    int n = scan.nextInt();
	    int m = scan.nextInt();
	    int cardArr[][] = new int[n][m];
	    int max = 0;
	 
	    for(int i = 0; i < n; i++){
	        //행에서 가장 작은 값을 담을 변수
	        int rowMin = 10001;
	       
	        for(int j = 0; j < m; j++){
	            cardArr[i][j] = scan.nextInt();    
	            
	            if(cardArr[i][j] < rowMin){
	                rowMin = cardArr[i][j];
	            }
	        }
	       
	        // 행에서 가장 작은 값이 max보다 클 경우 max 값 변경
	        if(max < rowMin){
	            max = rowMin;
	        }
	    }
	    
	    System.out.println("result = " + max);  
	}
}

 

예제 4 - 1이 될 때까지

난이도 ●○○ | 시간 제한 1초 | 메모리 제한 128MB | 기출 2018 E 기업 알고리즘 대회

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다
2. N을 K로 나눈다

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

 

입력 조건

• 첫째 줄에 N(2 ≤ N ≤ 100,000)과 K(2 ≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

 

출력 조건

• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최솟값을 출력한다.

 

입력/출력 예시

입력 예시	출력 예시
25 5	2
17 4	3

 

요점

• 최대한 많이 나눈다.

 

소스 코드 

import java.util.*;

public class Main
{
	public static void main(String[] args) {
	    Scanner scan = new Scanner(System.in);
	    
	    // 조건 값들 입력 받기
	    int n = scan.nextInt();
	    int k = scan.nextInt();
	    int result = 0;
	 
	    while(true){
	        // 나머지를 더한 후 나누기
	        result += (n % k) + 1;
	        n /= k;
	        
	        // 나눌 수 없어지면 종료
	        if(n < k) break;
	    }
	    
	    //1이 될때까지 남은 값을 연산 횟수에 포함
	    result += (n - 1);
	    
	    System.out.println("result = " + result);  
	}
}

 

그리디 알고리즘을 예제를 풀어본 후

업무가 아닌 코딩 테스트를 준비하고 알고리즘 문제를 풀어보니 정말 쉬운 일이 아니다ㅜㅜ 특히 IDE 자동 완성이 없는 환경에서 작성하는 것과 웬만하면 메서드를 외울려고 하다보니 다른 언어에 비해 메소드 사용이 복잡한 Java는 정말 죽을 맛이다. 그리드 알고리즘은 처음 풀어보는 코딩 테스트 문제이니 만큼 시간은 신경 쓰지 않으면서 했는데 알고리즘이 아니라 메서드명 찾아보고 외우는데 시간을 다 쓴 것 같다. 알고리즘 자체가 많이 어렵진 않았지만 이러한 형식의 문제들을 그리디 알고리즘이라고 인식하면서 풀어본 적은 없어서 알고 푸는 것과 모르고 푸는 것은 문제 해결 방식에도 큰 차이가 있을 것 같다. 책에 설명도 워낙 잘 되어있어서 이해하기 어려운 부분도 책을 읽어보면 쉽게 이해되는 편인 것 같다. 소스 코드를 다 짠 후 나동빈 님 GitHub에 들어가서 코드를 비교하고 배울 점은 배우는 것도 은근히 즐거운 일인 것 같다. 

 

GitHub: https://github.com/Leeyeonjae/coding-test/tree/main/3_Greedy

참고서적 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈