문제
아래 그림과 같은 규칙성을 가진다고 할 때(파스칼의 삼각형), 열번호와 행번호를 주면 해당 번호에 위치한 수를 리턴하는 함수를 제작하시오.
(행과 열번호는 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();
}
}
-끝-
'알고리즘 > 알고리즘(Java)' 카테고리의 다른 글
| 20. [다이나믹] 행렬 경로 문제 (0) | 2015.04.16 |
|---|---|
| 19. [다이나믹]피보나치 수열 (0) | 2015.04.14 |
| 17. [다이나믹] 다이나믹 프로그래밍 개요 (0) | 2015.04.14 |
| 14. [수치] 최대공약수 구하기 (이진 gcd 알고리즘) (0) | 2015.04.02 |
| 13. [수치] 최대공약수 구하기 (유클리드 알고리즘) (0) | 2015.04.02 |