1. 무식하게 풀기


생각

1단계. 문제는 (0, 0)에서 시작하여 (n-1, n-1) 까지 도달할 수 있는가 이다. 함수 jump를 정의 한다.

2단계. jump(y, x) 는 (y, x)좌표에서 시작해 끝까지 갈 수 있는지 반환하는 함수다.

3단계. (y, x)를 입력받은 함수는 오른쪽으로 가는 루트와 아래로가는 루트가 존재한다.

이를 점화식으로 나타내면 아래와같다.

- jump(y + m, x) || jump(y, x + m) m = 각 보드판의 숫자


코드 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// JUMPGAME_1
#include <iostream>
const int MAX = 101;
int g_JumpArray[MAX][MAX];
int g_BoardSize = 0;
 
// y, x의 좌표에서 끝까지 갈 수있는지를 반환하는 함수
int jump(int y, int x)
{
    // 기저사례1. y 또는 x 가 범위를 벗어났을때
    if (y >= g_BoardSize || y < 0) return 0;
    if (x >= g_BoardSize || x < 0) return 0;
    
    // 기저사례2. y와 x가 끝에 다달았을 때
    if (y == g_BoardSize - 1 && x == g_BoardSize - 1) return 1;
    
    // 여기에서 답을 계산한다.
    int value = g_JumpArray[y][x];
    // 점화식 : 갈수 있는 법 = (y + v, x) || (y, x + v)
    return (jump(y + value, x) || jump(y, x + value));
}
int main()
{
    // 테스트 케이스
    int testCase = 0;
    scanf("%d", &testCase);
    
    while(testCase--){
        // 보드판 크기 N * N
        scanf("%d", &g_BoardSize);
        
        // 보드판 입력
        for(int y = 0; y < g_BoardSize; y++)
        {
            for(int x = 0; x < g_BoardSize; x++)
            {
                scanf("%d", &g_JumpArray[y][x]);
            }
        }
        // 끝까지 도달 가능하다면 YES
        if(jump(0, 0))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
cs

 

결과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
7
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 2
1 1 1 1 1 2 0
NO
5
1 1 1 1 1 
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 0
YES
cs


결과는 나왔지만 다음과 같은 경우에 완전탐색알고리즘은 매우 오랜시간이 걸린다.

S  1  1  1  1  1

1  1  1  1  1  1

1  1  1  1  1  1

1  1  1  1  1  1

1  1  1  1  1  2

1  1  1  1  2  E


완전 탐색의 경우 모든 경로를 탐색한 후에서야 끝으로 갈 수 없다는 것을 알 것이다.

이 과정에서 같은 경로를 몇번이나 다시 탐색할 것이고 그로인해 속도저하의 결과를 가져올 것이다.



2. 메모이제이션 적용하기(기록하기)


생각

1단계. 위의 방법에서 구현했던 함수는 입력이 (y, x)로 정해져있으면 거기서 끝까지 갈 수 있는지 없는지 는 항상 일정한참조적 투명한 함수 이다. 때문에 메모이제이션을 적용하면 같은 루트를 두번이상 계산하지 않아 속도를 향상 시킬 수 있다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// JUMPGAME_2
#include <iostream>
const int MAX = 101;
int g_JumpArray[MAX][MAX];
int g_Cache[MAX][MAX];
int g_BoardSize = 0;
 
// y, x의 좌표에서 끝까지 갈 수있는지를 반환하는 함수
int jump(int y, int x)
{
    // 기저사례1. y 또는 x 가 범위를 벗어났을때
    if (y >= g_BoardSize || y < 0) return 0;
    if (x >= g_BoardSize || x < 0) return 0;
    
    // 기저사례2. y와 x가 끝에 다달았을 때
    if (y == g_BoardSize - 1 && x == g_BoardSize - 1) return 1;
    
    // 캐시가 -1이 아니라면 캐시에 저장된 값 리턴
    int& ret = g_Cache[y][x];
    if (ret != -1) return ret;
    
    // 여기에서 답을 계산한다.
    int value = g_JumpArray[y][x];
    
    // 점화식 : 갈수 있는 법 = (y + v, x) || (y, x + v)
    ret = (jump(y + value, x) || jump(y, x + value)); //점화식
    return ret;
}
 
int main()
{
    // 테스트 케이스
    int testCase = 0;
    scanf("%d", &testCase);
    
    while(testCase--){
        // 보드판 크기 N * N
        scanf("%d", &g_BoardSize);
        
        // 보드판 입력
        for(int y = 0; y < g_BoardSize; y++)
        {
            for(int x = 0; x < g_BoardSize; x++)
            {
                scanf("%d", &g_JumpArray[y][x]);
            }
        }
        // 캐시 배열 초기화
        memset(g_Cache, -1, sizeof(g_Cache));
        
        // 끝까지 도달 가능하다면 YES
        if(jump(0, 0))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
cs

 

결과


결과는 위의 것과 같다.


캐시를 사용하여 한번 계산한 루트에 대한 값을 저장하고 있다가 그부분에 대한 계산을 요구할 시 캐시값을 반환하는 형태로 수정하였다.

N이 커질수록 메모이제이션을 적용한 것과 안한 것의 속도차이가 커지는 것을 확인 할 수 있다.

'All > Algorithm' 카테고리의 다른 글

SelectionSort  (0) 2016.01.02
Sort Algorithm  (0) 2015.12.28
JUMPGAME_문제  (0) 2015.12.28
FIBONACCI_알고리즘  (0) 2015.12.28
FIBONACCI_문제  (0) 2015.12.28

문제

 

땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다.

균형을 잃어서 다른 발로 서거나 넘어져도 게임에서 집니다만, 재하와 영훈이는 젊고 활기차기 때문에 외발로 뛰어다니는 것은 아무것도 아닙니다. 다만 걱정되는 것은 주어진 게임판에 시작점에서 끝점으로 가는 방법이 존재하지 않을 수도 있다는 것입니다. 예를 들어 그림 (a)의 게임판에서는 사각형으로 표시된 칸들을 통해 끝에 도달할 수 있지만, 숫자가 하나 바뀐 그림 (b)에서는 그럴 수가 없습니다.

게임판이 주어질 때 왼쪽 위의 시작점에서 오른쪽 아래의 시작점에 도달할 수 있는 방법이 있는지 확인하는 프로그램을 작성하세요.

 

입력

 

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 격자의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에 각 n개의 숫자로 왼쪽 위부터 각 칸에 쓰인 숫자들이 주어집니다. 오른쪽 아래 있는 끝 점 위치에는 0이 주어집니다.

 

출력

 

각 테스트 케이스마다 한 줄로, 시작점에서 끝 점으로 도달할 수 있을 경우 "YES"를, 아닐 경우 "NO"를 출력합니다. (따옴표 제외)

 

예제 입력

2
7
2 5 1 6 1 4 1
6 1 1 2 2 9 3
7 2 3 2 1 3 1
1 1 3 1 7 1 2
4 1 2 3 4 1 2
3 3 1 2 3 4 1
1 5 2 9 4 7 0
7
2 5 1 6 1 4 1
6 1 1 2 2 9 3
7 2 3 2 1 3 1
1 1 3 1 7 1 2
4 1 2 3 4 1 3
3 3 1 2 3 4 1
1 5 2 9 4 7 0

예제 출력

YES
NO
문제출저 : 알고스팟


'All > Algorithm' 카테고리의 다른 글

Sort Algorithm  (0) 2015.12.28
JUMPGAME_알고리즘  (0) 2015.12.28
FIBONACCI_알고리즘  (0) 2015.12.28
FIBONACCI_문제  (0) 2015.12.28
BOGGLEGAME_알고리즘_3  (0) 2015.12.28

1. 점화식을 이용한 일반적인 방법


생각


단계1. 먼저 피보나치 수열은 앞에서도 이야기 했지만 f(n) = f(n-1) + f(n-2)로 정의된다. 

단계2. 이 식을 점화식으로 재귀함수를 만들 수있다.

함수 내용 

 - 함수 f는 n을 입력받아 n번째 피보나치수를 리턴하는 재귀함수이다.

 - n이 2 이하 라면 1을 리턴한다..

 - n이 3 이상 이라면 f(n-1) + f(n-2)를 리턴한다.


단계3. 리턴 받은 수를 2로 나눈 나머지가 0이라면 짝수 이므로 YES, 0이 아니라면 NO를 출력한다.


코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
 
// 함수 구현
// n번째 수의 피보나치 수열을 재귀적으로 반환
long long f(int n)
{
    // 기저사례 : n이 2 이하면 1반환
    if(n <= 2)
    {
        return 1;
    }
    // 점화식 f(N) = f(N-1) + f(N-2)
    return f(n-1) + f(n-2);
}
 
int main()
{
    // 테스트 케이스
    int testCase = 0;
    // 숫자 N
    int N = 0;
    scanf("%d", &testCase);
    
    while(testCase--){
        scanf("%d", &N);
        long long result = f(N);
        // 짝수면 YES
        if(result % 2 == 0)
            printf("YES\n");
        else
            printf("NO\n");
    }
}
cs

 

결과


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
10
10
NO
10
NO
10
NO
20
NO
30
YES
40
NO
50
NO
cs


답은 구했지만 위의 코드는 함수내에서 같은 함수를 2번 호출하는 재귀함수 이므로 2^n의 시간 복잡도를 가지며 매우 오랜시간이 걸린다. 




2. 캐시활용


생각


앞에서 [BOGGLEGAME_알고리즘_3] 에서 시간을 줄일때 사용했던 방법과 같은 아이디어로 시간을 절약 할 수있다.

단계1. 캐시를 저장할 수있는 배열을 정의하고 0으로 초기화한다.

단계2. 배열의  N번째 요소가 0이라는 것은 이전에 계산된적 없는 피보나치 수라는 것으로 계산하여   캐시배열에 저장한후 리턴한다.

단계3. 배열의 N번째 요소에 0이 아닌 값이 있다는 것은 한번 계산한 값이란 의미로 그 인덱스를 바로 참조하여 리턴한다.


코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// FIBONACCI_2
 
#include <iostream>
 
// 캐시 저장 배열
long long g_CacheArr[1001] = {0,};
 
// 함수 구현
// n번째 수의 피보나치 수열을 재귀적으로 반환
long long f(int n)
{
    // 기저사례 : n이 2 이하면 1반환
    if(n <= 2)
    {
        return 1;
    }
    
    // 캐시의 해당 요소가 아직 계산되지 않은 값이라면
    // 캐시 배열에 점화식으로 계산한 값 저장
    if(g_CacheArr[n] == 0)
        return g_CacheArr[n] = f(n-1) + f(n-2);
    else// 해당요소가 이미 계산된 값이라면 캐시값 리턴
        return g_CacheArr[n];
}
 
int main()
{
    // 테스트 케이스
    int testCase = 0;
    // 숫자 N
    int N = 0;
    scanf("%d", &testCase);
    
    while(testCase--){
        // 캐시배열 초기화
        memset(g_CacheArr, 0, sizeof(g_CacheArr));
        scanf("%d", &N);
        long long result = f(N);
        // 짝수면 YES
        if(result % 2 == 0)
            printf("YES\n");
        else
            printf("NO\n");
    }
}
cs


결과


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
10
10
NO
20
NO
30
YES
40
NO
50
NO
60
YES
70
NO
80
NO
90
YES
1000
NO
cs

 


숫자가 작을때는 큰차이를 보이지 않지만 40이상만 넘어가더라도 매우 큰 차이를 확인 할 수있다. 

'All > Algorithm' 카테고리의 다른 글

JUMPGAME_알고리즘  (0) 2015.12.28
JUMPGAME_문제  (0) 2015.12.28
FIBONACCI_문제  (0) 2015.12.28
BOGGLEGAME_알고리즘_3  (0) 2015.12.28
BOGGLEGAME_알고리즘_2  (0) 2015.12.28

+ Recent posts

티스토리툴바