오늘의 주제도 동적계획법
문제
입력과 출력
코드
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
arr=[0] * (numRows) #2차원 배열 생성하는 법
for i in range(len(arr)):
arr[i] = [0] * (i+1)
for i in range(numRows):
for j in range(i+1):
if i<2:
arr[i][j]=1
else:
if j==0 or j==i:
arr[i][j]=1
else:
arr[i][j]=arr[i-1][j-1]+arr[i-1][j]
return arr파스칼 삼각형
파스칼 삼각형이란 이항계수를 삼각형 모양으로 나열한 것
삼각형을 그리는 규칙은 다음과 같다.
(1) 숫자가 들어갈 칸을 첫 번째 줄에는 1개, 두 번째 줄에는 2개, 세 번째 줄에는 3개 이런 식으로 한 줄씩 내려가면 한 칸씩 늘어나게 정삼각형 모양으로 만든다.
(2) 첫 번째 줄과 두 번째 줄의 3칸에는 1을 쓴다.
(3) 세 번째 줄부터는 줄의 양쪽 끝 칸에는 1을 쓰고 나머지 칸에는 바로 윗줄에 위치한 칸 중 해당 칸과 인접해 있는 두 칸의 숫자를 더해서 그 값을 쓴다.
출처: 나무위키
알고리즘
먼저 2차원 배열을 생성해준다.
numRows 크기만큼의 배열을 생성해주고, 이 배열안에 각 또 각각 numRows 만큼의 크기 배열을 넣어 준다.
삼각형의 두번째 줄까지(numRows<2)는 1로 채워준다.
그 뒤부터는 첫번째와 마지막 요소느 1로 채우고 나머지는 각각의 전행렬들의 값을 더하여 넣어준다.
회고
처음에 써내려간 코드!
알고리즘은 비슷하지만 인덱스 설정이나 각각의 조건 디테일이 틀렸었다.
for문을 중복해서 적어주었던 부분을 제거해주었더니 1은 채워졌으나 전 배열의 요소들이 더해지지는 않았다.
이 결과를 보니 전체 배열을 하나 더 생성하여 돌고 있어서
arr=[0] * (numRows)
이부분을 numRows+1->numRows로 변경해주고
for i in range(numRows):
for j in range(i+1):
if i<2:
arr[i][j]=1
이 부분도 numRows+1->numRows 로 바꾸고
전체적으로 인덱스가 안맞는 부분들을 수정해주었다.
완성된 모습 !!
오랜만에 시간안에 문제를 풀어서 뿌듯했다 ㅎㅅㅎ
좀 촉박했지만 !
2차월 배열을 생성하는 코드를 새로 알았다.
자주 쓰일 거 같으니 꼭 기억해두자!
알고리즘을 작성하는 데에 조금씩 익숙해지고 있는 것 같다 ㅎㅎ
