본문 바로가기

부분탐색

알고리즘 기법[부분 탐색] - 분기 한정(Branch & Bound)
공부/자료 구조 및 알고리즘 2019. 7. 22. 알고리즘 기법[부분 탐색] - 분기 한정(Branch & Bound) 분기 한정(Branch & Bound) 분기: branch, 한정: bound →분기를 한정시켜 쓸데없는 시간 낭비를 줄이는 방법 백트래킹에서 부가적으로 발생한 알고리즘 설계 기법 백트래킹이 허용되는 탐색에서 더 이상 탐색할 필요가 없는 지점을 판단하는 것. -비선형 구조의 탐색 과정에서 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀 -탐색과정에서 더 이상 의미가 없다고 판단되는 데이터에 대해서는 더 이상 탐색하지 않고 백트래킹함. -나무에서 필요없는 가지를 잘라내는 가지치기와 유사하여 가지치기 기법이라고도 함. 만약 2번에서 3번으로 진행하려고 할 때, 3번 이하의 모든 노드를 더 이상 탐색할 필요가 없다고 판단할 경우, 이하의 탐색을 중단하고 9번으로 진행할 수 있다. 위 그림은 더 이상 탐..
알고리즘 기법[부분 탐색] - 탐욕적 방법(Greedy method)
공부/자료 구조 및 알고리즘 2019. 7. 21. 알고리즘 기법[부분 탐색] - 탐욕적 방법(Greedy method) 탐욕적 방법(Greedy method) 전체 문제가 여러 단계로 구성되어 있는 경우에 각 단계별로 최적 해를 구함으로써 전체 문제를 해결하려는 알고리즘 설계 방법. -수학적으로 탐색 영역을 배제함. -문제를 해결하기 위해서 해가 될 수 있는 모든 부분(전체적 최적화)을 탐색하는 것이 아니라, 탐색할 부분을 제한(부분적 최적해하여 원하는 해를 구하는 방법. -전체적 최적화에 도달하지 못하는 경우가 있을 수 있음. -올바른 해를 구하기 위해 탐색을 배제한 부분에 대한 수학적 검증이 필요. Greedy 예시 및 알고리즘 1. CPU 스케줄링(scheduling) 문제 선점을 허용하지 않는 하나의 CPU와 n개의 작업이 있을 때 CPU 스케줄링은 작업 시간의 크기를 기준으로 오름차순 정렬하여 작업 시간이 가장 ..

티스토리툴바