[AIGORITHM THEORY] GREEDY(탐욕법) 개념정리

개념

컨셉

• 탐욕법 이라고 불린다.
• 현재 상황에서 지금 당장 좋은것만을 고르는 방법
• 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음
• 보통 코딩테스트에 출제되는 그리디 알고리즘의 문제는, 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구
• 그리디 알고리즘을 이용한 해결은 정당성 분석이 중요!
  • 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토
• 문제에서 가장 큰 순서, 가장 작은 순서와 같이 기준을 암시적으로 제시해준다.

문제 해결 방법

1. 선택 절차
   • 현재 상태에서의 최적 해답을 선택한다.
2. 적절성 검사
   • 선택된 해가 문제의 조건을 만족 하는지 검사한다.
3. 해답 검사
   • 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 선택절차로 돌아가 과정을 반복한다.

문제 성립 조건

• 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕 선택조건과, 최적 부분조건 두가지를 만족한다.
  • 탐욕 선택 조건 : 앞의 선택이 후에 영향을 주지 않는다는 것이다.
  • 최적 부분조건 : 문제에 대한 최적해가 부분문제에서도 최적해 라는 것이다.
• 문제 성립 조건을 만족하지 않더라도 탐욕 알고리즘은 근사 알고리즘으로도 사용이 가능하다. 대부분의 경우 계산 속도가 빠르기에 실용적으로 사용 가능하다.
• 특별한 구조가 있는 문제에서는 탐욕 알고리즘이 언제나 최적 알고리즘을 찾아낼 수 있다.

---

필기

• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
  • 그리디 알고리즘으로 문제를 해결했을 경우, 해법이 정당한지를 검토할 필요가 있다.
• 대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고, 정당한지를 검토해야한다.
• 문제풀이를 진행하는 과정 :
  • 유형파악이 어렵다 → 그리디 알고리즘을 의심 → 해결이 불가능 하다면 → DP, GRAPH 알고리즘을 통해 문제해결 접근

---

코드

• 백준 11047 / 동전 0

#https://www.acmicpc.net/problem/11047
#동전 0
#11047

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

coins = []
for _ in range(n):
    a = int(input())
    coins.append(a)

# print(coins)

coins.sort(reverse=True)

# print(coins)

def fun(k):

    cnt = 0

    for coin in coins:
        if coin <= k:
            count =  k // coin
            k = k % coin
            cnt = cnt + count
            # cnt += 1
    
    return cnt

answer = fun(k)
print(answer)

• 백준 1541 / 잃어버린 괄호

#https://www.acmicpc.net/problem/1541
#잃어버린 괄호
#1541

import sys
input = sys.stdin.readline

n_list = list(map(str, input().strip().split('-')))

# print(n_list)

def fun(n_list):

    result = 0

    for i in range(len(n_list)):
        plus_result = 0
        plus_list = []

        plus_list = n_list[i].split('+')
        # print(plus_list)

        for j in range(len(plus_list)):
            plus_result += int(plus_list[j])
        
        # print(plus_result)

        if i == 0:
            result += plus_result

        else:
            result -= plus_result

    return result

answer = fun(n_list)
print(answer)

---

참고자료

• 감사하신 홍정희 교수님의 강의자료
• https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188
• https://hanamon.kr/알고리즘-탐욕알고리즘-greedy-algorithm/