자료구조&알고리즘
[알고리즘] 그리디 알고리즘 (탐욕법)
지윤공원🌳
2021. 3. 22. 01:26
728x90
그리디 알고리즘
그리디 알고리즘은 한국어로 하면 탐욕법이라는 뜻이다.순간마다 최적이라고 생각되는 선택을 하는 방식으로 진행하여 최종 답에 도달하는 문제 해결 방식이다.
1. 500, 100, 50, 10원 동전으로 거스름돈 주는 법
동전의 개수가 최소가 되도록 했을 때, 몇 개의 동전이 필요한지 구하는 문제이다.
money = int(input(""))
cnt = 0
arr = [500, 100, 50, 10]
for a in arr:
cnt += money // a
money %= a
print(cnt)2. 1이 될때까지
N이 K로 나누어 떨어지면 N을 K로 나누고, 그렇지 않으면 1씩 뺀다.
1이 될 때까지 몇 번의 연산이 필요한지 구하는 문제이다.
N, K = map(int, input("").split())
cnt = 0
while N != 1:
if N % K == 0:
N = N / K
else:
N = N - 1
cnt += 1
print(cnt)3. 더하기 혹은 곱하기
숫자로 된 문자열이 입력되면 순서대로 연산을 하는데, +와 *연산자만 사용할 수 있다.
어떻게 해야 가장 큰 수가 결과로 나오게 할까
nums = input("")
result = int(nums[0])
for i in range(1, len(result)):
num = int(nums[i])
if num <= 1 or result <= 1:
result += num
else:
result *= num
print(result)4. 모험가 길드
공포지수가 N인 사람은 N명과 팀을 이뤄야 한다는 규칙에 맞춰 몇 개의 팀이 이뤄지는지 구하는 문제이다.
num = int(input(""))
person = list(map(int, input("").split()))
person.sort()
result, cnt = 0
for p in person:
cnt += 1
if cnt >= p:
result += 1
cnt = 0
print(result)
728x90