[Algorithm][Greedy]그리디 알고리즘

필자의 포스팅 중에서 동적계획법 포스팅이 있다.

거기서 필자가 했던 말을 인용해서 가져와 보겠다.

여러분이 프로그램에게 일을 시키는 이유는 무엇일까?

정말 간단한데 "많은 작업을 시키거나 적은 작업을 여러번 반복하기"위해서이다.

결국에는 많이 시킨다는 것이다.

사람입장에서 덧셈을 만번시키면 아주 죽으려고 하겠지만 컴퓨터 입장에서는 만번이야 가볍게 할 것이다.

문제는 그러다 보니 컴퓨터에게 더 많은 일을 시키고 결국 컴퓨터 역시 한계에 부딪히게 된다.

이러한 문제는 여러방면에서 흔히 발생하는데...

소위 문제를 해결할때 보통은 브루트포스, 즉 완전탐색을 하게 된다.

이 방식은 지구상에 존재하는 모든 문제를 해결해 줄 수 있다.

단, 시간이 충분하게 있으면.

문제는 당연히 세상에서 억만금이 있어도 시간을 살 수는 없다는것,

즉 시간이 충분하다는 전재조건은 엄청나게 많은 경우에서는 성립하지 않는 명제다.(물론 작은 일이나 어쩔수 없는 경우는 제외다.)

이를 해결하기위해서 제일 처음 나온게 바로 캐싱을 이용한 것이다. 바로 동적 계획법이다.

문제는 동적계획법이라는게 1차원이라면 시간을 아주 절약가능하지만 차원이 늘어나게 되면 동적계획법도 시간을 많이 잡아먹는다.

어쨋든 모든 루트를 고려해야하는데 최적화 하는 개념인데 루트끼리 중첩이 안된다면?

혹은 루트가 너무 많이 생성된다면?? 의미가 없어지는것이다.

가령 아래의 문제를 해결하려고 해보자.

출처 - https://en.wikipedia.org/wiki/Greedy_algorithm

흔히 동정교환 문제라는 유명한 문제이다.

N이라는 값을 지불하기위해서 a,b,c,d...의 동전이 있다. 동전의 갯수를 최소화 하려면 어떻게 해야하는가?

위의 경우 36원, 20, 10, 5, 1의 화폐단위가 있다.

우리는 36원을 만들기 위해서 동전갯수를 최소화 하려면 20, 10, 5, 1을 한개씩 쓰는게 최소라는걸 알 수 있다.

근데 프로그램은 어떻게 이걸 구할까?

먼저 완전탐색을 생각할 수 있다. 경우의 수를 생각해보자.

성공하는 루트를 찾기위해서 탐색하는 양을 보자. 참고로 위의 그림은 "성공하는 루트" 만 찾은 것이다.

당연히 저것보다 엄청나게 많이돈다.

이제 우리는 엄청난 반복을 도는것을 회피하기 위해서 동적 계획법을 도입할 것이다.

하지만 보면 알겠지만 사용하는 동전이 4종류이므로 동적계획법의 차원도 4차원이 된다.

문제는 그게 전부가 아니라 4차원이 된다는것은 특별한 일이 있지 않는 한 동적계획법으로 효과를 드라마틱하게도 보기 어렵다.

왜냐하면 중복이 적을 것이기 때문이다. 중복이 적은데 연산량은 많다? 동적계획법이 먹히기 힘든 상황이라는 것이다.

이런 상황을 해결하기 위해서 등판한 것이 바로 그리디 알고리즘이다.

그리디 알고리즘은 사실 뭐...매우 단순한 개념이라고 볼 수 있다.

모든 각각의 상황에서 최적만 고른다! - 그리디 알고리즘

사실 아주 위험천만한 발상이다.

그리디 알고리즘은 각각의 상황에서 최선만 고른다는 것이다.

동전의 갯수가 M, 가격이 N일 때 

O(M^N)을 굴려야하는 동적계획법에 비해서 O(N)밖에 안걸리는 그리디가 아주 효과적이다.

하지만 여기서 문제가 있는데 그리디 알고리즘은 최적화 알고리즘은 될지 몰라도 정답을 찾는 알고리즘은 될 수 없다.

왜냐하면 아래 같은 문제가 있다고 가정해보자.

출처 - https://en.wikipedia.org/wiki/Greedy_algorithm

보다시피 매 순간 최적을 찾았더니 최대값을 찾지 못한다.

부분의 최고가 전체의 최적이 된다는 보장이 없기 때문이다.

단순 동전계산문제도 그렇다.

위의 값이 정답인것은 맞지만 이는 몇가지 조건이 가능해서이다.

100원을 70,60,40,10짜리 동전으로 나눈다고 할때 그리디로 계산하면 70,10,10,10이나온다.

그런데 실제로 값은 60,40이 정답이된다.

그래서 조건이 실제로 맞으려면 특정 동전 A가 있다면 A를 제외한 나머지 동전읜 A의 약수여야한다.

거꾸로 말하면 모든 다른 동전들의 배수가 A가 되야한다.

이렇게 그리디 알고리즘으로 무슨 정답(최적화를 하려고 한다면 이는 다른 이야기가 된다.)을 찾으려면 조건이 필요하다.

그리디 알고리즘으로 정답을 찾는 조건

1. 탐욕스런 선택 조건(greedy choice proeprty)

2. 최적 부분 구조 조건(optimal substructure)

각각이 뭘 뜻하냐면 매번 탐욕스러운 선택을 해야하며, 각각의 부분의 최적이 영원히 최적이여야한다.

왜냐하면 그럴 경우 앞으로도 최선인게 자명하기 때문이다.

이를 응용한 것이 다익스트라알고리즘과 교실할당문제, 동전교환문제, 냅색문제등이 있다.