2022 Final exam

1. 아래의 문장에 있는 빈칸을 채워라. 한 문제당 배점은 3점이며 오답인 경우는 2점의 감점이 있다. 
동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 ( (가) )이(가) 발생하는 경우에 이 재귀적 ( (가) )을(를) 해결하는 방법을 뜻한다.
그래프에서 정점은 대상이나 개체를 나타내고 ( (나) )은 이들 간의 관계를 표시한다.
( (다) ) 알고리즘은 패턴을 수치화해, 문자열의 비교를 수치 비교로 전환해 문자열 매칭을 수행하는 방법이다. 
간선들이 가중치를 가지는 그래프에서 간선 기준치의 합이 가장 작은 트리를 ( (라) )라 한다. 
( (마) )는 키 값을 입력으로 받아 해시 테이블상의 주소를 리턴한다. 
( (바) ) 알고리즘은 입력 그래프 G=(V,E)에서 간선의 가중치가 음의 값을 허용하는 임의의 실수인 경우 최단 경로 알고리즘이다. 
원시적인 매칭 알고리즘은 텍스트(길이 X)의 각 위치에서 시작해 패턴(길이 Y) 문자열과 일치하는지 체크하는 방법으로, O( (사) )의 수행시간이 소 요된다.

2. Boyer-Moore 알고리즘을 사용하여 아래의 주어진 텍스트에서 패턴(HELLO)을 찾는 과정을 표현하라. 먼저 bad matching table 을 구한 후

Bad Matching Table
Key	H	E	L	O
Value

알고리즘의 수행 과정을 주어진 표에 설명과 함께 표현하라. 

L

O

L

O

E

L

L

O

O

H

E

L

O

H

E

L

L

O

3. 플로이드 워샬 알고리즘을 사용하여 각 노드간 최단 거리를 구하라. (만일 노드 m에서 노드 n로 도달할 수 없는 경우는 비용이 무한대로 하며, 결과 를 행렬로 표현할 것)

4. 행렬 A1, A2, .. A5 가 각각 p0*p1, p1*p2, .. p4*p5 행렬이며, <p0 p1 .. p5> =<10,5,20,7,15,3>이라 하자.
(가)가능한 모든 곱셈 순서는 총 몇 가지인가? 
(나)동적 프로그래밍으로 최적 행렬 곱셈 순서를 찾으라.

5. 크기가 13인 해시 테이블이 해시 함수로 h(x) = x mod 13을 사용한다. 
(가) 충돌 해결은 개방 주소 방법의 선형 조사를 택한다. 원소 10, 20, 30, 43, 33, 46, 49, 61이 차례로 저장된 후 해시 테이블의 모양은 어떻게 되겠는가? (풀이과정 설명)
(나) 선형 조사 방법 대신 더블 해싱 hk(x) = (h(x)+ k f(x)) mod 13을 사용할 때 최종적인 해시 테이블 모양은 어떻게 되가?  (여기서 h(x)=x mod 13, f(x)=x mod 11, 풀이과정 설명)