[algorithm] 그리디 알고리즘

01.그리디 알고리즘

• 그리디 알고리즘(탐욕법) 은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다.
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.
• 그리디 해법은 그 정당성 분석이 중요합니다.
  • 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.
• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다
• 코테에서 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.

<문제> 거스름 돈

n = 1260
count = 0

array = [500, 100, 50, 10]
for coin in array:
  count += n // coin
  n %= coin

print(count)

<문제> 1이 될 때까지

def solution(n, k):
  count = 0
  while n != 1:
    if n % k == 0:
      n = n // k
    else:
      n -= 1
    count += 1
  return count


print(solution(10, 3))
print(solution(17, 3))
print(solution(25, 5))

<문제> 더하기 혹은 곱하기

# 내풀이
def solution(s: str):

    s = list(s)
    while len(s) != 1:
        ff, ss = s.pop(0), s.pop(0)

        if ff in ["0", "1"] or ss in ["0", "1"]:
            temp = int(ff) + int(ss)
        else:
            temp = int(ff) * int(ss)

        s.insert(0, str(temp))
    return int(s[0])

# 다른 풀이
def solution(s):
    result = int(s[0])
    for i in range(1, len(s)):
        num = int(s[i])
        if num <= 1 or result <= 1:
            result += num
        else:
            result *= num
    return result


print(solution("02984"))
print(solution("567"))

<문제> 모험가 길드

# 내 풀이
def solution(fears: list[int]):
    fears.sort(reverse=True)

    count = 0
    while fears:
        num = fears[0]
        for _ in range(num):
            fears.pop(0)
        count += 1
    return count
print(solution([2, 3, 1, 2, 2]))

# 영상 풀이
n = int(input())
data = list(map(int, input().split()))
data.sort()  

result = 0  # 총 그룹의 수
count = 0  # 현재 그룹에 포함된 모험가의 수
for i in data:  # 공포도가 낮은것부터 하나씩 확인
  count += 1
  if count >= i:
    result += 1
    count = 0
print(result)