Pascal's Triangle

Q: 파스칼의 삼각형을 생성하는 시간 복잡도는 얼마인가요?

각 행을 바로 위 행에서 만드는 데는 행이 n 개일 때 O(n²) 시간이 걸립니다. 삼각형에는 약 n²/2 개의 항목이 있고 각 항목은 한 번의 덧셈으로 계산되기 때문입니다. 출력의 모든 항목을 작성해야 하므로 이는 최적입니다. 출력 외에는 O(1) 의 추가 공간을 사용합니다.

Q: 파스칼의 삼각형은 이항 계수와 어떤 관련이 있나요?

0부터 세는 행 r 의 항 k 는 이항 계수 C(r, k) 이며, 이는 r 개 중에서 k 개를 선택하는 방법의 수입니다. 각 항이 바로 위에 있는 두 항의 합이라는 규칙은 항등식 C(r, k) = C(r-1, k-1) + C(r-1, k) 입니다. 이것이 행 r 의 합이 2^r 이 되는 이유이기도 합니다.

Q: 그 위의 행들을 만들지 않고 행 하나를 계산할 수 있나요?

네. 1에서 시작해 이전 항목으로부터 다음 항목을 각각 구합니다: C(r, k) = C(r, k-1) × (r-k+1) / k . 나눗셈이 정확히 이루어지도록 나누기 전에 곱하고, 곱셈 결과에는 64비트 정수를 사용하세요. 그러면 행 r 을 다른 행 없이 O(r) 시간에 구할 수 있습니다.

Q: 파스칼의 삼각형은 왜 동적 프로그래밍 문제인가요?

각 항목은 두 개의 더 작은 하위 문제에 의존하며, 그 위에 있는 항목들과 해당 하위 문제들은 서로 많이 겹칩니다. 단순 재귀는 이를 계속해서 다시 계산합니다. 행을 순서대로 구성하면 각 하위 문제를 한 번만 저장하고 재사용하므로, 지수 시간이 걸리는 작업이 O(n²) 으로 줄어듭니다.

쉬움동적 계획법

+10

파스칼의 삼각형에서 첫 번째 행은 [1]입니다. 이후의 각 행은 항목이 하나 더 많고, 1로 시작하고 끝나며, 그 사이의 각 항목은 바로 위에 있는 두 항목의 합입니다. 정수 numRows가 주어집니다. 삼각형의 처음 numRows개 행을 맨 위 행부터 각 행을 정수 배열로 반환하세요.

함수

generate(numRows: integer) → integer-2d-array

numRowsinteger: 삼각형을 만들 행의 수
반환값integer-2d-array: 첫 번째 numRows개의 행, 맨 위 행부터

제약 조건

1 ≤ numRows ≤ 30
처음 30개 행의 모든 항목은 32비트 부호 있는 정수로 표현할 수 있습니다. 가장 큰 값은 77558760이며, 30번째 행의 가운데에 있습니다.

예제

입력: numRows = 5
출력: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
설명: 각 내부 항목은 바로 위에 있는 두 항목을 더한 값입니다. 네 번째 행에서는 3 = 1 + 2이고 3 = 2 + 1입니다. 다섯 번째 행에서는 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1입니다.

입력: numRows = 1
출력: [[1]]
설명: 행이 하나일 때 삼각형은 맨 위 부분인 [1]뿐입니다.

제출 시 숨은 테스트 +13개

후속 질문

위쪽 행들을 유지하는 대신, 한 배열에서 마지막 행만 만들고 행마다 그 값을 바로 갱신할 수 있을까요? 내부 루프는 어떤 방향으로 실행해야 하며, 그 이유는 무엇인가요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

삼각형을 정의하는 규칙은 재귀적입니다. 각 항목은 바로 위 행의 두 항목을 더한 값입니다. 모든 항목에 대해 이 규칙을 처음부터 계산하면 같은 값을 계속해서 다시 계산하게 되고, 행이 하나 늘어날 때마다 작업량이 두 배가 됩니다. 반환하라는 행은 더 작은 문제들에 대한 저장된 답이므로, 삼각형을 위에서 아래로 만들고 각 행을 그전에 만든 행에서 읽어 오세요.

모든 항목을 재귀적으로 계산하기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

행과 각 행 안의 위치를 0부터 매깁니다. 삼각형의 정의는 함수로 바뀝니다. entry(row, col)은 col이 0이거나 row와 같을 때, 즉 두 가장자리에 있을 때 1이고, 그 외에는 entry(row-1, col-1) + entry(row-1, col)입니다. 모든 행의 모든 위치에 대해 이 함수를 호출하면 삼각형이 완성됩니다. 정의를 글자 그대로 구현했으므로 올바릅니다.

문제는 함수가 너무 많이 호출된다는 것입니다. 재귀는 가장자리에서만 멈추고, 그때 1을 반환하므로 값이 v인 항목을 계산하려면 약 2v번 호출해야 합니다. 행 r의 값들을 모두 더하면 2^r이 되므로, 30개 행을 계산하려면 총 약 2^31번, 즉 20억 번이 넘는 호출이 필요합니다. 같은 작은 항목을 수백만 번 다시 계산합니다. entry(2, 1)은 그 아래에 있는 거의 모든 값의 계산에 포함됩니다.

알고리즘

entry(row, col)을 작성하세요. col이 0이거나 col이 row와 같으면 1을 반환합니다.
그렇지 않으면 entry(row-1, col-1) + entry(row-1, col)을 반환합니다.
0부터 numRows-1까지 각 row에 대해, 0부터 row까지 모든 col의 entry(row, col)을 모읍니다.
행의 목록을 반환합니다.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

위 행을 바탕으로 각 행을 만드세요

핵심 아이디어

재귀 버전은 계속 이전 행의 항목을 요청하고, 어차피 그 행들을 만들고 있습니다. 그러니 위에서 아래로 순서대로 행을 계산하고, 행 r을 채울 때 이미 완성된 행 r-1에서 필요한 값을 바로 읽으세요. 그러면 각 항목을 계산하는 데 덧셈 한 번이면 됩니다. 이것이 가장 기본적인 형태의 동적 프로그래밍입니다. 더 작은 답을 담은 표 자체가 결과물입니다.

행 r을 r + 1개의 1로 시작하면 양쪽 끝이 설정됩니다. 그런 다음 1부터 r-1까지의 각 내부 위치 c에 above[c-1] + above[c]를 설정합니다. 행 0과 1에는 내부 위치가 없으므로, 특별한 경우를 따로 처리하지 않아도 [1]과 [1, 1]로 유지됩니다.

삼각형에는 1 + 2 + ... + n, 즉 약 n²/2개의 항목이 있으며, 각 항목을 계산하는 데 상수 시간이 걸리므로 작업량은 O(n²)입니다. 어차피 반환해야 하는 출력 외에는 추가 메모리가 필요하지 않습니다. numRows = 30이면 20억 번의 호출 대신 465개의 항목만 계산하면 됩니다.

알고리즘

행이 비어 있는 목록으로 시작합니다.
0부터 numRows-1까지 각 row에 대해 row + 1개의 1을 만듭니다.
1부터 row-1까지 각 col에 대해 이전 행의 col-1 위치와 col 위치의 합으로 설정합니다.
행을 추가하고 계속합니다. 목록을 반환합니다.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

함정과 경계 사례

반복문은 짧으므로 실수는 경계와 첫 번째 행에 관한 것입니다.

numRows + 1개의 행을 반환하기. 행 번호를 0부터 매기면 필요한 마지막 행은 numRows-1입니다.
내부 반복문을 가장자리까지 실행하기. 위치 0에는 왼쪽 부모가 없고 위치 row에는 오른쪽 부모가 없으므로, 그 위치에서 above[col-1] 또는 above[col]를 읽으면 범위를 벗어납니다. 위치 1부터 row-1까지만 채우세요.
작은 행에서 문제가 생기는 범위를 작성하기. Swift의 1..<row는 row가 0일 때 오류가 발생하고, R의 2:(row-1)은 row가 2일 때 1까지 거꾸로 셉니다. 조건을 추가하거나, 내부 위치를 1로 초기화하여 행 0과 1에서는 반복문이 필요 없게 하세요.
팩토리얼로 항목을 계산하기. C(29, 14)는 int에 들어가지만 29!는 64비트 정수에서도 오버플로가 발생하므로, 팩토리얼을 기반으로 만든 공식은 아래쪽 행에서 잘못된 숫자를 출력합니다.
모든 행에 배열 하나를 재사용하기. 매번 같은 배열을 추가한 다음 변경하면, 결과의 모든 행이 마지막 행과 같아집니다.

자주 묻는 질문4

파스칼의 삼각형을 생성하는 시간 복잡도는 얼마인가요?

각 행을 바로 위 행에서 만드는 데는 행이 n개일 때 O(n²) 시간이 걸립니다. 삼각형에는 약 n²/2개의 항목이 있고 각 항목은 한 번의 덧셈으로 계산되기 때문입니다. 출력의 모든 항목을 작성해야 하므로 이는 최적입니다. 출력 외에는 O(1)의 추가 공간을 사용합니다.

파스칼의 삼각형은 이항 계수와 어떤 관련이 있나요?

0부터 세는 행 r의 항 k는 이항 계수 C(r, k)이며, 이는 r개 중에서 k개를 선택하는 방법의 수입니다. 각 항이 바로 위에 있는 두 항의 합이라는 규칙은 항등식 C(r, k) = C(r-1, k-1) + C(r-1, k)입니다. 이것이 행 r의 합이 2^r이 되는 이유이기도 합니다.

그 위의 행들을 만들지 않고 행 하나를 계산할 수 있나요?

네. 1에서 시작해 이전 항목으로부터 다음 항목을 각각 구합니다: C(r, k) = C(r, k-1) × (r-k+1) / k. 나눗셈이 정확히 이루어지도록 나누기 전에 곱하고, 곱셈 결과에는 64비트 정수를 사용하세요. 그러면 행 r을 다른 행 없이 O(r) 시간에 구할 수 있습니다.

파스칼의 삼각형은 왜 동적 프로그래밍 문제인가요?

각 항목은 두 개의 더 작은 하위 문제에 의존하며, 그 위에 있는 항목들과 해당 하위 문제들은 서로 많이 겹칩니다. 단순 재귀는 이를 계속해서 다시 계산합니다. 행을 순서대로 구성하면 각 하위 문제를 한 번만 저장하고 재사용하므로, 지수 시간이 걸리는 작업이 O(n²)으로 줄어듭니다.

Python

def generate(numRows):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

입력

numRows = 5

기대값

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]