보고서

HW #03

(중간고사 문제풀이)

과목명 : 알고리즘

제출일 : 07년 10월 8일

학  번 : 20021558

성  명 : 경 규 성

2. 배열 Data[1..n]에서 최대값을 구하는 문제에 대하여 절반씩 나누어서 처리하는 divide and conquer 알고리즘으로  다음의 Max 를 완성하시오. 전체의 최대값은 다음과 같이 호출한다.

maximum = Max(1, n, Data);

int Max(int low, int high, int data[])

{

....

}

▣ 풀이

#include <stdio.h>

#define max(x,y) (((x) > (y)) ? (x) : (y))

int Max(int low, int high, int data[])

{

int mid = (int)((low + high)/2);

if((high - low) <= 1){

/* 임계값 지정 두 배열의 인댁스가 같거나

* 바로 옆이면 두 배열 값 중 큰 값 리턴

*/

return max(data[low], data[high]);

}

else{

/* 입력된 배열을 반으로 갈라

*  다시 Max의 입력으로 준다.

*/

return max(Max(low, mid, data), Max(mid+1, high, data));

}

}

int main()

{

int a, b;

int D1[11] =

{101, 102, 203, 303, 402, 501, 301, 201, 403};

int D2[10] =

{11, 12, 13, 14, 15, 16, 17, 17, 19, 20};

/* 호출 */

a = Max(1, 10, D1);

b = Max(1, 9, D2);

printf("D1배열 최대값 : %d\n", a);

printf("D2배열 최대값 : %d\n", b);

return 0;

}

출력화면

3. Floyd의 Shortest Path 알고리즘에 대하여

(a) 핵심적인 아이디어를 간략히 설명하시오.

▣ 풀이

n 개의 정점으로 된 가중치 포함 그래프를 배열 W로 표현하고, 배열 D는 그래프의 최단경로의 길이를 나타내 준다.

초기 W의 값에서 D의 값을 계산한다. n+1개의 배열 D를 만들어 D를 아래와 같이 정의하고,

k는 0 <= k <= n 이고,

D(k)[i][j] = 집합 {v1, v2, ...... vk} 에 속하는 정점만을 중간 정점으로 사용하면서 vi에서 vj로 가는 최단경로의 길이

D(0)에서 D(n)을 하나씩 구하여 나가면 최종 D(n)[i][j]는 어떤 것도 거쳐가도록 혀용하고 구한 vi에서 vj로 가는 최단 경로의 길이가 된다.

(b) 이 알고리즘이 dynamic programming 기법에 해당하는지의 근거를 구체적으로 설명하시오.

▣ 풀이

동적계획 알고리즘의 개발절차는 아래와 같다.

1. 문제 사례에 대해서 해답을 주는 재귀 관계식을 정립한다.

2. 작은 사례를 먼저 해결하는 상향식 방법으로 문제의 사례 전체를 해결한다.

Floyd 알고리즘이 위의 동적계획법으로 만들어 성립한다면 이 알고리즘은 dynamic programming 기법에 해당하는 것이다. 우선 Floyd 알고리즘을 동적계획해 본다.

절차1. D(k-1)로부터 D(k)를 계산하는 재귀 관계식을 정립한다.

경우 a) {v1, v2, ... vk}에 속한 정점만 중간정점으로 거쳐서 vi에서 vj로가는 최단경로 중에서 최소한 하나는 vk를 거치지 않은 경우이다. 식으로 나타내면 아래와 같다.

D(k)[i][j] = D(k-1)[i][j]

경우 b) {v1, v2, ... , vk}에 속한 정점만 중간정점으로 거쳐서 vi에서 vj로 가는 최단경로는 모두 vk를 거치는 경우이다. vk는 vi에서 vk로 가는 부분경로 상에서 중간정점이 될 수 없기 때문에, 그 부분경로는 {v1, v2, ... vk-1}에 속한 중간 정점만을 거치게 된다.

D(k)[i][j] = D(k-1)[i][j] + D(k-1)[k][j]

경우 a와 b둘중 하나는 반드시 성립해야 되므로 다음과 같이 D(k-1)로부터 D(k)를 구할 수 있다는 것을 의미한다.

D(k)[i][j]

= min(D(k-1)[i][j], D(k-1)[i][k]+D(k-1)[k][j])

동적계획 알고리즘 개발절차 1을 수행하였다.

절차2. k = 1부터 n 까지 과정을 상향식으로 반복하여 문제의 사례를 해결한다.

for(k=0; k<n; k++)

for(i=1; i<n; i++)

for(j=1; j<n; j++)

D[i][j] = minimum(D[i][j], D[i][k] + D[k][j]);

알고리즘은 k가 1부터 D(k-1)에서 D(k)를 계산해 나가도록 구현되어있다. 상향식으로 작은 사례에서 큰 사례를 계산하고 있다.

Floyd 알고리즘은 동적계획법으로 작성 가능하고 이미 성립하므로 dynamic programming이라고 할 수 있다.

(c) 이 알고리즘이 ‘principle of optimality’ 를 만족하는지를 논리적으로 설명하시오.

▣ 풀이

이 알고리즘에서 최적의 원칙이 성립하는지 보면, vk를 vi에서 vj로 가는 최적 경로상의 정점이라고 하면, vi에서 vk로 가는 부분경로와 vk에서 vj로 가는 부분경로도 반드시 최적이어야 한다.

k개의 정점을 지나는 최단경로길이는 문제(b)에서 설명했듯이 D(k)[i][j] = D(k-1)[i][j] 경우와 D(k)[i][j] = D(k-1)[i][j] + D(k-1)[k][j] 인 경우가 있다. 이 두 가지 모든 경우 중에서 최단의 경로를 아래의 식과 같이 구하여

D(k)[i][j]

= min(D(k-1)[i][j], D(k-1)[i][k]+D(k-1)[k][j])

k개의 정점을 지나는 경우의 부분사례에서 최적의 해를 구하고 있다.

문제 사례에 대한 최적해 D(n)[i][j] 역시 부분사례의 최적해들을 포함 하고 있기 때문에 이 알고리즘은 최적의 원칙을 만족한다.

4. (a) Dynamic programming 방식의 알고리즘이 divide-and-conquer 방식의 알고리즘보다 유리한 점을 구체적인 예를 들어 설명하시오.

▣ 풀이

n번째 피보나찌 항을 분할정복 알고리즘으로 구하면 계산되는 항의 개수는 n에 대하여 지수개이다. 그 이유는 분할정복법 문제의 사례를 작은 사례로 분할한 다음 그 작은 사례를 맹목적으로 해결하여 문제 전체의 답을 구하기 때문이다. 이런 하향식 접근법은 분할한 작은 사례들이 서로 관련이 없는 합병정렬과 같은 문제를 푸는 경우 좋지만, n번째 피보나찌 항 구하기와 같은 문제에서는 분할한 사례들이 서로 연관되어 있다. (0+1=1,1+1=2, 1+2=3...)

분할정복 알고리즘으로는 두 항을 서로 독립적으로 구하기 때문에 두 번째 이상 호출되는 피보나찌 항은 한번 이상 계산된다.

동적계획법은 작은 사례를 먼저 해결하고, 그 결과를 저장한 다음, 후에 그 결과가 필요할 때마다 다시 계산하는 대신 그 저장한 결과를 이용한다. n번째 피보나찌 항을 구하는 효율적인 알고리즘은 동적계획법을 이용한 예가 된다. 0부터 n까지 인덱스를 가진 배열에서 앞부분의 n+1항을 순서대로 구축하여 n번째 피보나찌 항을 구한다.이런 상향식 접근 방법은 필요없이 한번이상 중복계산하지 않아 분할정복법보다 유리하다.

(b) Dynamic programming 알고리즘이 더 유리하다면 merge sort 알고리즘을 dynamic programming 방식으로 개선할 수 있는가 ? 있다면 그 개략적인 알고리즘을, 없다면 그 이유를 설명하시오.

▣ 풀이

작은 사례를 먼저 해결하고, 그 결과를 저장한 후에 그 결과가 필요할 때마다 다시 계산하는 동적 계획법은 k번째 사례에서 연관성을 이용해 k+1을 계산한다.

하지만 merge sort알고리즘은 분할한 사례들이 서로 연관이 없다. 따라서 작은 사례에서 큰 사례를 유추할 수 없기 때문에 dynamic programming 방식으로 개선할 수 없다.