[Algorithm] 파스칼의 삼각형 알고리즘 구현하기 (Java)

 

 

파스칼의 삼각형이란 ❓

 

파스칼의 삼각형(Pascal's Triangle)은 수학에서 사용되는 삼각형 배열로, 각 행은 이항 계수(binomial coefficients)로 구성됩니다.

 

파스칼의 삼각형은 다음과 같은 규칙이 있습니다.

 

• 모든 행은 1로 시작하고 1로 끝납니다
• 각 숫자는 위 양쪽의 숫자를 더한 값입니다
• n번째 행의 숫자들의 합은 2^n입니다
• 각 행의 숫자들은 해당 행 번호의 조합(nCr)을 나타냅니다

 

수학적 표현

• n : 행 번호 (0부터 시작)
• k : 해당 행에서의 위치 (0부터 시작)

파스칼의 삼각형 구현하기 Java

import java.util.Arrays;

public class PascalTriangleDP {

    public static int[][] generate(int numRows) {
        // DP 테이블 초기화
        int[][] dp = new int[numRows][numRows];

        for (int i = 0; i < numRows; i++) {
            // 각 행의 첫 번째와 마지막 값은 항상 1
            dp[i][0] = 1;
            dp[i][i] = 1;

            // 중간 값 계산
            for (int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }

        return dp;
    }

    public static void printTriangle(int[][] dp, int numRows) {
        for (int i = 0; i < numRows; i++) {
            // 행의 유효한 값만 출력
            for (int j = 0; j <= i; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int numRows = 5; // 원하는 행 수
        int[][] pascalTriangle = generate(numRows);
        printTriangle(pascalTriangle, numRows);
    }
}

 

1. generate(int numRows)

• 2차원 배열 dp를 사용해 파스칼의 삼각형을 저장합니다.
• 각 행의 첫 번째와 마지막 요소는 항상 1로 초기화됩니다.
• 나머지 값은 동적 계획법의 점화식을 사용하여 계산합니다

 

• d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + d p [ i − 1 ] [ j ]
• dp[i][j]는 현재 위치의 값이고, dp[i-1][j-1]과 dp[i-1][j]는 바로 위 행의 두 인접한 값입니다.

2. printTriangle(int[][] dp, int numRows)

• 생성된 2차원 배열을 출력합니다.
•  각 행의 유효한 값들만 출력합니다.

// 출력
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1