Written by JS970
on March 29, 2023

컴퓨터 알고리즘 2023-03-29 수업정리

Flow

Dynamic Programming - Binomial Coefficient
Dynamic Programming - Floyd's Algorithm

Dynamic Programming - Binomial Coefficient

Dynamic Programming을 통해 이항 계수를 구하는 알고리즘에 대해 알아보자
Combination 연산의 성질 중 다음과 같은 성질이 있다.$$_nC_k = {n-1}C{k-1} + _{n-1}C_k$$
이를 이용하여 Combination의 계산이 가능하다. 하지만 이 자체를 recursive하게 구현 할 경우, 이전에 계산한 항에 대해 다시 연산하게 되어 성능이 떨어지는 문제점이 있다.
만약 이전 항이 미리 계산되었고, 배열을 통해 저장되어 이후에 별도의 연산 없이 그 값을 사용할 수 있다면 이러한 문제를 해결할 수 있다.

Dynamic Programming 적용

Dynamic Programming의 적용을 위해서는 Recursive Equation과 Matrix가 필요하다.
Recursive Equation으로는 앞서 살펴본 Combination연산의 성질을 이용할 수 있다.$$B[i][j] = B[i-1][j-1] + B[i-1][j]\ \ (if\ j=0\ or\ i=1,\ B[i][j] = 1)$$
n개 중 k개를 선택하는 조합 연산을 위해서는 n*k 크기의 배열을 사용하여 기존 연산값을 저장할 수 있다.
- 실제 이차원 배열에서 사용하는 공간은 n*k 배열의 왼쪽 아래 삼각형 부분만 사용하므로 동적 할당을 이용한다면 메모리 절약이 가능하긴 하다.
이렇게 Dynamic Programming 방법을 통해 이항 계수를 구하는 프로그램을 구현한 코드는 아래와 같다.

#include <iostream>
using namespace std;
 
void initialize_binomial_coefficient_matrix(int ** arr, int N, int K)
{
	for(int i = 0; i < N; i++) 
	{
		arr[i][0] = 1;
		for(int j = 1; j <= i; j++)
		{
			if(i == j) arr[i][j] = 1;
			else arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
		}
	}
}
 
int main()
{
	int ROW, COL;
	cout << "Type ROW and COL size of total space" << endl;
	cin >> ROW >> COL;
	int ** binomial_coefficient_matrix = new int*[ROW+1];
	for(int i = 0; i < ROW+1; i++)
	{
		binomial_coefficient_matrix[i] = new int[COL+1];
		for(int j = 0; j < COL+1; j++) 
			binomial_coefficient_matrix[i][j] = 0;
	}
 
	initialize_binomial_coefficient_matrix(binomial_coefficient_matrix, ROW+1, COL+1);
 
	cout << "type n and r for calculate nCr" << endl;
	int n, r; cin >> n >> r;
	cout << n << "C" << r << " = " << binomial_coefficient_matrix[n][r] << endl;
 
	return 0;
}

Dynamic Programming - Floyd's Algorithm

플로이드 알고리즘은 그래프 상에서 최단 경로를 구하는 알고리즘이다.
그래프는 노드와 간선, 간선의 가중치(비용)로 이뤄진다.
노드 간 이동에 있어 (i -> j) 보다 (i -> k -> j)의 비용이 더 적을 수 있다.

Dynamic Programming 적용

인접하지 않은 노드의 비용은 무한대, 인접한 노드의 비용은 간선의 가중치로 설정한 2차원 배열 G를 생성한다.
G[i][j]는 노드 i에서 j로 이동하는 데 소모되는 최소 비용을 의미한다.
Recursive Equation은 다음과 같이 설정할 수 있다.$$G^{(k)}[i][j] = minimum(length[v_i, v_j],\ length[v_i,\ v_k\ v_j])$$
이렇게 Dynamic Programming방법으로 Floyd's Algorithm의 구현을 통해 그래프 상의 최단 경로에 대한 가중치를 구하는 알고리즘을 구현한 코드는 아래와 같다.

#include <iostream>
#include <climits>
using namespace std;
 
int main()
{
    cout << "Type the number of nodes : " << endl;
    int N; cin >> N;
 
    /* Floyd's Algorithm - Initialization of adjacent matrix */
    int ** graph = new int*[N+1];
    for(int i = 0; i < N+1; i++)
    {
        graph[i] = new int[N+1];
        for(int j = 0; j < N+1; j++)
        {
            if(i == j) graph[i][j] = 0;
            else graph[i][j] = 1000;
        }
    }
 
    cout << "Type the number of edges : " << endl;
    int E; cin >> E;
    cout << "Type Start Node, Destination Node and their weights of each edges" << endl;
    for(int i = 0; i < E; i++)
    {
        int start, end, weight; cin >> start >> end >> weight;
        graph[start][end] = weight;
    }
    /* Floyd's Algorithm - Initialization of adjacent matrix */
 
    /* Floyd's Algorithm - Finding lowest cost from start to destination */
    for(int transfer = 1; transfer < N+1; transfer++)
    {
        for(int start = 1; start < N+1; start++)
        {
            for(int end = 1; end < N+1; end++)
            {
                graph[start][end] = 
                (graph[start][end] <= graph[start][transfer] + graph[transfer][end])
                 ? graph[start][end] : graph[start][transfer] + graph[transfer][end];
            }
        }
    }
    /* Floyd's Algorithm - Finding lowest cost from start to destination */
 
    for(int i = 1; i < N+1; i++)
    {
        for(int j = 1; j < N+1; j++)
        {
            if(graph[i][j] >= 1000) cout << "INF" << " ";
            else cout << graph[i][j] << " ";
        }
        cout << endl;
    }
 
    return 0;
}

총 고려해야 할 비교 연산의 수는 시작 노드(n) * 도착 노드(n) * 경유 노드(n)으로 cubic의 시간복잡도를 가진다.
Floyd's Algorithm은 표본의 개수가 적을 때 모든 정점의 최단 거리를 쉽게 구현 가능하다는 장점이 있다.

Top