그리디 알고리즘이란?
현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그리디 해법은 그 정당성 분석이 중요한데, 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.
일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
하지만 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.
그리디 알고리즘 예제 1 <거스름 돈>
# 줘야 할 거스름돈
n = 1260
count = 0
# 가지고있는 동전종류
array = [500, 100, 50, 10]
# 배열에 있는 동전별로 반복문 시작
for coin in array:
# 거스름돈에서 동전을 나눈 몫을 카운트에 담는다
count += n // coin
# 나머지값을 받아서 다시 반복문을 돈다.
n %= coin
print(count)그리디 알고리즘 예제 2 <1이 될때까지>
- n, k를 입력받고 n에서 1을 빼거나, n에서 k를 나누는 두 가지 식만 활용하여 최소 횟수로 1을 만드시오.
# n과 k를 공백을 기준으로 입력받는다
n, k = map(int, input(),split())
# 연산횟수
result = 0
while True:
# k로 나누어떨어지는 수중 가장 가까운 수를 찾게된다.
target = (n // k) * k
# 기존 n값에서 타겟값을 빼주면 그 수만큼 -1 연산을 한 것이기때문에 result에 담는다.
result += (n - target)
n = target
if n < k:
break
# 아직 n이 크기때문에 횟수 1을 추가하고 나눗셈 연산 수행
result += 1
n //= k
# 더이상 나눗셈 연산 불가, 남은 뺄셈연산 횟수를 찾는다
result += (n-1)
print(result)그리디 알고리즘 예제 3 <곱하기 혹은 더하기>
- 임의의 숫자를 입력받고 그 숫자들끼리 +, *를 이용하여 가장 큰 수를 만들어라. 대수학의 사칙연산 우선순위는 무시하고 왼쪽부터 연산이 이뤄진다.
# 임의의 여러 숫자 입력
data = input()
# 첫번째 숫자를 결과에 넣기
result = int(data[0])
for i in range(1, len(data))
num = int(data[i])
# 들어갈 num과 들어가있는 result 둘 중 하나라도 0,1이면 +수행
if num <= 1 or result <= 1:
result += num
else:
result *= num
print(result)그리디 알고리즘 예제 4 <모험가길드>
- 모험가 길드에서 여행을 떠날때 그룹을 지어서 떠나야 하는데, 최대한 많은 그룹을 만들고 싶다. 각 모험가들은 공포도를 가지고 있으며 모험가의 공포도가 x이면 x명이 존재하는 그룹에 속해야만 출발할 수 있다. 최대로 만들어지는 그룹의 갯수를 찾아라
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) # 총 그룹 수 출력 
🔥 Feelings fade, results remain