Greedy Algorithm
그리디 알고리즘
그리디(greedy)는 탐욕스럽고 욕심 많다는 뜻이다.
그리디 알고리즘은 이름에 걸맞게
항상 자신의 이익이 최대가 되게 하는 짓만 골라서 한다.
그리디 알고리즘은 문제를 푸는데 가장 직선적으로 설계된 기술이다.
n 개의 입력을 받아,
그 중 몇몇 제약조건을 만족시키는 부분 집합을 얻어내야 한다.
가령, 물건 몇 개와 그 물건들의 이득, 가방의 무게 한도를 준다면
무게가 한정돼있다든지, 몇 개 이상은 못 담는다든지 하는 제약조건을 만족시키면서
가장 많은 이득을 보게 하는 물건들의 리스트를 결과로 제출해야 한다.
이런 문제를 항상 이득을 많이 보려는 방향으로 해결하므로
그리디 알고리즘이라는 이름이 붙은 것이다.
해결 방법 (solution)
해결 방법은 많다.
물건 리스트가 A, B, C 라고 주어졌을 때
A와 B를 같이 담으면 폭발해서 사망한다거나 하는 것이 아니다.
따라서 그냥 ‘장바구니에 물건을 담는 방법’이라고 말한다면
이 문제의 해결 방안은 여러가지가 될 것이다.
A를 담든 A, B를 담든, C를 담든 일단 해결 방법이다.
해결 방법이라는 것은, 문제를 해결하기 위한 모든 상상 가능한 방법을 말한다.
실제 가능한 해 (feasible solution)
그렇기만 하면 얼마나 좋을까?
담을 수만 있으면, 살 수만 있으면 무슨 물건이든지 다 사담을 것이다.
그러나 우리는 항상 제약에 부딪힌다.
우리는 돈이 없고, 또 돈이 많더라도 가방이 싸구려라 담을 수 있는 양이 정해져있다.
사실 전쟁이 나는 것도, 싸움이 나는 것도 다 자원의 희소성에서 오는 것이 아니겠는가?
따라서 우리는 이 제약조건을 만족시키는 해를 찾아야 한다.
목적 함수 (objective function)
우리는 문제를 해결할 때 우리가 원하는 게 무엇인지를 정해야 한다.
우리가 원하는 게 비용을 줄이는 것인지, 아니면 이익을 많이 얻는 것인지 등을 정해야 한다.
이를 목적 함수라고 부른다.
최적의 해 (optimal solution)
우리의 최종 목표는
실현 가능하면서도
돈이 제일 적게 들거나 돈을 제일 많이 벌 수 있는 해를 구하는 것이다.
이를 최적의 해라고 한다.
해를 찾는 과정
-
해를 찾는다.
우리가 툭툭 던지는 해결 방법은 실제 가능한지 아닌지를 고려하기 전의 모든 해결 방법이다.
거기서 제약 조건이 걸린다. 제약조건은 그 해결 방법들을 제한하는 물리적인 고려사항이다.
100만원 밖에 없다면 150만원 어치를 살 수가 없고, 20kg 가 한도라면 30kg 를 담을 수 없다. -
실현 가능한 해를 찾는다.
우리가 찾은 해는 여기서 걸러진다.
이들은 해들의 집합 중 비로소 제약 조건을 만족시키는 부분 집합이다. -
목적 함수를 도입한다.
내가 100만원을 벌 수 있는 해가 있을 수 있는데,
80만원만 벌 수 있는 해가 나오면 거기서 만족하고 끝낼 것인가?
목적 함수는 그 해의 만족도를 측정한다.
그 만족도란 내가 그 문제에서 뭘 중요시하느냐에 따라 비용일 수도, 이익일 수도 있다.
전자라면 최소가 돼야 만족도가 높아질 것이고, 후자라면 최대가 돼야 높아질 것이다. -
최적의 해를 찾는다.
해들을 목적 함수에 넣으면 만족도가 나올 것이다.
그 중 가장 큰 만족도를 보이는 해가 바로 우리의 최적의 해이다.
내가 이익을 선택했다면 이익을 가장 크게 하는,
비용을 선택했다면 비용이 가장 적게 드는
최적화하는 과정을 거친 해, 바로 단 하나의 해이다.
우리는 그리디 알고리즘에서 이 최적의 해를 목표로 한다.
결론
그리디 알고리즘은 단계마다 한 번에 하나의 입력값을 고려하는 알고리즘이다.
그리고 그 단계마다 그 값이 최적해에 들어갈지 말지를 결정한다.
선택의 기준은 최적화 척도에 기반한다. (목적 함수가 만든 척도)
수도 코드
Greedy( int n, int A[] ) {
solution = Φ;
for ( i = 1 to n )
x = SELECT (A);
if ( FEASIBLE ( solution, x ) )
solution = UNION (solution, x);
return solution;
}
그리디 알고리즘은 배열로 입력을 받는다.
그 배열을 하나하나 참조하며 선택을 하고 (1. solution)
만일 그게 가능한 해라면 해에 포함시킨다. (2. feasible solution)
그리고 일련의 과정을 거쳐 목적 함수를 도입한다. 여기선 UNION 이라 설명하였다. (3. objective function)
이 모든 과정을 거친 해는 우리가 원하는 해, 최적의 해이다. (4. optimal solution)