[Greedy] 그리디 알고리즘

그리디 알고리즘을 설명하기전에 우리는 동적 계획법을 숙지할 필요가 있습니다.

 

먼저 동적 계획법이란 A라는 연산을 여러번 반복을 해야하는 문제가 있다면 A의 답을 미리 계산해놓고

 

후에 A 연산이 또 다시 등장할때 미리 계산해놨던 A의 답을 다시 쓰는 것을 말합니다.

 

너무 설명이 난해하죠? 간단한 예시를 들어보겠습니다.

 

'

'

'

 

아래는 흔히들 알고계시는 피보나치 수열입니다.

 

 

F0 = 0

F1 = 1

F2 = 1

F3 = 2

F4 = 3

F5 = 5

F6 = 8

.

.

. 

뜬금없이 피보나치 수열이 왜 등장할까요?

 

우리가 동적 계획법을 사용하지않고 피보나치 수열을 구하는 함수를 작성한다고 생각해봅시다.

 

F0 = 0 , F1 = 1 로 초기화를 시키고

F(int n) 이라는 함수를 선언하고

 

F(int n){

   if (n == 0 || n == 1) 

      return n;

   else

      return F(n-1) + F(n-2);

} 

이런 형태가 나오겠죠?

 

그럼 우리가 1번째부터 10번째 수열의 값을 구하고싶다고 하면

n에 0을 넣고 0을 받습니다.

n에 1을 넣고 1을 받습니다.

n에 2를 넣고 다시 1과 0 을 넣어 0과 1을 더해 1을 받습니다.

n에 3을 넣고 다시 2와 1을 넣고 n에 2를 넣어 다시 0과1을 더한 후 n에 1을 넣어 1이 나와 그것을 더하면 2가 나옵니다

.

.

.

 

1~10까지 구하기 위해서는 이러한 연산을 수없이 반복해야 나오게 되는군요;;;

만일 이 함수를 통해 반복문으로 1~10까지의 수열의 값을 구한다고 치면...

아주 많은 중복연산을 거쳐가게됩니다.

 

결국 쉽게말해 동적 계획법을 사용하지 않는다면 F(4)라던지 F(3)이라던지 한번 계산했던 연산을 여러번 반복하여 풀어야합니다.

그럼 이것을 동적 계획법을 통해 연산을 해보겠습니다.

 

먼저 자연수를 담을 배열을 하나 선언합니다.

int[] Array = new int[10];

 

다시 피보나치 함수를 만들어볼까요?

 

F(int n){
   if(n==0 || n==1)

      return n;
   if( Array[n] != 0 )

      return Array[n];

   Array[n] = F(n-2) + F(n-1);

   return Array[n];

}

아까 처럼 1~10까지의 피보나치 수열을 구해봅시다.

n에 0을 넣고 0을 받습니다.

n에 1을 넣고 1을 받습니다.

n에 2를 넣고 0과 1을 더해 1을 받고 Array[2]에 1을 저장합니다.

n에 3을 넣고 다시 f(2)와 f(1)을 넣습니다. 여기서 if( Array[n] != 0 ) return Array[n]; 이 코드를 통해 저장된 F(2)를            불러 오고 1과 1을 더해 2를 받음과 동시에 Array[3]에 2를 저장합니다.

n에 4를 넣고 f(3)와 f(2)를 더합니다. f(3)과 f(2)는 Array[3]과 Array[2]에 저장되어 3을 내뱉습니다.

 

이처럼 반복할것같은 계산은 미리 해버리는것이 동적 계획법입니다.

 

그럼 본론으로 넘어가서 이것이 그리디 알고리즘과 무슨 상관이 있을까요?

 

동적 계획법은 확실히 빠른 방법이지만 흔히 말하는 '주먹구구' 입니다.

미리 답을 구해서 연산했다는것은 다르지만 결국 1~10까지 모든 경우의 수를 계산해야 한다는건 다를바가 없습니다.

 

예시를 하나 들어보자면

 

동적 계획법으로 집에서 회사까지 가는 경우의 수가 100가지가 된다고 생각해봅시다.

동적계획법을 통해 최단 거리를 계산하려면 집과 회사 사이의 모든 교차로를 계산하여 가장 빠른 길을 제시해줍니다.

 

그렇다면 그리디 알고리즘을 쓴다면 무엇이 달라질까요?

그리디 알고리즘은 교차로에 도착할 때 마다 다음 교차로는 어디가 제일 가까운지 새로 계산합니다.

 

어? 비슷한거 아닌가요? 라고 생각하실 수 있는데요

 

동적계획법은 회사까지 출발하기 전에 미리 모든 경우의 수를 생각하여 전체의 최단거리를 구해서 출발하고,

 

그리디 알고리즘은 일단 출발하고 교차로가 나올 때 마다 더 빠른길을 선택하여 가는겁니다.

그렇다고 그리디 알고리즘이 항상 동적계획법보다 좋은건 아닙니다.

 

회사까지 가는길을 그림과 숫자로 표현을 해보자면

 

 

 

 

그림과 같은 상황에서 숫자 1당 1m라고 생각했을때

양쪽길은 한쪽은 265m , 한쪽은 31m 입니다

동적계획법을 사용하면 모든 경우의 수를 계산하기 때문에 처음에 30m를 가더라도 전체적으로 거리가 가까운 31m를

선택하게 됩니다.

 

그러나 그리디 알고리즘을 사용하게 되면 모든 경우의 수를 계산하지 않고 각각의 교차로에서만 선택하기 때문에 

뒤에 전체적으로 265m를 가야해서 훨씬 느리지만 첫 교차로에서 더 최적의 경우를 찾기 때문에 265m를

선택하게됩니다.

 

결론적으로 동적계획법은 계산시간이 걸리더라도 결과의 값은 항상 효율적이라고 할 수 있습니다.

반대로 그리디 알고리즘은 선택해야 할때 최적의 수를 선택하기 때문에 계산시간은 빠르지만 결과의 값은 항상 효율적인 값은 나오지 않습니다.

 

그렇다면 그리디 알고리즘을 이용할 수 있는 예시에는 무엇이 있을까요?

 

거스름돈을 예시로 들어볼까요?

 

1240원짜리 물건을 친구에게 2천원을 받고 팔기로 했습니다.

그런데 거스름돈으로 주는 동전은 최대한 적게 주고싶습니다.

 

여기서 거스름돈은 760원이 되는데요 여기서 거스름돈을 줄 수 있는 방법은 아주 많습니다.

10원짜리 76개 , 10원짜리 66개 100원짜리 1개 ... 이런식으로 나열하려면 꽤 많이 나열할 수 있는데요

여기에 그리디 알고리즘을 적용시켜 볼까요?

 

먼저 500 100 50 10 순으로 동전을 정렬시킵니다.

760을 500부터 큰 순으로 차감해 나갑니다.

500보다 760이 크네요 그렇다면 500원을 거슬러줄수있습니다.

260원이 남았습니다. 100보다 크고 500보다 작은 수 입니다.

100을 거슬러줍니다.

.

.

.

이런식으로 큰 수 부터 반복하면 최대한 적은 동전을 거스름돈으로 친구에게 줄 수있습니다.

 

 

오늘은 동적 계획법과 그리디 알고리즘에 대하여 이론공부를 해보았습니다.

마지막으로 기억할것은

 

동적계획법은 계산시간이 걸리더라도 결과의 값은 항상 효율적이라고 할 수 있다.

 

그리디 알고리즘은 선택해야 할때 최적의 수를 선택하기 때문에 계산시간은 빠르지만 결과의 값은 항상 효율적인 값은 나오지 않는다.

 

이 두가지입니다!