02.01 그리디 알고리즘 1 (JAVA)

그리디알고리즘(Greedy Algorithm)

• 그리디(Greedy)란 '탐욕스러운, 욕심 많은'이란 뜻입니다.
• 그리디 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방식입니다. 하지만 순간의 최적의 선택을 한다고 해서 최종적인 해답이 최적이라는 보장은 없습니다.
• 따라서 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들일 때 그리디 알고리즘을 적용할 수 있습니다.
• 가장 중요한 점은 그리디 알고리즘을 이용하면 최적해를 찾지 못할 수도 있다는 것을 항상 명심해야합니다.

그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제의 조건

• greedy choice property : 현재 선택이 이 후의 선택에 영향을 주지 않습니다.
• optimal substructure : 매 순간의 최적의 해가 문제 전체에 대한 최적의 해여야 합니다.

 

(위 조건이 만족하지 않아도 그리디 알고리즘을 근사 알고리즘으로 사용하는 경우가 있습니다.)

 

• 그리디 알고리즘은 계산 속도가 매우 빠른 알고리즘 중 하나이므로 물론 지역적으로 최적의 선택을 반복하기 때문에 전체적인 최적해를 보장하지는 못하더라도 어느 정도까지 최적에 가까운 해를 구할 수는 있습니다. 어느 정도 적합한 수준의 해답을 알려주기 때문에 근사 알고리즘으로 그리디 알고리즘을 사용하는 경우가 있습니다.

 

예시문제

 

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

package greedy;

import java.util.Scanner;

public class GreedyEx {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
//			Scanner라는 클래스를 임포트해와서 sc라는 변수에 담아준다.
        int a = sc.nextInt(); // 여기서 nextInt();는 int변수를 sc에 담아줄때 쓰는 함수
        int b = sc.nextInt();
//			int a,b에 sc.nextInt();을 담아준다.
        int[] arr = new int[a];
//			배열 arr에 a값을 담아준다.
        for (int i = 0; i < a; i++) {
            arr[i] = sc.nextInt();
        }
//			for문으로 0부터 a값을 반복할 때 arr[i]값에 sc.nextInt();을 담아준다
        int count= 0;
//			int count라는 변수를 초기화 동시에 선언한다.
        for (int i=a-1; i > 0; i--) {
            if(arr[i] < b){
                count = count + (b/arr[i]);
                b = b % arr[i];
            }
        }
//		for문을 돌릴 때 for문은 i를 a-1값으로 초기화하는 것으로 
//		시작하며 조건은 i가 0보다 크고
//		i를 1개씩 감소할때 count에 count+ (b/arr[i]); 더한값을 count에 넣어준다.
//		b에 b를 arr[i]값으로 나눈 값을 저장해준다.
//		count = count + (b/arr[i])를 count += (b/arr[i]);로 쓸수있고
//		b = b % arr[i]를 b %= arr[i]로 쓸수 있다.

        System.out.println(count);
//		count를 출력한다.
    }
}