Greedy 알고리즘 (+백준 11047)

그리디(Greedy) 알고리즘은 이름에서 나온 것 같이 '탐욕적으로 당장의 눈 앞에 보이는 최고의 결과만을 구하려는 알고리즘' 이다.

여러 경우 중 하나를 결정해야할 때마다 그 순간 최적의 것이라고 생각되는 것들을 선택해야하는데 이는 항상 최적의 결과만을 가져오지는 않는다. 

무슨 말인고.. 하면 이는 동적계획법(Dynamic Programming)과 비교가 되는 경우가 많은데, 우리 약속에 의해 어떤한 길을 찾는다고 가정해보자. 

 

서울->대전 , 대전->부산 

 

- 서울에서 대전을 갈 경우 세 갈래 길이 나왔다. 첫번째 길 부터 차근 차근 탐색해본다. ( Dynamic Programmin ) , 아니다 본능적으로 직진길이 우선이다 (Greedy) . 

- 대전까지는 직진을 했다. 다행히 제일 빠른 길이였고 대전->부산으로 또 다시 3가지 갈림길이 나온다. 똑같이 제일 가까워 보이는 직진을 하도록 하자 (Greedy)

- 사고 차량의 발생으로 오히려 시간이 더 지체가 되었다.

 

-> Greedy 알고리즘이라고 항상 최적의 해를 보장시키지는 않는다.

 

백준 11047

대표적인 그리디 알고리즘 문제로 백준 11047(동전0) 문제가 있다. 

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

11047번: 동전 0

 

 

N개의 동전의 종류로 K인 가치를 만드려할 때 , 가장 최소값의 동전 개수를 구하는 문제이다. 

-> 가장 조금만 사용하려면, 가장 큰 단위의 동전을 사용하면 되지 않을까?

 

해당 문제에 대한 코드를 공유한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " "); //한줄에 띄어쓰기(" ")로 입력받은 n과 k를 위해

int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());

int[] coins = new int[n];

int result = 0;

//동전 단위 setting
for (int i = 0; i < n; i++) {
    coins[i] = Integer.parseInt(st.nextToken());
}

//큰 동전의 단위부터 거꾸로 조사
for (int i = coins.length - 1; i >= 0; i--) {
    result += k / coins[i];
    k %= coins[i];
}
System.out.println(result);

n과 k 를 BufferedReader를 통해 입력받는다. (Scanner에 비해 1/6가량 처리시간이 줄어든다.)

동전 단위들을 coins라는 배열에 담아주고 가장 큰 단위 부터 k를 나누어 준다.

값이 나누어진다면 result(output)의 값은 증가되고, 나누고 남은 나머지의 값들을 k 가 되어 다음 큰 단위의 동전에 의해 나누어짐을 반복한다.

 

비교적 간단한 문제였지만, Scanner보다 BufferedReader 를 사용해야하는게 더 낫다는 점 (시간복잡도면에서) 을 배울 수 있던 문제였다.