알고리즘 특론(과제 2)

소개글

0000대학교 컴퓨터 전공 관련 과목 수강시 작성한 보고서입니다.
알고리즘 특론 과제 중 하나입니다.
세부내용은 목차를 참조 바랍니다.

목차

1. 아래 순열을 퀵 정렬을 이용하여 정렬하는 과정을 보여라.
(20, 40, 35, 5, 10, 45, 50, 25, 15, 30)

2. 다음은 분할 정복 방법을 이용하여 최근접 점쌍을 찾는 과정 중 합병 과정이다

3. 동전 문제에서 사용할 수 있는 동전들의 액면가가 {10. 30, 50, 100}일 때
거스름 돈 90원에 대하여 동적 프로그래밍을 이용하여 최적해를 구하라.

4. 두 문자열 X = INDEX와 Y = FINE에 대한 최소 편집 거리를 구하라.
단, δD=δI=δC=1 이라고 가정한다.

본문내용

- 우선 Sl을 보면 L을 기준으로 Y 좌표가 y와 y+A 사이에 있을 수 있는 점은 최대 2개 이다. Sr도 최대 2개이다.
- 이렇게 되면 L상에는 한 점이 중복해서 나타나게 되는데, 이 점은 기준점 i가 되므로 결국 최대 2번의 거리 계산만 하면 된다.





3. 동전 문제에서 사용할 수 있는 동전들의 액면가가 {10. 30, 50, 100}일 때
거스름 돈 90원에 대하여 동적 프로그래밍을 이용하여 최적해를 구하라.

★ 결 과 : 거스름 돈 90에 대한 최적해 값은 3이다.

★ 점화식 : A[T]=min1≤T≤n(A[T-C[i]]+1)
(A[0]=0, 음수 x에 대하여 A[x]=∞라고 가정)

★ 풀 이 : n=4, C[i]={10, 30, 50, 100}

참고 자료

없음