[알고리즘]그리디(greedy) 알고리즘

그리디(greedy) 알고리즘이란?

단어에서 나타내듯이 아주 탐욕스러운 알고리즘 입니다.

이렇게 탐욕스럽다라고 표현 하니 학생들은 아주 나쁜 알고리즘이네요? 라고 말하네요.

하지만 탐욕스러운 것이 정말 나쁜 것일까요?

자신이 항상 손해 보면서 사는 사람은 없을 것입니다.

사람 사는 세상에 주고 받고 하면서 자신이 더 큰 이득을 보기 위해 조금 더 작은 것을 내 주는 것일 뿐입니다.

이와 마찬가지로 그리디 알고리즘은 현재 선택해야 되는 시점에서 자신에게 가장 이득이 되는 것을 취하고 나머지는 버리는 경우를 그리디 알고리즘이라고 합니다.

이러한 알고리즘의 예로 가장 많이 사용 되는 것이 동전 바꿔 주는 문제인데요.

500원,100원,50원,10원,5원,1원 단위의 동전이 있을때

문방구에 가서 1432원짜리 필통을 구매하고 2000원을 지불 했을때 가장 적은 갯수의 동전으로 거스름돈을 받고 싶습니다.

이때 568원을 거슬러 받아야 하는데요.

500원짜리 한개를 먼저 취하고 나머지 68원이 남게 됩니다.

그 다음 50원짜리 한개를 먼저 취하고 나머지 18원이 남으면

10원짜리 한개 5원짜리 한개 1원짜리 3개로 거스름돈을 받을 때 동전의 갯수가 최소가 됩니다.

이렇게 가장 큰 단위부터 취하게 되는데 568원에서는 최선의 선택은 500원입니다.

하지만 68원에서는 최선은 50원이 되겠네요.

이렇게 선택해야 하는 시점에서 최고로 좋은 것을 취하는 것을 그리디 알고리즘이라고 합니다.

 

하지만 알고리즘에서는 이러한 그리디 문제를 해결하기 위해 먼저 작업을 해야 할 일이 있는데,

그것은 동전 단위를 500원,100원,50원,10원,5원,1원 과 같이 순서대로 정렬을 해 놓아야 합니다.

568원에서 첫번째 단위인 500원짜리를 선택 할 수 있는지 확인 하고 선택이 가능하면 가능한 갯수를 선택 후

남은 돈 68원에서 두번째 단위인 100원짜리를 선택 할 수 있는지 확인 하고 선택이 불가능하기에 0개 선택 후

다시 남은돈 68원에서 세번째 단위인 50원짜리를 선택 할 수 있는지 확인 하고 선택이 가능한 갯수 선택 후

남은 18원에서 그 다음 단위 10원짜리 선택 후 나머지 8원에서 그 다음 단위 5원짜리 선택 후 나머지 3원에 대해서 1원짜리 3개를 선택하는 개념으로 이루어 집니다.

 

하지만 이러한 그리디 알고리즘에는 항상 최적이 될 수 있는가 라는 문제가 발생합니다.

동전단위가 1,5,10,50,100,500 단위가 아니라 500원,284원,90원,10원,1원 단위 체계로 되어 있다고 하면 568원을 거스름돈을 주기 위해서는 284원 동전 2개만 주면 되는데...

그리디 알고리즘으로 처리 한다면 500원 하나, 나머지 68원에서 10원 6개,1원 8개 가 필요합니다.

따라서 그리디 알고리즘을 사용하기 위해서 가장 고려해야 할 부분은 바로 "전체적으로 최적이 될 것인가?"  입니다.

 

이러한 그리디 알고리즘을 설계하는 방법은 다음과 같습니다.

1. 설계의 기본은 선택할 것이 여러개 일 경우 그 중 가장 좋은 것을 선택하는 것

2. 문제를 여러 단계로 구분하여 각 단계마다 최적해를 구한다.

3. 각 단계의 최적해를 구할 때 가장 큰것 혹은 가장 작은것을 선택하게 된다.

 

그리디 알고리즘 구현시 유의점

- 현재 시점에 있어서 최적의 해를 선택하는데 그것이 전체적으로 최적의 해가 되지 않는 경우를 고려해야 한다.

 

그리디 알고리즘의 장점

- 전체의 모든 경우를 살피지 않고 현재 단계 단계에서 최선의 경우를 선택하는 경우로 각각의 단계를 한번만 수행하므로 수행 시간이 무척 빠르다.

 

이 정도로 소개를 마치도록 하겠습니다.

이러한 그리디 알고리즘은 실제 생활에서 가장 많이 사용되는 경우가 동전 거슬러 주는 경우에도 발생을 하고...

기차표를 예매할때 종점을 기준으로 정렬을 해서 그 사람의 좌석을 발매해 줄때도 유리합니다.

기차표를 구매하는데 첫번째 사람이 서울에서 대전을 구매 했다고 하면 그 좌석을 대전에서 부산 가는 사람에게 다시 부여 해 준다면 훨씬 유리 할 것입니다.

그리고 회의실 예약 시에도 더 많은 사람이 회의를 하기 위해서 중복 시간을 제거 하는 경우 빨리 끝나는 사람을 기준으로 배정을 해 준다면 좀 더 많은 사람이 할당을 받을 수도 있을것입니다.

 

이렇게 그리디 알고리즘은 다양한 곳에서 사용이 되고 있는데요.

이러한 그리디 알고리즘의 핵심은 데이터 정렬에 있다고 해도 과언이 아닐 것입니다.

 

만약 기차표를 예매하는데 있어서 출발지를 가지고 정렬을 한다고 하면 서울에서 출발해서 부산에 가는 사람,그리고 천안에서 대전에 가는 사람이 있는데 대전에서 대구를 가는 사람이 표를 사기 위해서는 서울에서 출발하는 사람이 어디서 내리는 지 확인해야 되고 천안에서 출발하는 사람이 어디서 내리는지를 확인해야 될것입니다.

만약 종점을 기준으로 정렬을 한다면 천안에서 출발해서 대전에서 내리는 사람이 먼저 조회가 될것이므로 어떤 조건으로 데이터를 정렬해서 먼저 선택을 할 것인가가 무척이나 중요한것 같아요.

 

실제로 컴퓨터 과학은 실생활의 규칙들을 얼마만큼 효율적으로 구현할 수 있는가가 중요하기 때문에...

그리디 알고리즘만으로도 충분히 그러한 규칙들을 생각해 볼수 있는 계기가 될것 같네요.

 

인천 원당 컴퓨터학원