최단 경로의 수

문제

0과 1로 이루어진 2차원 배열 map이 주어졌다. 1은 지나갈 수 있는 길이며, 0은 지나갈 수 없는 길이다.

Path의 i,j에 (0,0)에서 출발하여 (i,j)까지 갈 수 있는 최단 경로의 수를 계산해보자

 

m[i][j]=0 => p[i][j]=0

m[i][j]=1

i=0, j=0  => p[i][j] = 1

i=0, j>0  => p[i][j] = p[i][j-1]

i>0, j=0  => p[i][j] = p[i-1][j]

i>0, j>0  => p[i][j] = p[i][j-1] + p[i-1][j] //해당 위치의 바로 좌측,상단의 값의 합

동적 프로그래밍 ( Dynamic Programming DP)

 a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of (it is hoped) a modest expenditure in storage space.

 

두가지 접근 방법

• Top-down approach: This is the direct fall-out of the recursive formulation of any problem. If the solution to any problem can be formulated recursively using the solution to its sub-problems, and if its sub-problems are overlapping, then one can easily memoize or store the solutions to the sub-problems in a table. Whenever we attempt to solve a new sub-problem, we first check the table to see if it is already solved. If a solution has been recorded, we can use it directly, otherwise we solve the sub-problem and add its solution to the table.

=> 재귀 + 메모리, 간결한 코드 but 함수 호출 오버헤드

• Bottom-up approach: Once we formulate the solution to a problem recursively as in terms of its sub-problems, we can try reformulating the problem in a bottom-up fashion: try solving the sub-problems first and use their solutions to build-on and arrive at solutions to bigger sub-problems. This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger sub-problems by using the solutions to small sub-problems.

=> 반복 + 메모리, 속도 효율적 but 복잡한 코드

출처 : wikipedia.org

코드

 
 
#include "stdafx.h"
#include <iostream>
#include <iomanip>
using namespace std;
 
int ** generateMap(int m, int n);
void printMap(int **map, int m, int n);
int ** calculatePath(int **map, int m, int n);
int main()
{
 
 
    int m = 10, n = 10;
    int **map = generateMap(m, n);
    printMap(map, m, n);
    cout << endl;
 
    int **path = calculatePath(map, m, n);
    printMap(path, m, n);
    
 
    return 0;
}
 
//map 만들기
int ** generateMap(int m, int n) {
    srand(time(0));
    int ** map = new int*[n];
 
    for (int i = 0; i < m; i++) {
        map[i] = new int[n];
        for (int j = 0; j < n; j++) {
            map[i][j] = 1;
            if (rand() % 10 == 0)map[i][j] = 0;
        }
    }
    map[0][0] = 1; map[m - 1][n - 1] = 1;
    return map;
 
}
// map print
void printMap(int **map, int m, int n) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cout <<setw(5)<< map[i][j] << " ";
        }
        cout << endl;
    }
}
/*i=0, j=0  => p[i][j] = 1
i=0, j>0  => p[i][j] = p[i][j-1]
i>0, j=0  => p[i][j] = p[i-1][j]
i>0, j>0  => p[i][j] = p[i][j-1] + p[i-1][j] //해당 위치의 바로 좌측,상단의 값의 합*/
int ** calculatePath(int **map, int m, int n) {
    int **path = new int*[n];
    for (int i = 0; i < m; i++) {
        path[i] = new int[n];
 
    }
    path[0][0] = 1;
    for (int i = 1; i < m; i++) {
        if (map[i][0] == 0)path[i][0] = 0;
        else path[i][0] = path[i - 1][0];
    }
    for (int j = 1; j < m; j++) {
        if (map[0][j] == 0)path[0][j] = 0;
        else path[0][j] = path[0][j - 1];
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (map[i][j] == 0)path[i][j] = 0;
            else path[i][j] = path[i - 1][j] + path[i][j - 1];
        }
    }
    return path;
}
 

결과

피보나치 재귀를 이용하여 구현

int fibonacci(int n) {
    if (n == 0 || n == 1)return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
 
}

상향식

피보나치를 메모리와 반복문을 사용하여 구현 => 속도 효율적 but 복잡한 코드

int fibo_DP(int n) {//n 차원
    if (n == 0 || n == 1) return n;
    int *memo_DP = new int[n];
    memo_DP[0] = 0; memo_DP[1] = 1; //초기 항 넣고 시작
    for (int i = 2; i < n; i++) {
        memo_DP[i] = memo_DP[i - 1] + memo_DP[i - 2];
    }
    return memo_DP[n - 1] + memo_DP[n - 2];
}

하향식

피보나치를 메모리와 재귀를 사용하여 구현 => 간결한 코드 but 함수 호출 오버헤드

int fibonacci2(int n) {
    static int* memo = NULL;
    static int _n = n;
    if (!memo) {
        memo = new int[n + 1];
        memset(memo, 0, sizeof(int)*(n + 1));
 
    }
    if (memo[n])return memo[n]; // 저장된 값이 있으면 저장된 값을 return
    if (n == 0 || n == 1) {
        memo[n] = n;
        return n;
    }
    memo[n] = fibonacci2(n - 1) + fibonacci2(n - 2);
    //if (_n == n)delete memo; => 전역 변수로 설정해서 해제하기
 
    return memo[n];
}