패스트캠퍼스 온라인 강의

Part1.Ch04-01. 그리디 알고리즘 이해하기

탐욕알고리즘

• 당장 가장 좋아 보이는 상황만을 선택하는 알고리즘이다.
• 최적 해에 근사한 값을 구할 경우 사용된다.
• 코테에서 난이도가 낮은 문제로 나온다.

• 매 상황에서 단순히 가장 큰 노드를 선택하는 경우 ? (정답이라고는 할 수 없음. 최적해를 보장하지는 않지만 시간복잡도는 효율적이다. 최적해에 가까운 답일 것이다. )

• 코딩테스트에서는 최적 해임이 보장되는 문제가 출제된다.

탐욕 알고리즘 접근 방법

1. 방법 고안하기 : 현재 상황에서 어떤 것을 선택할지 알고리즘을 고안
2. 정당성 확인하기 : 자신이 고안한 알고리즘이 항상 최적 해를 보장하는지 확인 (증명)

예시: 거스름 돈 문제

• 가장 큰 화폐 단위부터 거슬러 준다.
• 500원 -> 100원 -> 50원 -> 10원

정당성 분석

• 화폐단위가 배수 관계이기 때문에 최적의 해를 찾을 수 있다.