[알고리즘] 탐욕알고리즘 (Greedy algorithm)

1. 탐욕알고리즘이란?

매순간 최적이라고 생각하는 경우를 선택해서 최종 값을 구하는 방식이다.

 

2. 탐욕 알고리즘의 예

1) 동전문제

: 지불해야하는 돈이 4540원일 경우, 1원, 10원, 50원, 100원, 500원 동전으로 가장 적은 수의 동전을 지불하는 문제

public static void main(String[] args) {
		int[] coin = {1, 50, 100, 500};
		int[] pay_count = new int[4];
		
		int price = 4720;
		int count = 0;
		for (int i = coin.length - 1; i >= 0; i--) {
			pay_count[i] = price / coin[i];
			System.out.println(coin[i] + "원 : " + pay_count[i] + "개");
			count += pay_count[i];
			price %= coin[i];
		}
		System.out.println(count);
	}

 

2) 부분 배낭 문제

: 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는다.

- 각 물건은 무게(w)와 가치(v)로 표현된다.

- 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있다.

 

3. 탐욕알고리즘의 한계

- 탐욕알고리즘은 근사치 추정에 활용된다.

- 반드시 최적의 해를 구할 수 있는 것은 아니기 때문이다.

- 최적의 해에 가까운 값을 구하는 방법 중 하나라고 생각.