43. 미로에서 길찾기 알고리즘 (재귀, 메모이제이션, 동적 프로그래밍)

1. 개요

길찾기 알고리즘은 쉬움.

길찾기 알고리즘은 이차원 배열 안의 시작점에서 종착역까지 최단 경로의 길이 몇 개인지 찾는 알고리즘.

고등학교 수학에서 각 미로 교차점에 숫자를 써놓고

왼쪽까지 오는 경우의 수 + 위쪽까지 오는 경우의 수 

를 더해서 가다보면 최종적으로 종착역까지 올 수 있는 길이 몇 가지인지 알게 되는 알고리즘.

이 알고리즘은 재귀, 메모이제이션, 동적 프로그래밍 3가지 방식으로 풀이가 가능한데

확실히 알아두어야 할 것은

지금까지 동적 프로그래밍이란 재귀 + 메모이제이션 이라고 알고있었다.

그런데 책마다 조금씩 다른 것 같다. 그리고 이제서야 확실히 구분 짓는 방식은

재귀의 단점을 발전시킨 것이 메모이제이션이고 이는 Top Down 방식으로 진행된다.

동적 프로그래밍은 초기화 된 처음 값을 쌓아가는 방식으로 Bottom Up 방식으로 진행된다.

둘 다 아이디어는 같다. 부분 문제들의 값을 다른 메모리 배열에 저장하여 반복 계산을 하지 않는다.

그래도 이제 조금 명확하다. 메모이제이션은 인자가 감소하는 상황으로 코드를 작성하면 되고

동적 프로그래밍은 반복문과 다른 저장 배열을 통해 그 최종 값을 찾아낸다.

둘 중 어느 방법도 상관없으나

하지만 역시 코드를 읽기 쉽고 간결하고 미감이 좋은 메모이제이션 방법이 나는 좋은 것 같다.

(점화식)

if ( map[i][j] == 0 ) MEMO[i][j] = 0;

if ( map[i][j] == 1 ){

i==0, j==0 이면 MEMO[0][0] = 1;

i > 0, j==0 이면 MEMO[i][j] = MEMO[i-1][j];

i==0, j > 0 이면 MEMO[i][j] = MEMO[i][j-1];

i > 0, j > 0 이면 MEMO[i][j] = MEMO[i-1][j] + MEMO[i][j-1];

}

하지만 이 알고리즘은 너무 빨리 경우의 수가 증가하기에 최종적으로 long long 타입으로도 커버가 안된다.

이런 문제를 해결하기 위해 Big Integer 타입, 즉 자리수에 제한받지 않는 Type이 필요하다.

2. 문제

이차원배열의 크기인 m * n을 입력받으면 0,0에서부터 m-1,n-1까지 가능한 경로를 모두 찾는 알고리즘을 작성하시오.

(재귀, 메모이제이션, 동적 프로그래밍 3가지 방법으로 작성하시오.)

3. 코드

3-1) search_map_RECUR()

3-2) search_map_MEMO()

3-3) search_map_DP()

3-4) 출력

4. 정리

메모이제이션과 동적 프로그래밍의 문제를 풀어가는 알고리즘의 순서를 잊지말 것.

Top Down과 Bottom Up

재귀인가 반복인가

아이디어는 같은 맥락이니 자기와 알맞는 하나를 선택.