알고리즘 6장 연습문제

소개

알고리즘 6장 연습문제

목차

1. 이항계수의 알고리즘 6.1과 6.2를 구현하고 몇 가지 예를 대상으로 그 실행 시간을 실제적으로 비교하시오.

2. 알고리즘 6.2에서 1차원 배열을 이용해서도 그 결과를 구할 수 있다. 이를 알고리즘으로 작성하고 구현하시오.

3. 경기의 최종 승산 확률은 행 또는 열의 순서로도 각 칸의 값을 구할 수 있다. 이에 대한 알고리즘을 작성하시오.

4. 동적프로그래밍 알고리즘이 최적화 문제에서 가져야 할 요건에 대해 설명하시오.

5. 4개 행렬의 행과 열의 구성이 5×3, 3×10, 10×4, 4×5 와 같을 때 최소의 곱셈횟수와 곱셈 순서를 구하는 과정을 보이시오.

6. 최고 곱셈횟수의 알고리즘에서 본문에서 소개한 비교 연산의 실행 횟수를 구하시오.

7. 문자열 A=aabab, B=baba 일 때 이들의 편집거리를 구하는 과정을 나타내시오.

본문내용

1. 이항계수의 알고리즘 6.1과 6.2를 구현하고 몇 가지 예를 대상으로 그 실행 시간을 실제적으로 비교하시오.
예 : S=(a, b, c, d, e, f)
6.1 알고리즘
① Combination (6, 2)
② Combination (5, 1)
③ Combination (4, 0)
④ Combination (4, 1)
⑤ Combination (3, 0)
⑥ Combination (3, 1)
⑦ Combination (2, 0)
⑧ Combination (2, 1)
⑨ Combination (1, 0)
⑩ Combination (1, 1)
⑪ Combination (5, 2)
⑫ Combination (4, 1)
⑬ Combination (3, 0)
⑭ Combination (3, 1)
⑮ Combination (2, 0)
Combination (2, 1)
Combination (1, 0)
Combination (1, 1)
Combination (4, 2)
Combination (3, 1)
Combination (2, 0)
Combination (2, 1)
Combination (1, 0)
Combination (1, 1)
Combination (3, 2)
Combination (2, 1)
Combination (1, 0)
Combination (1, 1)
Combination (2, 2)

알고리즘 6.2
n=6, k=2
① i = 0, b = min (i, k) ∴ b = 0, j = 0, C[0][0] = 1
② i = 1, b = min (i, k) ∴ b = 1, j = 0, C[1][0] = 1
③ i = 1, b = min (i, k) ∴ b = 1, j = 1, C[1][1] = 1
④ i = 2, b = min (i, k) ∴ b = 2, j = 0, C[2][0] = 1

참고자료

· 없음