목록작업 스케출링 알고리즘 (1)

YJ_Scribbles

그리디 알고리즘

★ 그리디 알고리즘 - 최적화 문제를 해결하는 알고리즘 - 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림 ☆ 종류 1. 동전 거스름돈 문제 2. 최소 신장 트리 3. Dijkstra(다익스트라) 최단 경로 4. 부분 배낭 문제 5. 집합 커버 문제 6. 작업 스케줄링 문제 ★ 배낭 문제 - 최대의 가치를 갖도록 배낭에 넣을 물건들은 정하는 문제 (-> n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 경우) ☆ 부분 배낭 (Fractional Knapsack) 문제 - 물건을 부분적으로 담는 것을 허용 - 그리디 알고리즘으로 해결 ☆ 0-1 배낭 문제 (0/1 배낭 문제) - 부분 배낭 문제의 원형으로 물건을 통째로 배낭에 넣어야 함 -..
이론_전공/알고리즘 2020. 11. 9. 21:43
이전 Prev 1 Next 다음