Algorithm
2003.04.23 11:08
[algorithm] Greedy (탐욕 기법)
조회 수 15163 댓글 0
◈ 탐욕 기법
탐욕 기법이란?
- 최적화 문제를 푸는 한가지 방법 (다른 방법도 있는가?)
- 과거나 미래는 생각하지 않고, 오직 현재의 최대 만족만을 추구 (그래서 "greedy"임)
- 입력에 대하여 단계별로 진행하며, 각 단계에서는 현재 최적이라고 판단되는 결정을 한다. (전체적으로 최적인지는 판단하지 않는다.)
- 따라서 문제에 따라 최적해 또는 근사해를 구하게 된다.
- 전체를 고려치 않고 현재만을 생각하므로 비교적 간단히 구현되며 알고리즘을 이해하기 쉽다.
탐욕 기법의 개략적 구조(control abstraction)
greedy (int n , A [ ]) {
solution = 0;
for ( i =1; i <= n ; i ++) {
x = select (A );
if (feasible (solution , x )) solution = UNION (solution , x );
}
return solution ;
}
탐욕 기법의 구성
- 탐욕 기법은 다음의 부분들로 구성되어 있다.
(1) 선택하기: 현재 상태에서 최적의 해를 구하는 부분
(2) 점검하기: 구해진 해가 주어진 문제의 조건을 만족하는지 검사하는 부분
(3) 종료하기: 원래의 문제가 모두 해결되었는지를 검사하는 부분
동전 거슬러 주기
- 문제: 가게에서 거스름 돈을 100원, 50원, 10원, 5원, 1원짜리 동전들로 거슬러 주고자 한다.
- 제약 조건: 손님들은 동전을 많이 받아 가기를 원하지 않는다.
- 탐욕 기법에 의한 해결: 87원 만들기
단계 1: 100원을 선택 (선택하기) → 87원 보다 많으므로 선택을 물림 (점검하기)
단계 2: 50원을 선택 (선택하기) → 87원 보다 적으므로 선택을 인정 (점검하기) → 이제 남은 돈은 37원
단계 3: 다시 50원을 선택 (선택하기) → 37원 보다 많으므로 선택을 물림 (점검하기)
단계 4: 10원을 선택 (선택하기) → 37원 보다 적으므로 선택을 인정 (점검하기) → 이제 남은 돈은 27원
단계 5: 다시 10원을 선택 (선택하기) → 27원 보다 적으므로 선택을 인정 (점검하기) → 이제 남은 돈은 17원
단계 6: 다시 10원을 선택 (선택하기) → 17원 보다 적으므로 선택을 인정 (점검하기) → 이제 남은 돈은 7원
단계 7: 다시 10원을 선택 (선택하기) → 7원 보다 많으므로 선택을 물림 (점검하기)
단계 8: 5원을 선택 (선택하기) → 7원 보다 적으므로 선택을 인정 (점검하기) → 이제 남은 돈은 2원
단계 9: 다시 5원을 선택 (선택하기) → 2원 보다 많으므로 선택을 물림 (점검하기)
단계 8: 1원을 선택 (선택하기) → 2원 보다 적으므로 선택을 인정 (점검하기) → 이제 남은 돈은 1원
단계 8: 다시 1원을 선택 (선택하기) → 1원과 같으므로 선택을 인정 (점검하기) → 이제 남은 돈은 0원 → 남은 돈은 0원이므로 알고리즘 끝 (종료하기)
동전 거슬러 주기를 통해서 본 탐욕 기법
- 단계별로 진행: 한 단계에서 하나의 동전을 포함.
- 선택 방법: 각 단계에서 가능한 최대의 동전을 선택하고자 시도
- 적합성 검사: 남은 돈을 넘는가를 점검
- 종료 검사: 남은 돈이 0원이면 종료.
번호 | 분류 | 제목 | 글쓴이 | 날짜 | 조회 수 |
---|---|---|---|---|---|
1017 | Develop |
[ios] 기본 네비게이션바의 타이틀, back버튼 위치와 속성 변경
![]() |
hooni | 2016.05.16 | 2186 |
1016 | Develop |
[ios] UUID 생성 + Key Chain 연동
![]() |
hooni | 2016.05.13 | 4771 |
1015 | Develop |
[c#] 전자금융보안론 발표/설치 자료(툴바 소스코드)
![]() |
hooni | 2016.05.07 | 0 |
1014 | PPT |
[ppt] 전자금융보안론 발표/설치 자료
![]() |
hooni | 2016.05.03 | 1439 |
1013 | Develop |
XE Core 1.8.18 본문 작성시 태그(html) 사라지는 버그
![]() |
hooni | 2016.04.21 | 1015 |
1012 | Develop | [io] Apple Watch, Today Extension 앱ID 설정 | hooni | 2016.04.20 | 928 |
1011 | Develop | [ios] Did UIScrollView End Scrolling? | hooni | 2016.04.19 | 1165 |
1010 | Develop |
[ios] How To Use UIScrollView to Scroll and Zoom Content (Using Swift)
![]() |
hooni | 2016.03.23 | 7633 |
1009 | Develop |
[ios] How To Use UIScrollView to Scroll and Zoom Content (Using Objective-C)
![]() |
hooni | 2016.03.23 | 1749 |
1008 | Develop |
[js] AngularJS 란?
![]() |
hooni | 2015.11.26 | 1019 |
1007 | PPT |
[ppt] OCB기술개발팀 OJT 자료
![]() |
hooni | 2015.11.13 | 1261 |
1006 | Develop | [php] 한글 문자열 자르기 (utf-8) | hooni | 2015.11.10 | 1449 |