[알고리즘] 그리디 알고리즘

그리디 알고리즘이란?

• 현재 상태에서 보이는 선택지 중 최선의 선택지 고르는 과정을 반복하다보면 전체 선택지 중 최선의 선택지라고 "가정"하는 알고리즘이다.
• 실제 문제에서 적용할 때 잘 따져보지 않으면 "반례"가 생길 수 있음.=> 그리디 알고리즘 적용 가능한지 체크해봐야함(조건 등)
• 꼭 각 선택지 중 최선의 선택지를 고른 것이 모였을 때 전체 선택지 중 최선이 아닐 수 있기 때문이다.

다음의 3단계를 반복하면서 문제 해결
1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결 못하면 1로 돌아가 다시 반복.

ex) 10개의 동전 종류로 4200원을 만드려고 할 때 필요한 동전 개수의 최소값은?
10개 종류: 1 5 10 50 100 500 1000 5000 10000 50000

현재상태에서 best수를 선택해서 해를 찾는 방법 => best수? => 최대한 동전 적게
=> 최대한 큰 금액의 동전부터 채우면서 만들기

---

실전! 문제 풀이(백준 11047)

해당 문제는 왜 그리디 알고리즘을 적용해도 될까?
동전의 종류로 제시된 것들이 배수의 형태이기에 반례가 나올 수 없음!

import java.util.*;
class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextInt();
        int[] coins =new int[n];
        int min = 0;
        
        for(int i=0 ; i<n ; i++){
            coins[i]=sc.nextInt();
        }
       
        for(int i=n-1 ; i>=0 ; i--){
            if(k>=coins[i]){
                min += k/coins[i];
                k= k%coins[i];
                if(k==0){
                    break;
                }
            }
        }
        System.out.print(min);
    }
}

얻어갈 점:

• 큰 동전부터 채우기 때문에 평상시에 쓰던 range가 작은 것에서 커지는 for문이 아닌 큰 것에서 작아지는 for문 사용해야한다!

---

실전! 문제 풀이(백준1541)

import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        String[] inputSplited = input.split("[-]");
        int result = 0;
        
        for(int i=0 ; i<inputSplited.length ;i++){     
            if(i==0){
                result += getSplitedSum(inputSplited[i]);
            }else{
                result -= getSplitedSum(inputSplited[i]);
            }
        }
        System.out.print(result);
    }
    
    public static int getSplitedSum(String part){
           int splitedSum=0;
           String[] elements= part.split("[+]");
           for(int i=0; i<elements.length;i++){
               splitedSum += Integer.parseInt(elements[i]);
           }
           return splitedSum;
    }
}

얻어갈 점:

• 문제 풀이 과정에서 string 배열을 "-"를 기준으로 자르고, splited된 string 배열을 다시 "+"기준으로 나눈 후에 합을 구하는데 이 과정을 함수로 추출할 수 있다는 idea (모든 splited된 배열이 동일한 과정으로 합을 구할 것이기에 함수로 뽑아낼 수 있음)

• split함수를 사용할때 파라미터로 넘긴 "-"나 "+"가 가끔 잘 인식되지 않을 수 있다. 이럴 때는 대괄호[]를 이용해 감싸주면 해결 가능!