[알고리즘] 그리디 알고리즘

그리디 알고리즘; 욕심쟁이 알고리즘

: 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출.

 

5개의 도시를 모두 한번씩만 거쳐서 가장 짧은 경로 찾기

-> 지금 위치한 도시에서 고를 수 있는 가장 짧은 도시로 가기*반복

 

따라서, 매 순간에서는 최적이지만 종합적으로 봤을 땐 최적이라는 보장이 없음.

부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용 가능.

최적해/근사해(탐욕 알고리즘)

특징

탐욕 선택 속성 greedy choice property

; 매 선택이 독립.

최적 부분 구조 optimal substructure

; 문제의 최적 해결 방법==부분 문제에 대한 최적 해결 방법

 

최적해라는 보장은 없지만 빠른 경우가 많기 때문에 실용적으로 사용 가능.

"근사해" 구하는 목적

 

수행과정

1. 해 선택: 알고리즘 고안

2. 정당성 확인: 증명

 

예시

1. 거스름돈 문제

; 거스름돈 n원을 거슬러 주어야 할 때, 동전 개수의 최솟값은?

ex) 6480원일 때

500원 12개 (480원)

100원 4개 (80원)

50원 1개 (30원)

10원 3개 (0원)

 

거스름돈 문제가 그리디 알고리즘인 이유는 각 화폐 단위가 배수 관계에 속하기 때문.

만약 단위가 80원, 50원 이런 식이라면 그리디 알고리즘으로 해결X

 

2. Decision Tree

타이타닉 호 탑승객의 생존 여부를 나타내는 결정 트리. (sibsp는 탑승한 배우자와 자녀의 수를 의미)

지도 분류 학습 기법 중 하나

각 노드마다 질문을 던지고 그 응답에 따라 가지를 쳐서 데이터를 분리.(분리 후 각 노드의 불순도가 낮아지게끔)