코딩 테스트를 위한 자료 구조와 알고리즘 with C++
탐욕법
- 매번 탐욕스럽게 현재 상황에서의 최적해를 선택하는 방법이다.
- 탐욕법의 해가 항상 최적해가 되는 것은 아니다.
다음의 두 가지를 만족하면 탐욕법을 통해 최적해를 구할 수 있다.
최적 부분 구조(Optimal Substructure): 문제 P의 최적해가 P의 부분 문제들의 최적해로 구성될 경우
탐욕 선택(Greedy Choice): 문제 P의 지역적 최적해를 반복적으로 선택해 전체 최적해를 구할 수 있는 경우
탐욕법의 예
- 다익스트라(Dijkstra) 알고리즘
지도에서의 최단 경로 계산 등 - 최단 작업 우선(SJF, Shortest Job First) 스케줄링
총 대기 시간 단축 등
'자료구조 & 알고리즘 > 코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 카테고리의 다른 글
| 서로소 집합(Disjoint Set) (0) | 2023.02.25 |
|---|---|
| 최단 작업 우선(SJF) 스케줄링 (0) | 2023.02.22 |
| 맵리듀스(MapReduce) (0) | 2023.02.21 |
| 분할 정복 관련 STL 함수들 (0) | 2023.02.20 |
| 병합 정렬(Merge Sort) (0) | 2023.02.17 |
