[TIL] Algorithm - Greedy 기본 문제 풀이

1. 그리디 알고리즘 (탐욕 알고리즘)

항상 각 단계에 있어서 가장 좋을 거라 생각되는 선택을 한다.
이 선택이 전체적으로 최적해로 안내하게 될 거라는 바람을 가지고 부분적으로 최적인 선택을 한다.
언제나 최적의 해답을 구하지는 못하지만 많은 문제에 대한 해를 구해줄 수 있다.

1. 11047번 - 동전 0

import sys

N, K = map(int, sys.stdin.readline().split())
# 오름차순으로 입력을 받는다.
coin = [int(sys.stdin.readline()) for _ in range(N)]

count = 0
# 동전의 가치가 가장 큰 동전부터 반복 시작
for i in range(N-1, -1, -1) :
    if K == 0 :
        break
    # 현재 K보다 작은 수 중 가장 큰 수를 선택하여 계산
    if coin[i] <= K :
        count += K//coin[i]
        K %= coin[i]

print(count)

현재 우리가 만들어야 할 돈의 가치 K를 가지고 최소의 동전 수를 구해야 한다.
그리디 알고리즘은 각 상황마다 최적의 선택을 하면된다.
여기서 최적의 선택은 K보다 작은 값 중에서 가장 큰 값을 선택하면 사용되는 동전의 개수는 작아질 수 밖에 없다.
그러므로 입력받은 동전을 큰 값부터 차례로 살펴보면서 K보다 작은 값이 나오는 순간 계산을 해주도록 했다.

---

2. 1541번 - 잃어버린 괄호

import sys

s = sys.stdin.readline().strip()

# 식의 값을 최소로 만들기 위해서는 - 빼기가 나중에 되어야한다.
# 즉, +를 먼저 하고 나중에 -를 해야하므로 - 를 기준으로 나눈다.
minus = s.split('-')

result = 0
for i in range(len(minus)) :
    plus = minus[i].split('+')
    tmp = int(plus[0])
    if len(plus) > 1 :
        plus = list(map(int, plus))
        tmp = sum(plus)
    # 첫 값일 경우 빼주면 안된다.
    if i == 0 :
        result += tmp
    else :
        result -= tmp

print(result)

당연히 연산 결과가 최소가 되려면 더하기와 빼기 중 빼기를 나중에 해서 큰 수를 빼면 작아질 확률이 높다.
그러므로 우선 - 를 기준으로 문자열을 분할하고 각 요소별로 먼저 덧셈 계산을 한 후 결과값에 빼주도록 한다.

원하는 결과

import sys

s = sys.stdin.readline().strip()

minus = s.split('-')

result = sum(list(map(int,minus[0].split('+'))))
for i in range(1, len(minus)) :
    result -= sum(list(map(int,minus[i].split('+'))))

print(result)

생각해보니 파이썬을 가지고 구현 중인데 너무 코드가 길게 나와서 줄일 수 있을 것같아 줄여봤다.
확실히 반복문 안의 조건문도 빼고 한줄에 작성하니 코드가 많이 짧아지고 속도도 빨라졌다.