탐욕(그리디) 알고리즘(Greedy Algorithm)

탐욕 알고리즘은 현재 사용할 수 있는 최선의 옵션을 선택하여 문제를 해결하기 위한 접근 방식이다.

현재의 최상의 결과가 전반적인 최적의 결과를 가져올지는 걱정하지 않으며 현재 진행 중인 선택이 잘못되더라도

이전의 결정을 뒤집지 않고 계속 진행한다.

 

다시금 얘기하면 현재 보기에 가장 최적으로 보이는 경우를 조건으로 두고 

계속해서 답을 좆는 방식이란 것이다. 

최적의 해를 구하기 위해 설계적으로 딱! 하고 가는 것이 아니라 

일차적 최적, 이차적 최적해서 가장 가까운 최적을 찾아가는 기법이기에 항상 최적의 해를 구할 수 있는 문제는 아니다.

---

그러나 왜 이 알고리즘을 많이 사용할까?

 

코딩테스트에서 구현문제의 경우 그리디 알고리즘을 사용하는 경우가 많다. 

---

전체적인 맥락에서 처음부터 끝까지 최적의 길을 찾기보단 순차적으로 문제에서 주어진 조건을 해결해 나가는 순으로

구현하는 것이 구현하는 시간 측면에서 득이기 떄문이다. 

또한 그리디로 구현시 계속해서 성공하는 녀석을 연결지어 찾아가는 경우도 생기기에

성질을 보존함으로써 정답을 얻을 수 있다. 

 

그럼 가장 눈에 보이는 최적의 조건이라 생각드는 것을 순서로 구현한다!* 다만 반례가 있을시 그걸로하면 안된다... 다 되는건 아니다 ㅠ 

 

그럼 예시를 들어보자

 

1000원을 동전으로 주려는데 가장 적은 동전 개수로 돌려준다면 어떡할까? 

100원 10개? 10원 100개? 500원 2개?

누가 봐도 500원 2개다.

즉, 가장 큰 단위의 동전으로 돌려주는 것이다.

 

그럼 1230원이 주어지고 환전 동전 단위 500,100,50,10 원이 주어진다면 

가장 큰 단위 순으로 동전을 사용해서 돌려주고 나머지를 다음으로 큰 동전 순으로 환전해주면된다.

---

위에서 설명한 바와 같이 문제의 성질이 보존되었다. 

가장큰 단위의 동전으로 나누고, 다음으로 큰 단위의 동전으로 나누는 이 행위는 

가장 최소 개수로 환전해주는 성질을 계속해서 유지하고 있다. 

 

그렇다면 이런식으로 찾아가는 그리디 알고리즘이 항상 최적 해를 찾을 수 있을까? 

아니,,, 때에 따라 다르다...

당장에 가까이 보이는 답이 정답일 수 있지만 예외를 생각하고 설계하다보면

그리디로 접근하다가는 최적해에 도달하지 못하는 경우가 생긴다.

 또한 그리디 특성상 접근하다가 최적이 아니더라도 접근했기때문에 일단 끝까지 시행한다... ㅠ 

 

그렇다면 그리디 알고리즘은 이런 단점이 있는데 계속 써야할까 ?

그렇다!!!

복잡하지만 최적해를 뽑아내는 다른 알고리즘에 비교하여 그리디 알고리즘의  비용이 적은 경우가 많다.

 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

import java.util.*;
import java.io.*;
public class Main {
        public static void main(String[] args)throws IOException{
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StringTokenizer st = new StringTokenizer(br.readLine());
                int n = Integer.parseInt(st.nextToken());
                int k = Integer.parseInt(st.nextToken());
                int[] arr = new int[n +1];
                
                for(int i = 1; i<=n; i++){
                        arr[i] =Integer.parseInt(br.readLine());
                }
                
                int min = 0;
                for(int i = n; i>0; --i){
                        min += (k/arr[i]);
                        k = (k%arr[i]);
                        if(k==0) break;
                }
                System.out.print(min);
        }
}

 

참고 블로그) https://m.blog.naver.com/kks227?categoryName=%EB%8C%80%ED%9A%8C%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98&categoryNo=299