공부/자료 구조 및 알고리즘
2019. 7. 21.
알고리즘 기법[부분 탐색] - 탐욕적 방법(Greedy method)
탐욕적 방법(Greedy method) 전체 문제가 여러 단계로 구성되어 있는 경우에 각 단계별로 최적 해를 구함으로써 전체 문제를 해결하려는 알고리즘 설계 방법. -수학적으로 탐색 영역을 배제함. -문제를 해결하기 위해서 해가 될 수 있는 모든 부분(전체적 최적화)을 탐색하는 것이 아니라, 탐색할 부분을 제한(부분적 최적해하여 원하는 해를 구하는 방법. -전체적 최적화에 도달하지 못하는 경우가 있을 수 있음. -올바른 해를 구하기 위해 탐색을 배제한 부분에 대한 수학적 검증이 필요. Greedy 예시 및 알고리즘 1. CPU 스케줄링(scheduling) 문제 선점을 허용하지 않는 하나의 CPU와 n개의 작업이 있을 때 CPU 스케줄링은 작업 시간의 크기를 기준으로 오름차순 정렬하여 작업 시간이 가장 ..
![알고리즘 기법[부분 탐색] - 탐욕적 방법(Greedy method)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/bCutbr/btqwVf7RSEx/4uVSXkNKFV76IPMhHx53B0/img.png)