현재 상황에서 지금 당장 좋은 것만 고르는 방법
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로', ‘가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘은 정렬 알고리즘과 자주 짝을 이뤄 출제된다.
대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
예제) 거스름돈 문제
n = 1260
count = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)
→ 화폐의 종류가 K개일 때 시간 복잡도는 O(K)
그리디 알고리즘을 사용하기 위해 필요한 조건!
def solution(n, lost, reserve):
_reserve = [r for r in reserve if r not in lost]
_lost = [l for l in lost if l not in reserve]
# 정렬 꼭 필요
_lost.sort()
_reserve.sort()
for r in _reserve:
f = r - 1
b = r + 1
if f in _lost:
_lost.remove(f)
elif b in _lost:
_lost.remove(b)
return n - len(_lost)
def solution(name):
answer = 0
changed = []
for c in name:
changed.append(min(ord(c)-ord('A'), ord('Z')-ord(c)+1))
idx = 0
while True:
answer += changed[idx]
changed[idx] = 0
if sum(changed) == 0:
break
left, right = 1, 1
while changed[idx-left] == 0:
left += 1
while changed[idx+right] == 0:
right += 1
if left <= right:
answer += left
idx -= left
else:
answer += right
idx += right
return answer
→ 아직 모든 테케를 통과하지 못했다 ㅠㅠ