[그리디] CHAPTER 03 그리디 (p. 86~102)
<이것이 취업을 위한 코딩테스트다 with 파이썬> 책의 내용을 정리한 것입니다.
그리디(Greedy) 알고리즘은 어떤 문제가 있을 때, 단순히 지금 당장 좋은 것만 골라서 답을 찾는 방식이다.
현재의 선택에서 가장 좋은 것을 선택하므로, 현재의 선택이 나중에 미칠 영향은 고려하지 않습니다.
따라서 100% 최적의 답을 찾는다고 보장할 수는 없습니다.
보통, '가장 큰/작은 순서대로' 와 같이 문제에서 기준을 제시해주는 경우 사용하면 좋습니다.
대표적인 예로는 거스름돈을 거슬러 주는 경우, 최소한의 동전의 개수를 구하는 문제에 사용됩니다.
그리디 알고리즘으로 해결이 안된다면, 다이나믹 프로그래밍이나, 그래프 알고리즘으로 문제를 해결해보는 생각을 가져야 합니다.
[예제 2] 큰 수의 법칙
https://darongrong.tistory.com/146
[그리디] 02 큰 수의 법칙
책의 예제 문제에 대한 제 답안을 작성한 게시글 입니다.CHATER 03: 그리디P. 92제출 코드N, M, K = map(int, input().split())number_list = list(map(int, input().split()))number_list.sort(reverse=True)# 반복되는 묶음의 개수se
darongrong.tistory.com
[예제 3] 숫자 카드 게임
https://darongrong.tistory.com/147
[그리디] 03 숫자 카드 게임
책의 예제 문제에 대한 제 답안을 작성한 게시글 입니다.CHATER 03 그리디P.96내 코드N, M = map(int, input().split())min_card = []for i in range(N): cards = list(map(int, input().split())) min_card.append(min(cards))min_card.sort(rev
darongrong.tistory.com
[예제 4] 1이 될 때까지
https://darongrong.tistory.com/manage/posts/
티스토리
좀 아는 블로거들의 유용한 이야기, 티스토리. 블로그, 포트폴리오, 웹사이트까지 티스토리에서 나를 표현해 보세요.
www.tistory.com