[알고리즘] 파스칼의 삼각형

[문제] 아래 그림과 같은 규칙성을 가진다고 할 때, 열번호와 행번호를 주면 해당 번호에 위치한 수를 리턴하는 함수를 제작하시오(행과 열번호는 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번 규칙 이외의 값들에 대해서는 바로 윗 행의 같은 열값과 왼쪽열값의 합

위 두가지 규칙성을 보면, 특히 두번째 규칙성을 보면 점화식형태로 되어 있고, 따라서 재귀호출을 쓰면 쉽게 구현이 되겠다. (최적의 구현방법이라는 것은 아니다)

    private static int triangleNum(int i, int j) {
        if(j==0 || i==j) return 1;
        return triangleNum(i-1, j-1) + triangleNum(i-1, j);
    }

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

위 코드에서 triangleNum(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)에 대해서 중복되서 호출되는 것을 볼 수 있다. 만약 이 값을 전역변수배열에 저장해뒀다가 사용한다면, 메서드가 다시 호출되는 중복을 없앨 수 있을 것이다. 코딩하면 아래와 같이 될 것이다.

 public class PascalTriangle {
    public PascalTriangle() {
        long time1, time2;
        int n = 30;

        time1 = System.currentTimeMillis();
        test1(n);
        time2 = System.currentTimeMillis();
        System.out.println("\nTest1:" + (time2 - time1) + " mili-sec elapse.");

        time1 = System.currentTimeMillis();
        test2(n);
        time2 = System.currentTimeMillis();
        System.out.println("\nTest2:" + (time2 - time2) + " mili-sec elapse.");
        
        time1 = System.currentTimeMillis();
        test3(n);
        time2 = System.currentTimeMillis();
        System.out.println("\nTest3:" + (time2 - time2) + " mili-sec elapse.");
    }
    
    private void test1(int n) {
        for(int i=0; i<n; i++) {
            for(int j=0; j <= i; j++) {
                System.out.print(triangleNum(i, j) + "");
            }
            System.out.print("");
        }
    }
    
    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(triangleNumCache(i, j, cache) + "");
            }
            System.out.print("");
        }
    }

    private void test3(int n) {
        for (int i=0; i<n; i++) {
            for(int j=0; j<=i; j++) {
                System.out.print(triangleNumTable(i, j) + " ");
            }
            System.out.print("");
        }
    }
    
    private static int triangleNum(int i, int j) {
        if(j==0 || i==j) return 1;
        return triangleNum(i-1, j-1) + triangleNum(i-1, j);
    }
    
    private static int triangleNumCache(int i, int j, int[][] cache) {
        if(j==0 || i==0) return 1;
        if(cache[i][j] != 0) return cache[i][j];
        
        cache[i][j] = triangleNum(i-1, j-1) + triangleNum(i-1, j);
        return cache[i][j];
    }
    
    private static int triangleNumTable(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 PascalTriangle();
    }
}