728x90
Greedy Algorithm (그리디 알고리즘)
: 현재 상황에서 지금 당장 좋은 것만 고르는 방법
그리디 알고리즘의 특징
- 그리디 알고리즘 유형 문제는 매우 다양하기 때문에 많은 유형을 풀어봐야 한다!
- 현재 상황에서 가장 좋은 것만 선택해도 문제가 해결되는지 파악한 후, 적용한다
- 보통 코딩 테스트에서 문제를 풀기 위한 최소 아이디어를 떠올릴 능력을 요구하는 문제이다
* 기준에 따라 좋은 것을 선택하므로 문제에서 '가장 큰 순서대로' 같은 기준을 알게 모르게 제시한다
* 자주 정렬 알고리즘(기준을 만족시킬 수 있음)과 짝을 이뤄 출제
그리디 알고리즘의 정당성
- 정확한 답을 구할 수 있다는 보장이 있을 때, 매우 효과적이고 직관적인 알고리즘이다
- 그 해법이 정당한지 검토할 수 있어야 한다
간단한 예제
- [문제] 500, 100, 50, 10원짜리 동전으로 N원을 줄 때, 동전의 최소 개수
- '가장 큰 화폐 단위부터' 돈을 거슬러준다 (500 -> 100 -> 50 -> 10)
- 동전의 단위가 서로 배수 형태
- 화폐의 단위가 무작위일 경우, 다이나믹 프로그래밍으로 해결 가능하다
📚 참고서적 : 이것이 코딩테스트다 with 파이썬
728x90
'Computer Science > Algorithm' 카테고리의 다른 글
[Algorithm] 리스트 컴프리헨션 (List Comprehension) (0) | 2021.09.01 |
---|---|
[Algorithm] 구현 문제 (Implementation) with 방향 이동(dx, dy) (0) | 2021.09.01 |
[Algorithm] 내가 보려고 정리하는 '이것이 취업을 위한 코딩 테스트다' (0) | 2021.09.01 |
[Algorithm] 자료구조 - 그래프 (Graph) (0) | 2021.03.25 |
[Algorithm] 자료구조 - 해시 테이블 (Hash table) (0) | 2021.03.25 |