Pascal's Triangle
파스칼의 삼각형에서 첫 번째 행은 [1]입니다. 그 뒤의 각 행은 항목이 하나 더 많고, 1로 시작하고 끝나며, 그 사이의 각 항목은 바로 위에 있는 두 항목의 합입니다. 정수 numRows가 주어집니다. 삼각형의 처음 numRows개 행을 맨 위 행부터 각 행을 정수 배열로 반환하세요.
함수
- 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]만 있습니다.
후속 질문
배열 하나만 유지하고 행마다 그 배열을 직접 업데이트할 수 있을까요? 내부 반복문은 어느 방향으로 실행해야 하며, 그 이유는 무엇인가요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
행 0은
[1]이고 행 1은[1, 1]입니다. 행r의 길이는 얼마이며, 첫 번째 항목과 마지막 항목은 무엇인가요?각 내부 항목에는 바로 위 행의 값 두 개만 필요합니다. 행을 순서대로 만들면, 그 행이 필요할 때는 항상 이미 완성되어 있습니다.
새로운 각 행을 모두 1로 시작하세요. 그런 다음 각 내부 위치
c에 대해 이전 행의 위치c-1과c를 더하세요. 행을 추가하고 다음으로 넘어가세요.
풀이
각 항목은 바로 위 행에 있는 두 항목의 합입니다. 모든 항목에 대해 이 규칙을 처음부터 다시 계산하면 같은 값이 반복해서 계산되고, 행이 하나 늘어날 때마다 작업량은 두 배가 됩니다. 반환하는 행들은 더 작은 문제들에 대한 저장된 답이므로, 삼각형을 위에서 아래로 쌓아 각 행을 바로 앞 행에서 만드세요.
모든 항목을 재귀적으로 계산하기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
행과 위치는 0부터 번호를 매깁니다. 정의는 함수가 됩니다. entry(row, col)은 가장자리에서 1이며, 여기서 col은 0 또는 row이고, 그 외에는 entry(row-1, col-1) + entry(row-1, col)입니다. 정의 그대로이므로 올바릅니다.
재귀는 가장자리에서만 멈추고, 가장자리는 1을 반환하므로 값이 v인 항목은 약 2v번 호출됩니다. 행 r의 합은 최대 2^r이므로, 30개 행에는 약 2^31번, 즉 20억 번이 넘는 호출이 필요합니다.
알고리즘
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 + 1개의 1로 시작하면 양쪽 끝이 설정되므로, 내부 위치가 없는 행 0과 1에는 별도의 처리가 필요하지 않습니다. 삼각형에는 1 + 2 + ... + n, 즉 대략 n²/2개의 항목이 있으므로, 출력 이외의 메모리를 사용하지 않고 작업량은 O(n²)입니다. 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에는 오른쪽 부모가 없으므로, 이 위치를 읽으면 범위를 벗어납니다. - 작은 행에서 문제가 생기는 범위. Swift의
1..<row는row가 0일 때 오류가 발생하고, R의2:(row-1)은row가 2일 때 1까지 카운트다운합니다. - 팩토리얼로 항목을 계산하는 것.
C(29, 14)는 int에 들어가지만,29!은 64비트 정수에서도 오버플로가 발생합니다. - 모든 행에 같은 배열을 추가한 다음 변경하는 것. 답에 있는 모든 행이 마지막 행이 됩니다.
자주 묻는 질문3
파스칼의 삼각형을 생성하는 시간 복잡도는 얼마인가요?
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로, r개의 항목으로 만들 수 있는 부분집합의 수입니다.
위에 있는 행들을 만들지 않고도 한 행을 계산할 수 있나요?
네. 1에서 시작해 각 항목을 이전 항목으로부터 구합니다: C(r, k) = C(r, k-1) × (r-k+1) / k. 나눗셈이 정확히 나누어떨어지도록 나누기 전에 곱하고, 곱셈 결과에는 64비트 정수를 사용하세요. 그러면 행 r을 구하는 데 O(r) 시간이 걸립니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def generate(numRows):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자
numRows = 5
예상 출력
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]