탐욕법(Greedy)

목차

탐욕법(Greedy)

• 탐욕법 또는 그리디 알고리즘은 문제 해결의 각 단계에서 그 순간에 최적이라고 생각되는 선택을 하는 방법입니다.
• 하지만 그리디 알고리즘으로 최적의 해를 구할 수 있는 문제는 많지 않습니다. 그 이유는 항상 눈앞의 가장 큰 이익만을 쫓기 때문입니다. 따라서 그리디 알고리즘을 적용할 때는 잘못된 방향으로 가고 있지 않는지 꼼꼼히 확인이 필요합니다.
• 문제의 성질이 동일하게 보존되고, 같은 전략을 반복적으로 취할 수 있을 때만 그리디 알고리즘을 적용할 수 있습니다.
•  그리디 알고리즘의 대표적인 문제인 동전 문제를 예시로 들어보겠습니다. 그와 동시에 그리디 알고리즘의 한계도 살펴보겠습니다.
  • 동전 문제 : 10원, 50원, 100원, 500원짜리 동전들을 사용해서 어떤 금액을 표현하려고 할 때 동전 개수를 최소로 사용해서 표현하려면 어떻게 해야 할까요? 
    • 무조건 사용할 수 있는 한 가장 큰 금액의 동전을 많이 사용해야합니다.
    • 위와 같은 문제가 그리디 알고리즘으로 풀리는 이유는 큰 쪽의 금액이 적은 쪽 금액의 배수이기 때문입니다. 만약 배수가 아닌 동전이 존재한다면 그리디 알고리즘은 적용할 수 없게 됩니다.
  • 그리디 알고리즘을 적용할 수 없는 동전 문제 : 10원, 50원, 60원짜리 동전을 사용해서 220원을 표현하려면 어떻게 해야 할까요?
    • 기존 그리디 알고리즘처럼 무조건 큰 금액의 동전을 먼저 사용한다고 하면 60원 3개, 10원 4개로 표현하게 됩니다.
    • 하지만 답은 60원 2개와 50원 2개로 총 4개의 동전만으로 표현할 수 있게 됩니다. (이럴 경우는 dp와 같은 방식을 이용하여 문제를 해결할 수 있습니다.)
    • 그리디 알고리즘을 적용할 수 없는 이유는 60원 동전이 그전 금액의 동전인 50원 동전으로만 표현할 수 없기 때문입니다. 
    • 이처럼 그리디 알고리즘을 적용할 때는 주의가 필요합니다.
• 그리디 알고리즘의 다른 대표적인 문제인 도시락 문제를 예시로 들어보겠습니다.
  • 도시락 문제 : N개의 도시락이 있고, 전자레인지는 단 한 대만 존재하며 한 번에 하나의 도시락만 데울 수 있습니다. 각 도시락은 조리시간과 먹는 시간이 다르게 정해져 있습니다. 이때 첫 번째 도시락을 데우기 시작한 순간으로부터 모든 도시락을 다 먹는 데 걸리는 시간이 최소가 되게 하려면 어떻게 해야 할까요? (다 데운 도시락은 바로 누군가 먹습니다.)
    • 이럴 경우 무조건 먹는데 오래 걸리는 시간부터 순서대로 데우면 됩니다.
    • 전자레인지 데우는 시간은 겹칠 수 없지만, 도시락을 먹는 시간은 여러 명이 동시에 먹을 수 있으니까 시간이 겹치더라도 상관이 없습니다.
    • 예시를 들어보겠습니다. 도시락 1, 2 가 있을 때 도시락 1은 데우는 시간이 10, 먹는 시간이 4이고, 도시락 2는 데우는 시간이 3, 먹는 시간이 15입니다. 이럴 경우 도시락 데우는 시간은 순서에 상관없이 같게 될 것이고, 식사시간은 겹치는 것이 가능하기 때문에 무조건 식사시간이 빠른 도시락부터 데우는 것이 유리합니다.
      • 
    • 이처럼 확실한 방향성이 존재하는 문제는 그리디 알고리즘을 통해 해결할 수 있습니다.

예시

• [백준 11000] 강의실 배정
  • Si에 시작해서 Ti에 끝나는 N개의 수업이 주어질 때, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 합니다. 즉, 어떤 강의실이 끝나면은 그 강의실은 계속해서 사용하는 것이 유리합니다. 
    • 여기서 그리디 알고리즘 아이디어를 떠올릴 수 있습니다.
  • 먼저 강의 시작 시간 순서대로 정렬을 해줍니다. 
  • 어떤 강의실이 끝나면 그 강의실은 계속해서 사용이 가능합니다. 따라서 강의실을 배정해 주면서 끝나는 시간을 우선순위큐에 넣어줍니다.
  • 다음 강의실을 배정할 때 만약 먼저 배정된 강의실 중에 끝난 강의실이 있다면 그 강의실을 그대로 사용하면 됩니다. 
    • 끝난 강의실을 우선순위큐에서 빼주고, 새로운 강의의 끝나는 시간을 우선순위큐에 넣어줍니다.
    • 우선순위큐를 사용하는 이유는 먼저 배정된 강의실 중에 가장 빨리 끝난 강의실을 파악하기 위함입니다.
  • 만약 먼저 배정된 강의실 중 가장 빨리 끝나는 시간보다 현재 강의의 시작시간이 빠르다면 새로운 강의실을 배정받아야 하는 상황입니다.
  • 우선순위큐는 그대로 두고, 새로운 강의의 끝나는 시간을 우선순위큐에 넣어줍니다.
  • 코드

    • import sys
      from heapq import heappush,heappop
      
      input = sys.stdin.readline
      
      n = int(input())
      
      arr = [list(map(int,input().split())) for _ in range(n)]
      
      arr.sort(key=lambda x:x[0])
      q = []
      
      for start,end in arr:
          if not q or q[0]>start:
              heappush(q,end)
          else:
              if q[0]<=start:
                  heappop(q)
                  heappush(q,end)
      print(len(q))

• [프로그래머스] 재미있는 레이싱 경기장 설계하기
  • 난이도 높은 그리디 문제입니다.
  • 문제는 높이 차이의 최솟값이 최대가 되도록 레이싱 경기장을 설계하는 것입니다. 높이 차이의 최솟값이 최대가 되기 위해서는 높이가 작은 것과 높이가 큰 것을 번갈아가며 설치하게 되면 높이 차이 최솟값이 최대가 될 것입니다.
  • 전체 경기장 개수가 짝수개인 경우는 아래와 같이 나눠질 수 있습니다. (큰-작은-큰-작은-큰-작은-..) 또는 (작은-큰-작은-큰-작은-큰-...) 처럼 번갈아갈 경우 높이 차이의 최솟값이 최대가 될 것입니다. 
    • 
    • 위 경우를 살펴볼 경우, 큰-작은 과 작은-큰 의 높이 차이는 동일하지만, 그 쌍끼리의 사이의 차이는 다르게 됩니다. 그때의 차이를 살펴본 결과 큰 것을 먼저 세웠을 때가 차이가 더 크게 됩니다. 차이의 최솟값을 크게 만드는 것이 목표기 때문에 왼쪽과 같이  설계를 해야 합니다.
    • 여기서는 또한 |b1-a3|가 가장 작을 경우이기 때문에 앞에 것들을 뒤로 이어 붙여봐야 의미가 없습니다.
  • 전체 경기장 개수가 짝수개인 경우는 아래와 같이 나눠질 수 있습니다. 가운데 있는 값을 작은 걸로 볼지 큰 걸로 볼지에 따라서 나뉘게 됩니다.
    • 
    • 가운데 있는 것을 작은 것으로 보게 되면 왼쪽과 같이 표현이 가능하고, 큰 것으로 보게 되면 오른쪽 같이 표현이 가능합니다. 
    • 그 차이를 살펴보니 a1 a4 a2 a5 순서는 모두 같지만 a3의 위치만 다른 것을 확인할 수 있습니다. 그런데 이때 |a5-a3|와 |a3-a1|중 어떤 것이 더 차이가 큰지 모르기 때문에 이 경우에는 확인작업이 필요합니다. 
      • 이 뿐만 아니라 |a1-a4| |a4-a2| |a2-a5| 도 체크를 진행해주어야합니다. |a5-a3| 또는 |a3-a1|이 나머지 경우보다 값이 작다는 보장이 없기 때문입니다.
      • 참고: 짝수일때는 |b1-a3|가 가장 작은경우인게 확실합니다. (번갈아가면서 하는데 앞부분에서 제일 큰값과 뒷부분에서 제일작은값의 차이이기때문에)
    • 만약 앞에 것을 뒤에 이어 붙이게 된다면 ( |a1-a4| |a4-a2| |a2-a5| |a5-a3| |a3-a1| )중에서 차이가 가장 작은 것을 제거해 줄 수 있습니다.
      • a1 - a4 - a2 - a5 - a3 순서가 동일하므로 a4 - a2 - a5 - a3 - a1 / a2 - a5 - a3 - a1 - a4 / a5- a3 - a1 - a4 - a2 /...처럼 앞에 거를 뒤로 붙여주면 차이가 가장 작은 것을 제거해줄 수 있습니다.
      • 위처럼 나오게 되는 이유는 a3이 작은지 큰지 애매하기 때문에, a1 하고 붙어도 큰-작은 쌍이 될 수도 있고 a5랑 붙어도 큰-작은 쌍이 될 수 있기 때문입니다.
      • ( |a1-a4| |a4-a2| |a2-a5| |a5-a3| |a3-a1| ) 에서 차이의 최솟값이 되는 것을 하나는 제일 앞 하나는 제일 뒤로 배치를 해주면 차이의 최솟값을 제거한 상태로 배열을 진행할 수 있습니다.
    • 따라서 새로운 arr에 가운데 값을 제외하고 절반으로 나눈 뒤 반반씩 번갈아가며 넣어줍니다. 그 후에, 가운데 값을 맨 뒤에 넣어주고, 가운데 값과 제일 앞의 비교를 위해 제일 앞에 있는 값도 추가를 해줍니다. 
    • 그 후에 모든 값들의 차이를 구해주고 2번째로 작은 값을 출력하면 차이의 최솟값이 최대가 됩니다. 
      • 2번째로 작은 값인 이유는 가장 작은 값인 부분을 기준으로 나눠서 앞 뒤로 쪼개면 되기 때문입니다.
      • 만약 a4-a2의 차이가 제일 작다면  a2 - a5 - a3 - a1 - a4와 같이 쪼개주면 됩니다.
  • 이처럼 홀수, 짝수로 나눠서 그리디 문제를 다르게 생각하는 문제도 많이 존재합니다. 꼭 홀수, 짝수가 아니더라도 각 범위별로 쪼갠 뒤 각각 그리디로 풀어나가는 방식도 존재합니다. 따라서 문제를 볼 때 상황에 따라 결과가 다르게 나오는 것 같으면 값의 범위를 나눠서 풀어나가는 방식도 생각해주어야 합니다.
  • 코드

    • def solution(heights):
          heights.sort()
          
          n_heights = len(heights)
          if n_heights%2==0: # 짝수개 인경우
              new_arr=[]
              for i in range(n_heights//2):
                  new_arr.append(heights[n_heights//2+i])
                  new_arr.append(heights[i])
              
              diff = []
              for i in range(n_heights-1):
                  diff.append(abs(new_arr[i+1]-new_arr[i]))
              diff.sort()
              
              return diff[0]
          else:
              new_arr=[]
              for i in range(n_heights//2):
                  new_arr.append(heights[i])
                  new_arr.append(heights[n_heights//2+1+i])
              new_arr.append(heights[n_heights//2])
              new_arr.append(heights[0]) # 제일 작은 값을 찾기 위함.
              
              diff = []
              for i in range(len(new_arr)-1):
                  diff.append(abs(new_arr[i+1]-new_arr[i]))
              diff.sort()
              
              return diff[1]