#2 그리디 알고리즘 (탐욕법)

그리디 알고리즘 (탐욕법)

현재 상황에서 지금 당장 좋은 것만 고르는 방법

각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방법

• 항상 최적의 값을 보장하는 것이 아니라, 최적의 값의 '근사한 값'을 목표로 함

• 가장 큰 값을 구한다고 할 때, 최적의 값은 100이라는 값을 찾는 것이지만 그리디 알고리즘은 각 단계에서 가장 큰 값을 구하며 내려가기 때문에 다른 결과가 나올 수 있음

그리디 알고리즘 조건

1. 탐욕스러운 선택 조건

   • 앞의 선택이 이후의 선택에 영향을 주지 않아야 함

2. 최적 부분 구조 조건
   - 최종 해결 방법은 부분 문제에 대한 문제 해결 방법으로 구성되어야 함

   보통 코딩테스트에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해줌

   그리디 알고리즘 해결 방법

3. 선택 절차

   • 현재 상태에서의 최적의 해답 선택

4. 적절성 검사

   • 선택된 해가 문제의 조건을 만족하는지 검사

5. 해답 검사

   • 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위 과정 반복

   예제

   <문제>
   당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 짜리의 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전 의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

   풀이
   -> 동전의 최소 개수 : 가장 큰 단위의 화폐부터 거슬러 주기

   

   위 문제가 그리디 알고리즘으로 풀린 이유?

• 가지고 있는 동전 종류에서 큰 단위가 작은 단위의 배수 형태이어서
• 예를 들어 800원을 거슬러 주어야 하는데 동전의 단위가 [500, 400, 100]인 경우, 그리디 알고리즘은 (500 + 100 + 100 + 100)으로 4개의 동전. 그러나, 최적의 해는 (400 + 400)으로 2개의 동전
• 그리디 알고리즘의 해답이 최적해가 아닌 경우도 있으니 검토와 정당성이 중요

시간 복잡도

• 화폐의 종류가 K라고 할 때, 시간 복잡도는 O(K)

• 거슬러줘야 하는 금액과는 무관하며 동전의 총 종류에만 영향을 받음

  
  

---

규명보트

분석

• 규명보트는 한 번에 최대 2명씩
• 두 사람의 무게 합이 무게 제한(limit)을 넘으면 안 됨
• 모든 사람을 구출하기 위해 필요한 구명보트 개수 최솟값 return

입력

• people: 사람 몸무게가 담긴 배열
• limit: 무게 제한

출력

• 모든 사람을 구출하기 위해 필요한 구명보트 개수 최솟값

제한 사항

• 사람은 1명 이상 50,000명 이하
• 각 사람 몸무게, 구명보트 무게 제한은 40이상 240 이하
• 구명보트 무게 제한 > 몸무게 최댓값
  -> 사람들 구출 못하는 경우 없음
  

풀이

• 사람 몸무게를 정렬을 한다 -> 탐색으로 가장 큰 값과 더해서 limit을 넘으면 high를 하나 줄인다 -> 가장 먼저 limit를 넘지 않았을 때 삭제하고 count + 1 -> 모든 경우가 limit를 넘거나 하나 남았을 때 + 1
  -> 결국 맨 뒤 값 2개 비교하게 해서 했다

시간 초과 풀이

def solution(number, k):
    number.sort(reverse=True)
    count = 0

    for i in number:
        high = number.index(i) + 1
        while high < len(number):
            a = i + number[high]
            if a > k:
                high += 1
            elif a <= k:
                count += 1
                number.remove(number[high])
                number.remove(i)
                break
    count += len(number)
    return count

---

멀티탭 스케줄링

분석

• 전기용품 사용 순서가 주어짐
• 멀티탭 구멍 개수에 맞춰 플러그를 빼는 횟수를 최소화

입력

• N: 멀티탭 구멍 개수, K: 전기 용품 총 사용횟수

출력

• 하나씩 플러그를 빼는 최소의 횟수

제한 사항

• 1 <= N <= 100
• 1 <= K <= 100

---

큰 수 만들기

분석

• 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자 구하기

입력

• numbers: 문자열 형식으로 주어진 숫자
• k: 제거할 수의 개수

출력

• number에서 k개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return

제한 사항

• number은 2자리 이상, 1,000,000자리 이하
• k는 1이상 number 자릿수 미만 자연수

풀이

• 리스트를 돌면서 뒤의 값이 앞의 값보다 클 경우 앞에서부터 삭제 개수만큼!
  - 진짜 3분도 안 걸려서 나 진짜 천재인가 싶었는데 역시 아니었다!! 헤헷
  • 틀린 풀이

    def solution(number, k):
    n = list(number)
    count = 0

    while count != k:
        for i in range(len(n)):
            if n[i] < n[i+1]:
                n.remove(n[i])
                count += 1
                break
            else:
                pass

    return ''.join(n)