그리디 Greedy 알고리즘이란?
현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않고, 오직 현재 시점에서 가장 좋은 선택을 하는 알고리즘
ex) 대표적인 문제 : 백준 11047 동전 0
미래를 고려하지 않고 현재 내릴 수 있는 최선의 선택에만 집중하기 때문에
일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장하지는 않는다.
항상 최적의 해를 찾을거라는 보장은 없기 때문에 근사 알고리즘이라고도 한다.
코테에서 그리디 알고리즘 사용 가능한 조건?
코딩테스트에서는 최적 해가 보장되는 조건에서만 그리디 알고리즘을 사용해야 한다.
(보통 코테에서 그리디 문제는 이렇게 얻은 해가 최적의 해가 되는 상황으로 풀리도록 출제가 된다고 함)
- 현재의 선택이 미래의 선택에 영향을 주지 않을 때
- 부분의 최적 해가 모이면 전체의 최적 해가 될 때 (최적 부분 구조 조건 Optimal Structure)
단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토
그리디 전략?
기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에 '가장 큰 순서대로' '가장 작은 순서대로' 같은 기준을 제시해준다.
따라서 정렬이 중요.
어떻게 정렬해야 미래의 선택은 따져보지 않고 현재만 고려해도 최적의 해를 구할 수 있을 지 고민해야.
ex) 백준 1931 회의실 배정
추천 문제
silver : 2839 설탕배달, 11399 ATM, 11047 동전 0, 1541 잃어버린 괄호, 1931 회의실 배정
gold : 11000 강의실 배정, 1715 카드 정렬하기, 1339 단어 수학, 1744 수 묶기, 1202 보석 도둑
참고 :
- 개발자로 취직하기 youtube
'Algorithm > 자료구조 알고리즘' 카테고리의 다른 글
| [Swift 알고리즘] 백준 7568 덩치 (0) | 2024.08.12 |
|---|---|
| [알고리즘] 투 포인터 Two Pointers (0) | 2023.09.11 |
| [알고리즘] 누적 합, 구간 합 Prefix Sum (0) | 2023.04.07 |
| [알고리즘] Binary Search 이분탐색 (0) | 2022.12.31 |
| 알고리즘 시간복잡도 분석 (0) | 2022.12.15 |