✅ 그리디
- 매 순간 가장 좋아 보이는 선택을 함 → 최적의 해가 아닐 수도 있음
- 특정 조건이 만족하는 경우 최적해를 보장함
- 최적해를 보장하는 경우에만 사용해야 함
✅ 최적해를 보장하기 위한 특성
- 탐욕적 선택 속성
- 각 단계에서 가장 좋은 것을 선택한다는 것이 전체 문제 최적해가 됨
- 최적 부분 구조
- 부분 문제의 최적해로 전체 문제의 최적해를 구성할 수 있음
✅ 예시 1 : 거스름돈 문제 ( 그리디로 풀리는 경우)
- 문제 : 4원,2원,1원의 화폐 단위로 13원을 거슬러 줘야 할 때, 가장 적은 동전 개수로 거슬러 주는 방법은?
- 접근 방법
- 가장 적은 동전 개수를 위해서 화폐가 큰 동전부터 최대한 활용하자
- 4원, 4원, 4원, 1원 = 13원 , 동전 4개 사용
✅ 예시 2 : 거스름돈 문제 ( 그리디로 풀리지 않는 경우)
- 문제 : 5원, 4원, 1원인 경우, 8원을 거슬러 줘야 할 때 가장 적은 동전 개수로 거슬러 주는 방법은?
- 접근 방법
- 위와 똑같이 큰 단위 화폐부터 최대한 활용한다.
- 큰 화폐부터 거슬러 주는 경우 : 5원, 1원, 1원, 1원 → 4개. 하지만 최적해가 아니다.
- 4원짜리 2개를 거슬러 주면 동전 2개만 사용하게 됨.
☑️ 거스름돈 문제 정리
- 단위가 큰 화폐부터 돈을 거슬러 주는 경우
- 각 화폐간 단위가 배수관계인경우 (예를 들어 1,2,4 원), 4원은 2원의 조합으로, 2원은 1원의 조합으로 만들 수 있다. 즉 앞의 동전을 최대한 사용해도 뒤의 동전 사용에 영향을 미치지 않는다.
- 그리디로 최적해 보장 ⭕
- 배수 관계가 아닌 경우 (5원, 4원, 1원) 5원을 최대한 사용해서 거슬러줬을 때 4원을 사용하지 못하는 경우가 발생. 즉 이후 동전선택에 영향을 미치게 된다.
- 그리디적으로 최적해 보장 ❌
- 각 화폐간 단위가 배수관계인경우 (예를 들어 1,2,4 원), 4원은 2원의 조합으로, 2원은 1원의 조합으로 만들 수 있다. 즉 앞의 동전을 최대한 사용해도 뒤의 동전 사용에 영향을 미치지 않는다.
✅ 예시 2 : 최소 신장 트리(MST)
- 신장트리란?
- 모든 정점이 간선으로 연결되어 있고, 간선 개수가 정점 개수보다 하나 적은 그래
- 최소신장트리란?
- 신장트리 중 가중치의 합이 최소인 것
- 최소신장트리 구하기 (프림 알고리즘)
- 임의 정점 하나 최소신장트리에 추가
- 최소신장트리로 연결된 정점 중 가장 가중치가 적은 정점을 최소신장트리에 추가, 단 순환을 형성하지 않아야 함
- 과정 2를 신장 트리 조건 만족할 때 까지 반복
💡코딩테스트에 나오는 그리디 패턴
- 매 순간 가장 좋은 선택을 하면서 해결되는 경우
- 최소 신장 트리
- 최단 경로 문제 (다익스트라에서 사용, 벨만포드는 아님)
- 특정 조건을 만족하면서 가장 최대/최소값을 찾는 경우
- 부분 배낭 문제 (0/1 배낭은 그리디 아님)
- 스케쥴링 문제
[참고 강의]
코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]
[참고 도서]
코딩테스트 합격자 되기 - 파이썬 편