-
2021.06.25
0-1 배낭 문제(0-1 Knapsack Problem)
0-1 배낭 문제(0-1 Knapsack Problem) 조건 물건들의 집합 O = {O₁, O₂, ..., On}이 있을 경우 Wi : i번째 물건 Oi의 무게 Vi : i번째 물건의 가격(Value) 최대 무게를 T까지 견딜 수 있는 가방(배낭)이 1개 주어짐. 물건들을 가방에 담아야 함. 가방에 넣은 물건들의 가격(V) 합이 최대가 되도록 물건 선택 단, 물건들의 무게 합이 T를 넘지 않아야 함. 예 : 무역을 하는 상인이 매출의 일정 비율을 이익으로 가져갈 떄 이익을 극대화하려면 최대한 비싼 물건들을 가지고 다니면서 팔아야 하지만, 사용할 수 있는 운송 수단(또는 배낭)에는 최대 T 무게까지의 물건말 실을 수 있음. 각각의 물건에 대한 무게(W)와 가격(V)은 이미 알고 있음. 물건들을 어떻게 조..
-
2021.06.24
최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)
최단 작업 우선 스케줄링(Shortest-Job-First Scheduling) 그리디 알고리즘(Greedy Algorithm)으로 해결할 수 있는 문제 중 하나 예 : 은행 창구 하나의 창구에서만 업무를 보고 있음. 대기열에 N명의 사람이 기다리고 있음. 서로 다른 용무로 방문했기 떄문에 일 처리에 필요한 시간은 사람들마다 서로 다름. 대기열에 기다리고 있던 모든 사람이 매우 합리적이어서 평균 대기 시간이 최소화될 수 있도록 대기 순서를 다시 정하는 것 에 동의하였음. 그래서 이제 대기 순서를 어떻게 바꿔야 하는지를 결정해야 함. 항목 Pi : i번째 사람 Ai : Pi의 일 처리 시간 Wi : Pi가 기다려야 하는 시간 창구에서 가까운 사람이 먼저 일을 처리할 수 있으므로 첫 번째 사람 P0의 대기 ..
-
2020.08.13
탐욕 알고리즘(Greedy Algorithm)
*탐욕 알고리즘 탐욕 알고리즘(Greedy Algorithm) - 결과값에 대하여 생각하지 않고 최선의 옵션을 선택하여 문제를 해결하는 알고리즘 - 즉, 지역적(locally)의 최선의 선택이 전역적(globally)의 최상의 결과값을 생성하도록 하는 것을 목표로 하는 알고리즘.- 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘 - 탐욕 알고리즘은 해답에 포함될 원소들을 차례로 선택하는 과정을 거치게 됨 - 각 단계에서는 전체적인 상황을 종합적으로 판단하고, 고려하여 결정하는 것이 아니라 현 시점의 정보 를 바탕으로 가장 이익이 되는 원소들을 선택함. - 동적 계획법(Dynamic Programming)과 마찬가지로 최적화 문제(Optimization Problem) 를 푸는데 사..
