More actions
imported>Unknown No edit summary |
(Table transclusion repair v1) |
||
| Line 8: | Line 8: | ||
==== 3. kanpsack ==== | ==== 3. kanpsack ==== | ||
The kanpsack problem is defined as follows: | The kanpsack problem is defined as follows: | ||
Given positive integers P | Given positive integers P<sub>1</sub>, P<sub>2</sub>, ..., P<sub>n</sub>, W<sub>1</sub>, W<sub>2</sub>,..., W<sub>n</sub> and M. | ||
Find X | Find X<sub>1</sub>, X<sub>2</sub>, ..., X<sub>n</sub>, 0 ≤ X<sub>i</sub> such that | ||
∑P | ∑P<sub>i</sub>X<sub>i</sub> (1 ≤ i ≤ n) is maximized subject to ∑W<sub>i</sub>X<sub>i</sub> ≤ M (1 ≤ i ≤ n) . | ||
Give a greedy method to find an optimal solution of the knapsack problem and prove its correctness. | Give a greedy method to find an optimal solution of the knapsack problem and prove its correctness. | ||
| Line 17: | Line 17: | ||
==== 5. Optimal Binary Tree ==== | ==== 5. Optimal Binary Tree ==== | ||
Optimal Binary Tree는 Dynamic Programming 기법으로 풀리는 유명한 문제입니다. 그누스 형님 방법에 의하면 O(n | Optimal Binary Tree는 Dynamic Programming 기법으로 풀리는 유명한 문제입니다. 그누스 형님 방법에 의하면 O(n<sup>2</sup>)으로 풀립니다. 그러나 우리는 이보다 점근적으로 더 빠른 휴리스틱 버전을 작성해야 합니다. | ||
다음과 같이 input 이 들어온다고 가정합시다. 여기서 맨 앞 하나의 정수는 노드의 수를 나타냅니다. 그 밑으로 노드에 대한 정보가 입력됩니다. 노드의 처음은 key 값이고, 그 다음 값은 확률(확률은 1이상의 정수로 임의로 입력) 입니다. 하나의 노드를 검색했을때 실패하는 경우는 없다고 가정합시다. 최적의 평균탐색시간을 가지는 이진탐색트리를 구현하고 다음을 출력하시오. | 다음과 같이 input 이 들어온다고 가정합시다. 여기서 맨 앞 하나의 정수는 노드의 수를 나타냅니다. 그 밑으로 노드에 대한 정보가 입력됩니다. 노드의 처음은 key 값이고, 그 다음 값은 확률(확률은 1이상의 정수로 임의로 입력) 입니다. 하나의 노드를 검색했을때 실패하는 경우는 없다고 가정합시다. 최적의 평균탐색시간을 가지는 이진탐색트리를 구현하고 다음을 출력하시오. | ||
Inorder 순회를 통해 각 키값을 모두 출력하고, 또한 각 키값의 탐색시간의 합계를 출력하시오. | Inorder 순회를 통해 각 키값을 모두 출력하고, 또한 각 키값의 탐색시간의 합계를 출력하시오. | ||
| Line 23: | Line 23: | ||
샘플 Output 에서는 beta를 root 값으로 본 것임. 여러 풀이가 나올 수 있음. 이 페이지의 하위 페이지에 코드와 설명을 올려주세요. | 샘플 Output 에서는 beta를 root 값으로 본 것임. 여러 풀이가 나올 수 있음. 이 페이지의 하위 페이지에 코드와 설명을 올려주세요. | ||
===== input ===== | ===== input ===== | ||
3 | |||
alph 3 beta 7 theta 10 | alph 3 beta 7 theta 10 | ||
===== output ===== | ===== output ===== | ||
alph beta theta | |||
33 | 33 | ||
===== test ===== | ===== test ===== | ||
{| class="wikitable" | {| class="wikitable" | ||
Latest revision as of 12:46, 27 March 2026
Greedy
1. Friendly Coins
Given the denominations of coins for a newly founded country, the Dairy Republic, and some monetary amount, find the smallest set of coins that sums to that amount. The Dairy Republic is guaranteed to have a 1 cent coin.
2. 0/1 knapsack
Give a greedy method, which is heuristic, to solve the 0/1 knapsack problem and also give an example to show that it does not always yield an optimal solution.
3. kanpsack
The kanpsack problem is defined as follows: Given positive integers P1, P2, ..., Pn, W1, W2,..., Wn and M. Find X1, X2, ..., Xn, 0 ≤ Xi such that ∑PiXi (1 ≤ i ≤ n) is maximized subject to ∑WiXi ≤ M (1 ≤ i ≤ n) . Give a greedy method to find an optimal solution of the knapsack problem and prove its correctness.
4. Job Scheduling
Consider the problem of scheduling n jobs on one machine. Describe an algorithm to find a schedule such that its average completion time is minimum. Prove the correctness of your algorithm.
5. Optimal Binary Tree
Optimal Binary Tree는 Dynamic Programming 기법으로 풀리는 유명한 문제입니다. 그누스 형님 방법에 의하면 O(n2)으로 풀립니다. 그러나 우리는 이보다 점근적으로 더 빠른 휴리스틱 버전을 작성해야 합니다. 다음과 같이 input 이 들어온다고 가정합시다. 여기서 맨 앞 하나의 정수는 노드의 수를 나타냅니다. 그 밑으로 노드에 대한 정보가 입력됩니다. 노드의 처음은 key 값이고, 그 다음 값은 확률(확률은 1이상의 정수로 임의로 입력) 입니다. 하나의 노드를 검색했을때 실패하는 경우는 없다고 가정합시다. 최적의 평균탐색시간을 가지는 이진탐색트리를 구현하고 다음을 출력하시오. Inorder 순회를 통해 각 키값을 모두 출력하고, 또한 각 키값의 탐색시간의 합계를 출력하시오. !! 주의 : 최적을 구하는 것이 아니고, 빠른 시간안에 최적에 가까운 값을 구하는 것이 목적임. 샘플 Output 에서는 beta를 root 값으로 본 것임. 여러 풀이가 나올 수 있음. 이 페이지의 하위 페이지에 코드와 설명을 올려주세요.
input
3
alph 3 beta 7 theta 10
output
alph beta theta
33
test
| 알고리즘8주숙제/test |
풀이
| 작성자 | 개발시간 | 풀이 |
| Leonardong | 2h | [1] |
| 김상섭 | 엄청 | AproximateBinaryTree/김상섭 |
| 문보창 | 상섭이형보다많이 | 알고리즘8주숙제/문보창 |