알고리즘 과제 #3

Optimal binary search tree를 구하는 dynamic programming algorithm과 Optimal sequence alignment룰 구하는 dynamic programming algorithm을 구현하는 것이다.

---

Optimal binary search tree [50점] 

제 3 장에서 공부한 optimal binary search tree를 구하는 dynamic programming algorithm을 C/C++ 언어로 구현하시오. 입력은 한 줄로 이루어지며, 입력 값들은 space로 구분되어 입력된다. 첫 번째 입력 값은 key의 개수  이며, 두 번째부터  번째 입력 값은 각 key를 search할 확률 이다. Key1, Key2, …, Keyn 은 정렬되어 있다고 가정한다. (주의: Key 자체는 입력되지 않는다. 각 key의 확률값만 입력된다.) 출력은 optimal binary search tree의 average number of key comparisons를 출력한다. 입출력 예는 아래와 같다. 

입력 예
4 / 0.375 / 0.375 / 0.125 / 0.125

출력 예
1.750

입력되는 key의 개수 n의 범위는 1 이상 100 이하이다. 

입력되는  p1,p2,p3... pn 는 소수점 셋째 자리까지 표기된 실수이다. 

출력도 소수점 셋째 자리까지 표기해야 한다. 

여러분이 작성할 프로그램은 한번 실행에 위와 같은 입력을 단 한 세트만 입력 받는 것으로 작성되어야 한다. 

여러분이 작성한 프로그램을 채점할 때에는 10개의 입력 세트를 만들어서 프로그램을 10번 실행하여 채점한다. 

배점은 한 개의 입력 세트에 대해서 5점씩이다. 이 10개의 입력 세트는 미리 알려주지 않는다.

 

주의사항

(1) 여러분이 작성한 프로그램을 10번 실행하는 것은 채점자가 할 일이며, 여러분이 작성할 프로그램은 한 개의 입력 세트를 받아서 한 개의 출력 세트를 출력해야 한다. 제출한 프로그램이 여러 번의 입력 세트를 입력 받도록 프로그램 되어서 채점시 에러가 발생하는 경우에는 0점으로 처리한다.

(2) 문제에서 요구하는 출력 이외에 다른 것을 출력하는 경우에도 0점으로 처리한다. 예를 들어서, 여러분의 프로그램이 “자, 이제 key의 개수 n을 입력하세용” 같은 메시지를 출력하면 0점이다. 

(3) 출력 양식을 지키지 않으면 0점으로 처리한다. 예를 들어서 175E-02 등의 형식으로 출력하면 0점으로 처리한다.

(4) 입력과 출력은 standard input과 standard output을 사용해야 한다. 입력화일 또는 출력화일을 사용하면 0점으로 처리한다.

(5) 교재에 나와 있고 강의에서 설명한 알고리즘을 구현해야 한다. 다른 알고리즘을 구현한 경우에는 0점으로 처리한다.

(6) 제출 프로그램은 한 개의 화일로 작성되어야 하며, 여러 개의 화일로 나누어 작성하면 0점으로 처리한다. 주석 처리 되지 않은 설명 등이 들어가 정상적 실행이 되지 않는 경우도 0점으로 처리한다.

(7) 반드시 스탠다드 라이브러리만 사용해야하며, 다른 외부 라이브러리를 사용할 수 없다.

(8) 다시 말할 필요도 없지만, 절대로 다른 사람의 프로그램을 베끼지 마시오. 다른 사람의 프로그램을 베끼는 경우에는 무슨 일이 벌어질지 나도 잘 모름. 상당히 과격한 일이 벌어질 수 있음.