Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
Greedy 알고리즘
Greedy : 탐욕 알고리즘
현재 상황에서 가장 좋은 선택지를 고르는 방법
※ 현재의 선택이 나중에 미칠 영향은 고려하지 않는다.
- 적용 예시: 최단 경로 선택( 플로이도 워셜, 다익스트라 알고리즘)
가장 큰 순서대로같은 기준이 있는 경우 적용- 그리디 알고리즘을 문제에 적용하여 푼 후, 문제를 해결하는 아이디어가 정당한지 검토할 수 있어야 한다.
[예시 1] 거스름돈 문제
- 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재할 때 손님에게 거슬러 줘야할 돈이 n원인 경우 거슬러줘야 할 동전의 최소 개수 구하기
-
해결 방식: 가장 큰 화폐 단위부터 돈을 거슬러 준다.
n = 1260 count = 0 coin_types = [500,100,50,10] for coin in coin_types: count += n // coin n %= coin print(count)
[예시 2] 큰 수의 법칙
- 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙
- 배열의 특정 인덱스에 해당하는 수가 연속으로 k번을 초과하여 더해질 수 없다.
- 입력: 배열의 크기 N, 더하는 횟수 M, 최대 연속 횟수 K
-
해결 방식: 배열 중 가장 큰 순서대로 k번씩 더한다.
# 입력 N, M, K = map(int, input().split()) data = list(map(int, input().split())) # 정렬 data.sort() first = data[N-1] second = data[N-2] # 결과 계산 result = 0 while True: for i in range(K): if M==0: break result += first M-=1 if M==0: break result += second M-=1 print(result)
[그리디와 동적 프로그래밍의 차이]
- 동적 프로그래밍: 단계마다 선택 한다. 이때, 선택은 부분문제 해에 의존한다.
- 그리디 알고리즘: 현재 가장 최적인 선택을 하고 이후 생기는 부분 문제를 푼다.
