반응형
[C언어 알고리즘] 7. 탐욕(Greedy) 알고리즘
탐욕(Greedy) 알고리즘은 커다란 문제를 해결하기 위해 여러 단계를 나누어 해결하는 알고리즘의 하나입니다. 동적 알고리즘에서는 현 단계에서 다음 단계로 갈 수 있는 모든 경험을 수행하면서 문제를 해결하였습니다. 하지만 탐욕 알고리즘은 현 단계에서 갈 수 있는 다음 단계들 중에 최적이라고 판단하는 하나의 단계만 수행합니다. 따라서 현 단계에서 다음 단계로 갈 수 있는 모든 경험 중에 무엇을 선택할 것인지 결정하는 것이 중요합니다.
그런데 매 순간 최적이라고 판단하는 다음 단계를 선택하면서 전체 문제를 해결하였을 때 이 해결 방법이 전체 문제에 최적일 수도 있지만 최적이 아닐 수도 있습니다. 따라서 가치있는 탐욕 알고리즘은 매 순간 최적이라고 판단하면서 다음 단계로 진행하면서 문제를 해결하였을 때 전체 문제도 최적임을 증명할 수 있어야 합니다.
여기에서는 매 순간 최적의 선택을 하였을 때 전체 문제도 최적으로 해결할 수 있음을 증명한 몇 개의 알고리즘을 소개할게요. 첫 번째 알고리즘은 최소 개수의 거스름 돈을 계산하는 알고리즘이고 두 번째는 길이가 다른 노래를 테이프에 기록하고 맨 앞에서부터 원하는 노래를 찾고자 할 때 평균 탐색 비용을 최소로 하기 위해 기록하는 알고리즘입니다. 그리고 마지막으로 최소 신장 트리를 만들 때 사용하는 프림과 크루스칼 알고리즘입니다.
[C언어 알고리즘] 7.2 SJF(Shortest Job First) 알고리즘
[C언어 알고리즘] 7.3 프림(Prim) 알고리즘(최소신장트리 알고리즘)
[C언어 알고리즘] 7.4 크루스칼(Kruskal) 알고리즘(최소신장트리 알고리즘)
반응형
'언어 자료구조 알고리즘 > 디딤돌 알고리즘 (C언어)' 카테고리의 다른 글
[C언어 알고리즘] 7.3.1 프림 알고리즘에 맞게 그래프 소스 코드 수정 (0) | 2016.12.04 |
---|---|
[C언어 알고리즘] 7.3 프림(Prim) 알고리즘(최소신장트리 알고리즘) (0) | 2016.12.04 |
[C언어 알고리즘] 7.2 SJF(Shortest Job First) 알고리즘 (0) | 2016.12.04 |
[C언어 알고리즘] 7.1.1 거스름 돈 알고리즘 소스 코드 (0) | 2016.12.02 |
[C언어 알고리즘] 7.1 거스름 돈 알고리즘 (0) | 2016.12.02 |
[C언어 알고리즘] 6.2.8 깊이우선탐색(DFS) 알고리즘 소스 코드 (0) | 2016.12.01 |
[C언어 알고리즘] 6.2.7 깊이우선탐색(DFS) 알고리즘 테스트 코드 작성 (0) | 2016.12.01 |
[C언어 알고리즘] 6.2.6 깊이우선탐색(DFS) 알고리즘의 경험 정보 구현 (0) | 2016.12.01 |
[C언어 알고리즘] 6.2.5 깊이우선탐색(DFS) 알고리즘의 경험(Heuristic) 정보 설계 (0) | 2016.12.01 |
[C언어 알고리즘] 6.2.4 그래프 테스트 소스 코드 (0) | 2016.12.01 |