[Algorithm] 탐욕법은 뭐야?

탐욕이란 지나치게 탐하는 욕심이라는 뜻이다. 여기서 알 수 있듯이 탐욕법은 주어진 상황에서 최선의 방법을 고르는 알고리즘을 말한다.

 

탐욕법은 앞서 소개했던 정렬 알고리즘, 탐색 알고리즘 등과는 다르게 사전에 외우고 있지 않아도 풀 수 있는 가능성이 많은 코딩 테스트 문제 유형이지만 그만큼 사전 지식보다는 수험생의 창의력, 논리력, 판단력, 관찰력 등 여러 가지 능력을 요구하는 문제 유형이다.

 

"백준 2847번 게임을 만든 동준이" 라는 문제를 예로 탐욕법을 설명하겠다.  문제 확인

 

해당 문제에서는 더하기는 불가능하고 빼기는 가능하다. 따라서 "가장 뒤에 있는 수는 변하지 않는다."라는 생각을 할 수 있다. 그러므로 문제 해결을 위해서는 주어진 배열의 앞에서부터 값을 바꾸는 것이 아니라 뒤에 있는 숫자를 기준으로 생각해야 한다. 다음은 문제 해결 논리 순서이다.

 

1. 기준값과 기준 앞의 값을 비교한다.
2. 기준값이 크다면 기준 앞의 값을 기준값으로 설정하고 과정 4로 넘어간다.
3. 기준 앞의 값이 크다면 해당 값을 기준값보다 1 작게 설정하고, 두 수의 차이를 저장한다.
4. 2, 3의 과정을 반복한다.
5. 마지막에 두 수의 차이를 저장해줬던 값을 출력한다.

다음은 2847번 풀이를 위한 배열을 시각화한 자료이다.

 

탐욕법 1번째

초록색은 비교 값, 파란색은 기준값이라고 하겠다. 배열의 뒤를 기준으로 비교를 해야 하므로 기준값을 5로 한다.

 

탐욕법 2번째

기준값보다 비교 값이 크기 때문에 비교 값을 4(기준값 - 1)로 만들어주고 감소시킨 횟수를 저장한다. (현재 감소 횟수: 3)

 

탐욕법 3번째

기준값보다 비교값이 작기 때문에  무시한다. (현재 감소 횟수: 3)

 

탐욕법 4번째

기준값보다 비교값이 크기 때문에 비교값을 2(기준값 - 1)로 만들어주고 감소시킨 횟수를 저장한다. (현재 감소 횟수: 5)

 

탐욕법 5번째

기준값보다 비교값이 크기 때문에 비교값을 1(기준값 - 1)로 만들어주고 감소시킨 횟수를 저장한다. (현재 감소 횟수: 10)

 

탐욕법 6번째

최종적으로 탐욕법이 진행된 모습이다.

 

다음은 위의 과정을 코드로 표현한 값이다.

 

n = int(input())
 
data = []
for i in range(n):
  data.append(int(input()))
 
result = 0
for i in range(n-1, 0, -1):
  if data[i] <= data[i-1]:
    result += data[i-1] - data[i] + 1
    data[i-1] = data[i] - 1
print(result)
 

 

data[i]가 기준값, data[i-1]가 비교 값, result가 감소 횟수이다.