문제

아래 그림과 같은 규칙성을 가진다고 할 때(파스칼의 삼각형), 열번호와 행번호를 주면 해당 번호에 위치한 수를 리턴하는 함수를 제작하시오.

(행과 열번호는 0부터 시작)


1

1  1

1  2  1

1  3  3  1

1  4  6  4  1

1  5 10 10  5  1

1  6 15 20 15 6 1

...


입력: 행번호 열번호

출력: 해당 행,열에 위치한 갓


ex) 입력: 2 1

    출력: 2


풀이

파스칼의 삼각형이라는 유명한 문제이다.

규칙성을 보면,

  1) 각 행의 첫 번째와 제일 마지막 수는 1

  2) 1번 규칙 이외의 값들에 대해서는 바로 윗 행의 같은 열값과 왼쪽열값의 합: c(i,j) =  c(i-1,j-1) + c(i-1,j)


위 두가지 규칙성을 보면, 특히 두번째 규칙성을 보면 점화식형태로 되어 있고, 따라서 재귀호출을 쓰면 쉽게 구현이 되겠다.

(최적의 구현방법이라는 것은 아니다)


private int tri_num(int i, int j){

     if(j==0 || i==j) return 1;

     return tri_num(i-1,j-1) + tri_num(i-1,j);

}


위 코드도 그렇지만, 재귀호출을 사용한 코딩은 코드가 단순해지는 장점이 있지만, 항상 비효율성(중복된 계산을 반복)과 Stack Overflow의 위험성을 내포하고 있기에, 검토해봐야 한다.


위 코드에서 tri_num(5,4)를 했을 때, 메서드가 호출되는 순서를 적어보고, 중복이 있는지 생각해 보자.

(5,3)

(4,2)

(3,1)

(2,0)

1

(2,1)

(1,0)

1

(1,1)

1

(3,2)

(2,1)

(1,0)

1

(1,1)

1

(2,2)

1

(4,3)

(3,2)

(2,1)

(1,0)

1

(1,1)

1

(2,2)

1

(3,3)

1


위와 같이, 메서드가 호출되는 순서를 보면, (3,2)에 대해서 중복되서 호출되는 것을 볼 수 있다. 만약 이 값을 전역변수배열에 저장해뒀다가 사용한다면, 메서드가 다시 호출되는 중복을 없앨 수 있을 것이다. 코딩하면 아래와 같이 될 것이다.


private int tri_num_cache(int i, int j, int[][] cache){

if(j==0 || i==j) return 1;

    if(cache[i][j] != 0) return cache[i][j];

                 

    cache[i][j] = tri_num(i-1,j-1) + tri_num(i-1,j);

    return cache[i][j];

}


위 코드에서 cache 배열은 n x n 배열로 선언되어 전달될 것이다. (클래스변수로 선언해서, 파라미터로 전달되지 않게 할 수 도 있다.)


위와 같이 한 번 계산된 값을 메모리에 저장하고, 다시 계산하지 않는 것이 다이나믹프로그래밍의 핵심.

이렇게 하면 실행시간이 좀 줄어들 것이다.


근데, 과연 이 코드가 최선일까?


파스칼의 삼각형 규칙을 자세히 보면, 현재 행의 값들을 계산하기위해서는, 바로 윗 행의 값들만 알면 된다. 즉, 제일 윗행부터 계산된 값을 배열에 저장해두고, 그 값을 이용해서 바로 다음 행의 값을 계산해서 다시 배열에 넣는다면, 재귀호출을 안 쓰고도 프로그래밍이 되기에, 굉장히 빠른 시간안에 값을 구할 수 있을 것이다.

코딩하면 다음과 같다.


private int tri_num_table(int r, int c) {

int n = r + 1;

    int[][] table = new int[n][n];

 

    table[0][0] = 1;

    for (int i = 0; i < n; i++) {

    for (int j = 0; j <= i; j++) {

        if (j == 0 || i == j)

            table[i][j] = 1;

            else

            table[i][j] = table[i - 1][j - 1] + table[i - 1][j];

        }

    }

    return table[r][c];

 }


아래의 소스코드를 실행해보면 알겠지만, 테이블에 의해 저장해놓고 계산하는 것이, 재귀호출하는 것보다 비교할 수 없게 빠르다는 것을 알 수 있을 것이다. 

n = 30일 때,

  1)재귀호출: 4199 ms

  2)부분 Cache & 재귀호출: 3982 ms

  3)테이블 저장: 11 ms


소스코드

package dynamic;

 

public class PascalsTriangle {

         public PascalsTriangle() {

                  long t1, t2;

                  int n = 30;

 

                  t1 = System.currentTimeMillis();

                  test1(n);

                  t2 = System.currentTimeMillis();

                  System.out.println("Test1:" + (t2 - t1) + " mili-sec elapsed.");

 

                  System.out.println("");

 

                  t1 = System.currentTimeMillis();

                  test2(n);

                  t2 = System.currentTimeMillis();

                  System.out.println("Test2:" + (t2 - t1) + " mili-sec elapsed.");

 

                  System.out.println("");

 

                  t1 = System.currentTimeMillis();

                  test3(n);

                  t2 = System.currentTimeMillis();

                  System.out.println("Test3:" + (t2 - t1) + " mili-sec elapsed.");

         }

 

         private void test1(int n) {

 

                  for (int i = 0; i < n; i++) {

                           for (int j = 0; j <= i; j++) {

                                   System.out.print(tri_num(i, j) + " ");

                           }

                           System.out.println("");

                  }

         }

 

         private void test2(int n) {

 

                  int[][] cache = new int[n][n];

 

                  for (int i = 0; i < n; i++) {

                           for (int j = 0; j <= i; j++) {

                                   System.out.print(tri_num_cache(i, j, cache) + " ");

                                   // tri_num_cache(i,j,cache);

                           }

                           System.out.println("");

                  }

         }

 

         private void test3(int n) {

                  for (int i = 0; i < n; i++) {

                           for (int j = 0; j <= i; j++) {

                                   System.out.print(tri_num_table(i, j) + " ");                                   

                           }

                           System.out.println("");

                  }

         }

 

         private int tri_num(int i, int j) {

                  if (j == 0 || i == j)

                           return 1;

                  return tri_num(i - 1, j - 1) + tri_num(i - 1, j);

         }

 

         private int tri_num_cache(int i, int j, int[][] cache) {

                  if (j == 0 || i == j)

                           return 1;

                  if (cache[i][j] != 0)

                           return cache[i][j];

 

                  cache[i][j] = tri_num(i - 1, j - 1) + tri_num(i - 1, j);

                  return cache[i][j];

         }

 

         private void tri_num_table(int n) {

                  int[][] table = new int[n][n];

 

                  table[0][0] = 1;

                  for (int i = 0; i < n; i++) {

                           for (int j = 0; j <= i; j++) {

                                   if (j == 0 || i == j)

                                            table[i][j] = 1;

                                   else

                                            table[i][j] = table[i - 1][j - 1] + table[i - 1][j];

                                   System.out.print(table[i][j] + " ");

                           }

                           System.out.println("");

                  }

         }

 

         private int tri_num_table(int r, int c) {

                  int n = r + 1;

                  int[][] table = new int[n][n];

 

                  table[0][0] = 1;

                  for (int i = 0; i < n; i++) {

                           for (int j = 0; j <= i; j++) {

                                   if (j == 0 || i == j)

                                            table[i][j] = 1;

                                   else

                                            table[i][j] = table[i - 1][j - 1] + table[i - 1][j];

                           }

                  }

                  return table[r][c];

         }

 

         public static void main(String[] args) {

                  new PascalsTriangle();

 

         }

 

}

 

 

-끝-



맨위로
통합 검색어 입력폼