그리디 알고리즘

그리디 알고리즘

• 그리디 알고리즘
  
  • 문제해결 단계마다 욕심을 부리며 가장 최고의 답을 선택하는 방법 ( = 탐욕적 문제결방식! )
  • 문제 상황에서 최선의 답을 선택 -> 선택마다 좋은 방법을 적용하여 최선을 해답을 찾아감 (근시안적)
  • 데이터 간의 관계를 고려하지 않음.
  • 수행 과정에서 우선적으로 최선인 답을 선택하므로 문제 전체로는 최적 방안이 아닐 수 있음.

 

• 적용되는 경우
  • 한 단계의 선택이 다음 선택에 전혀 무관하며 매 단계의 최적 방향이 문제 전체의 최적화로 이어질 때
  • 시간 / 공간적 제약으로 인해 최적의 문제해결을 찾기 어려운 경우, 최적 근삿값 찾고자 할때

 

• 설계절차
  • 선정 과정 : 현재 상태에서 가장 좋으리라 생각되는 해답을 찾아 해답 모음에 포함시킴
  • 적정성 점검 : 새로 얻는 해답 모음이 적절한지 결정
  • 해답 점검 : 새로 얻은 해답 모음이 최적의 해인지 결정

 

• 그리디 알고리즘과 최적화 해결책

문제 상황 (서울 -> 부산)	그리디 알고리즘	최적화 해결책

 

그리디 알고리즘이 적용되는 대표적인 문제.

• 최단 경로 찾기
  • 다익스트라 알고리즘(음수일 때는 적용X)
  • 가중치O 그래프에서 한 특정 정점(시작점)에서 다른 모든 정점으로까지 최단 경로를 구하는 문제(최소비용, 최소시간)

문제 예시		b	c	d	e	선택된 정점	결과
	a	3		7		b
	a, b	3	7	5		d
	a,b,d	3	7	5	9	c
	a,b,d,c,e	3	7	4	9	-

 

•  배낭문제
  • 최적화가 요구되는 문제
  • 무게는 한정되어있고, 가치는 최대로 해야함

문제			풀이과정
무게제한 10kg			1) 가치가 높은 순	2) 무게 당 가치	3) 분할가능으로 그리디 적
itme	wight	value	E + A + B w : 3.5 + 4 + 2.5 = 10 v : 70 + 52 + 25 = 147	A : 13 B : 10 C : 8 D : 15 E : 20 F : 8 E + D + A + B  w :  3.5 + 1 + 4 + 2.5 = 11  무게초과로 B <-> F E + D + A + F w:  3.5 + 1 + 4 + 1.5 = 10 v : 70+ 15+52+12 = 149	① 무게당 가치가 높은 E 선택 ② 차례대로 D, A 선택 = w : 3.5 + 1 + 4 = 8.5kg ③ 네번째로 가치가 높은 B에서 1.5kg에 해당하는 15의 가치 (60%) 만 챙김 총 가치 70 + 15 + 52 + 15 = 152
A	4	52
B	2.5	25
C	3	24
D	1	15
E	3.5	70
F	1.5	12