Greedy algorithm

  Greedy algorithm (그리디 알고리즘) 이란 여러 경우 중 하나를 선택해야 할 때 그 순간 최적값을 고르는 방식을 말한다. 

그리디 알고리즘은 순간순간 최적의 선택을 하지만 결과값인 최종적 해답이 최적이라는 보장을 하지는 않는다. 따라서 그리디 알고리즘을 적용할 수 있는 문제인지 아닌지 생각해야한다.

 

  greedy choice property와 optimal substructure 두가지 조건을 만족해야한다. Greedy choice property는 그 순간 가장 좋아보이는 선택을 한다. 하지만 이후에 상황이나 선택에는 영향을 받지 않는다.  탐욕적 선택 조건은 계속해서 순간의 최적해만 찾는 선택을 하게되고, 이전의 선택이나 이후의 선택에 대해서는 고민하지 않는다. Optimal substructure란 최적해가 부분문제에 대해서도 최적해를 가질때 Optimal substructure라고 한다. 

 

  그리디 알고리즘 문제의 예시로 거스름 돈 문제를 살펴보면 거스름 돈을 동전으로 돌려준다고 했을때 동전의 최소 갯수를 구하는 문제가 있다. 문제의 해결과정은 가장 큰 화폐 단위부터 최대한으로 거슬러 준 다음 그 다음 가장 큰 단위의 동전을 최대한으로 거슬러 주는 방식을 반복하면 된다. 동전의 단위는 500원 100원 50원 10원이다. 이 문제를 그리디 알고리즘으로 해결하기 위해서는 문제의 조건이 그리디 알고리즘으로 해결 할 수 있는지 부터 확인해야한다. 동전중 큰 단위가 항상 작은 단위의 배수 이므로 이 문제는 Optimal substructure를 가지고 있다. 이전의 선택이 나중에 선택에도 영향을 주지 않기 때문에 거스름 돈 문제는 그리디 알고리즘으로 해결할 수 있다.   

# python
n = 1260
count = 0

array = [500, 100, 50, 10]

for coin in array:
	count += n // coin
    n %= coin

print(count)

  다른 문제로 돈을 인출하는데 걸리는 시간의 최솟값을 구하는 문제다. N명의 사람들이 줄을 서있다.  i 번째 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 전체시간은 사람들이 줄 서있는 순서에 따라서 다르다. 이 문제의 조건을 살펴보면 인출에 걸리는시간이 적은 사람이 앞쪽에 있을 수록 전체 시간합이 작아진다는 것을 알 수 있다. 따라서 이 문제는 그리디 알고리즘으로 해결할 수 있는 문제이다. 인출에 걸리는 시간을 오름차순으로 N명을 세우는 방식으로 전체 시간값을 최소화 할 수 있다. 

 

  그리디 알고리즘은 최적해를 구하는 방법으로 사용할 수 있지만 앞서 말한 두 조건에 해당하는지 파악해야한다. 하지만 코딩테스트에서는 대부분의 그리디 문제가 최적인 상태에서 출제된다. 그리디 알고리즘은 코딩테스트에 자주 나오는 부분이므로 공부해서 잘 다듬어야 한다.

 

  그리디 알고리즘 문제처럼 보이는데 동적 프로그래밍 문제였던 것들이 있었다. 그리디 알고리즘과 동적 프로그래밍의 문제 형태가 비슷한 것처럼 느껴지기 때문에 그리디 알고리즘의 방식으로 접근하다가 해결하지 못했다. 예를 들어 X가 주어질때 X가 3으로 나누어떨어지면 3으로 나누고, 2로 나누어 떨어지면 2로 나누고 그 외의 경우에는 1을 빼는 방식을 반복하여 X가 1이 되는 연산 횟수의 최소값을 구하는 문제였는데 이 문제는 동적 프로그래밍을 활용해야 하는 문제였다. 공부를 하다보니까 모르는 부분이 계속 나와서 해결하고 문제발생 해결하고 문제 발생이 반복되고 있다. 해결 못하는 부분이 나오지 않아서 다행이라고 생각한다.