Greedy 알고리즘 - 이것이 취업을 위한 코딩테스트다
책을 보며 공부를 하고 있다
지금의 지식으로는 2단계를 풀기가 힘들다고 판단되었다
(BFS , DFS , DP 등등...)
그래서 책을 보며 공부하고 있다
이번 포스팅에서는 Greedy( 탐욕법 ) 에 대해 알아보겠다
Greedy ( 탐욕법 ) 이란
현재 상황에서 최선의 선택을 하는 방법이다
각 단계별로 가장 최선의 선택을 하는 것이다
에제 문제와 같이 탐욕법에 대해 알아보겠다
거스름돈
당신은 음식점의 점원이다
카운터에는 거스름돈으로 사용할 500원 100원 50원 10원짜리의 동전이
무한히 존재한다
손님에게 거슬러 줘야 할 돈이 N원일 때
거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다
여기서 핵심은 색이 다른 저 문장이다.
이제 문제를 풀기 위해 조건을 생각해보자
1. N은 항상 10의 배수이기 때문에 무조건 0이 될 수 있다
2. 최소 개수를 구하기 위해 큰 수부터 거슬러 주도록 한다
이걸 코드로 작성해보면
ps. 동빈 나 책은 파이썬 기준이지만 나는 자바로 푼다.
코드는 Github 에 올라가 있다.
public class Greedy01 {
public static void main(String[] args) {
System.out.println(solution(1260));
}
public static int solution(int n) {
if(n == 500 || n == 100 || n == 50 || n ==10) { // 딱 맞아 떨어지는것들
return 1;
}
int[] moneys = {500,100,50,10};
int answer = 0;
for(int i=0; i<moneys.length; i++) {
int share = n / moneys[i];
n -= moneys[i] * share;
answer += share;
}
return answer;
}
}
코드를 보면 일단 n 이 거스름돈과 일치할 경우 1을 return 시켜준다.
그이 후부 터는 배열에 거스름돈으로 사용할 돈을 넣어주고
n에서 가장 큰돈부터 나눠준후
n에서 동전 * 몫만큼 빼준다.
그리고 answer에 몫만큼 더해주면
500원부터 순차적으로 자기가 거슬러 줄 수 있는 최대치만큼의 값을 구할 수 있다.
여기서 주의해야할점!
이 문제는 최적의 값을 찾았지만
그리디가 항상 최적의 값을 찾아주는건 아니다
매 순간 최고의 선택을 하는거지
최적의 선택이 아닌거다.
당분간은 책을보며 챕터별로 문제를 풀고 올릴거 같다.