Maintenance script: Table transclusion repair v1

2026-03-27T12:46:21Z

Table transclusion repair v1

← Older revision		Revision as of 12:46, 27 March 2026
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~~<~~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.		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~~<~~sub~~>~~1~~<~~/sub~~>~~, X~~<~~sub~~>~~2~~<~~/sub~~>~~, ..., X~~<~~sub~~>~~n~~<~~/sub~~>~~, 0 ≤ X~~<~~sub~~>~~i~~<~~/sub~~>~~ such that		Find X<sub>1</sub>, X<sub>2</sub>, ..., X<sub>n</sub>, 0 ≤ X<sub>i</sub> such that
	∑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) .		∑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~~<~~sup~~>~~2~~<~~/sup~~>~~)으로 풀립니다. 그러나 우리는 이보다 점근적으로 더 빠른 휴리스틱 버전을 작성해야 합니다.		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		3
	alph 3 beta 7 theta 10 ~~\|}}~~		alph 3 beta 7 theta 10
	===== output =====		===== output =====
	~~{{\|~~ alph beta theta		alph beta theta
	33 ~~\|}}~~		33
	===== test =====		===== test =====
	{\| class="wikitable"		{\| class="wikitable"

imported>Unknown at 05:30, 7 February 2021

2021-02-07T05:30:21Z

New page

== 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 =====
{| class="wikitable"
|-
| [[알고리즘8주숙제/test]]
|}

===== 풀이 =====
{| class="wikitable"
|-
| 작성자
| 개발시간
| 풀이
|-
| [[Leonardong]]
| 2h
| [http://wiki.zeropage.org/trac/leonardong/browser/AlgorithmTrainning/OptimalBST.py]
|-
| 김상섭
| 엄청
| [[AproximateBinaryTree/김상섭]]
|-
| 문보창
| 상섭이형보다많이
| [[알고리즘8주숙제/문보창]]
|}
----

알고리즘8주숙제 - Revision history

Maintenance script: Table transclusion repair v1

imported>Unknown at 05:30, 7 February 2021