그리디 & 구현

그리디 알고리즘

그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함. 그리디 해법은 그 정당성 분석이 중요함. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하는 과정이 필요함.

루트 노드부터 시작하여 거쳐 가는 노그 값의 합을 최대로 만들고 싶음. 최적의 해는? 5->7->9 단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까? 5->10->4

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음. 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨.

<문제> 거스름 돈 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. 문제 해결 아이디어 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 됩니다. N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 줍니다. 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 됩니다. N = 1260일 때의 예시를 확인해 봅시다. STEP0 남은 돈 1260원 STEP1 남은 돈 260원 STEP2 남은 돈 60원 STEP3 남은 돈 10원 STEP4 남은 돈 0원 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유? 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문 만약 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면 어떻게 되는가? 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 함. JAVA class Solution { public static void main(String[] args){ int n = 1260; int cnt = 0; //동전 개수 int[] coinTypes = {500, 100, 50, 10}; for(int i = 0; i < 4; i++){ cnt += n / coinTypes[i]; n %= coinTypes[i]; } System.out.println(cnt); } } <문제> 1이 될 때까지 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 수행하려고 합니다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다. 1.N에서 1을 뺍니다 2.N을 K로 나눕니다. 예를 들어 N이 17, K가 4라고 가정. 이때 1번의 과정을 한 번 수행하면 N은 16이 됨. 이후에 2번의 과정을 두번 수행하면 N은 1이 됨. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됨. 이는 N을 1로 만드는 최소 횟수. N과 K가 주어질때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성. 문제 조건 출력 조건 첫째 줄에 N이 1이 될때 까지 1번 혹은 2번의 과정을 수행해야하는 횟수의 최솟값을 출력. 문제 해결 아이디어 주어진 N의 대하여 최대한 많이 나누기를 수행하면 됨. N의 값을 줄일 때 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있음. 예를 들어 N = 25, K = 3일 때, 다음과 같다. STEP1 N=25 STEP2 N=24 STEP3 N=8 STEP4