앞으로 코딩테스트를 준비하며 공부하는 알고리즘 유형에 대해서 정리를 해보고, 관련된 문제들을 정리해보려고 한다.
1. 그리디 알고리즘이란?
그리디 알고리즘이란 말그대로 Greedy(탐욕)이라는 이름 그대로 지금 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘이다.
일반적인 그리디 알고리즘은 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
→ 그리디 알고리즘의 해법은 정당성 분석, 최적의 해를 구할 수 있는지 검토하는 것이 중요하다.
일반적인 상황에서는 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많지만, 코딩테스트는 그리디 알고리즘을 활용해서 만들어질 수 있도록 문제를 출제하므로 OK 인것.
2. 그리디 알고리즘 예시 (이코테 내용 정리)
가장 대표적인 예시로는 거스름돈 예시가 있다.
최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러주면 되기 때문이다.
(100원 5개와 500원 1개를 비교해보자, 동전의 최소 개수를 위해서는 큰 단위부터 주는 것이 가장 효율적이다.)
정당성 분석이 매우 중요하다.
3. 주의점
그리디 알고리즘은 만족하는 적합한 해를 찾는 방법이지 최적의 해를 찾는 방법은 아니다.
최적의 해를 찾기 위해서는 동적계획법(Dynamic Programming)을 사용한다.
4. 문제 추천
: 해당 문제들에 대해서는 나도 풀면서 풀이를 정리해보고자 한다.
[참고자료]
'CS 공부 > 알고리즘' 카테고리의 다른 글
| 해시(Hash) 란? (0) | 2021.09.07 |
|---|---|
| C++ 알고리즘 문제풀이하며 자주 쓰이는 라이브러리, 함수 정리 (0) | 2021.09.07 |
| 불안정 정렬 sort, 안정정력 stable_sort (0) | 2021.09.03 |