Pascal's Triangle(파스칼 삼각형)
Pascal's Triangle(파스칼 삼각형) — #LeetCode #Pascaltrianlge #파스칼삼각형 #개발자의도구들 only 파이썬 목표 참고 : 여기 파스칼 삼각...
#LeetCode#Naver Blog
#LeetCode #Pascaltrianlge #파스칼삼각형 #개발자의도구들
- only 파이썬
- 목표 참고 : 여기
파스칼 삼각형
LeetCode(esay 110. Balanced Binary Tree)
출처: LeetCode
이렇게 만들어진 삼각형이 파스칼의 삼각형이다.
1차시도
정답
💡 idea
1. 모든 row의 양쪽 끝 index는 항상 1이다.
2. 양쪽 idex를 제외하면 이전 row의 이전 idx, 같은 idx 값이 필요하다.
>>> 메모리를 사용해서 기억해주거나, parameter로 넘겨줘야한다.
3. 배열 생성 규칙
>>> row_idx = 0부터 시작하면, 각 층의 배열 크기는 row_dix + 1이다.
>>> 각 층의 배열 크기를 n이라고 하면, idx = 0, idx = n - 1은 항상 1이다.
>>> 전체 층에 대한 정보는 전역으로 관리한다.
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
result = []
def make_row(row_idx):
row_size = row_idx + 1
row = [1 for i in range(row_size)]
# set init
if row_size == 1 or row_size == 2:
result.append(row)
return
for idx in range(1, row_size - 1):
row[idx] = result[row_idx - 1][idx - 1] + result[row_idx - 1][idx]
result.append(row)
for i in range(numRows):
make_row(i)
print(result)
return result
- 일단 맞추긴했다.
- 근데 뭔가 찜찜하다. .
⌛ 시간 복잡도
O(numRows ** 2) 수준
근거: 1. numsRows만큼 각 층별 row 생성
2. row만들 때, 업데이트 수 (numRows - 1 - 2)
줄일 수 없을까?
세가지 방안이 있다고 한다.
1. Using Recursion
-- 5 -> 4 -> 3 -> 2 -> 1 순으로 recursive
2. Using Combinatorial Formula
->
3. Using Dynamic Programming with 1D Array
>>> 이거 내가 했던거랑 빗스
>>> 근데 이것도 recursive랑 비슷함
class Solution:
def generate(self, numRows):
result = [1]
if numRows == 1:
return result
prev = self.generate(numRows - 1)
for i in range(1, numRows - 1):
result.append(prev[i - 1] + prev[i])
result.append(1)
return result
- 음.. 일단 recursive로 원하는 row 배열을 구하는것은 완료
- 문제는 전체 배열을 어떻게 관리해야할지가 관건이다.
❌🙅🙅🙅🙅❌
class Solution:
def __init__(self):
self.results = []
def generate(self, numRows):
result = [1]
if numRows == 1:
self.results.append(result)
return result
prev = self.generate(numRows - 1)
for i in range(1, numRows - 1):
result.append(prev[i - 1] + prev[i])
result.append(1)
self.results.append(result)
return self.results
- result를 이런식으로 관리하는건 의미가 없다. generate에서 return으로 self.resultf를 return하기 때문에 이상한 값이 나온다.
🤔 generate는 항상 자기 자신만을 return 하는데 전체 결과를 어떻게 가져와야 하는가?
>> 아무리 생각해봐도 dp를 함께 사용해야할 것 같다. ❌
✅ 🙆🙆♂️🙆♀️🆗 ✅
class Solution:
def generate(self, numRows):
row = [1 for i in range(numRows)]
if numRows == 1:
return [[1]]
prev = self.generate(numRows - 1)
for i in range(1, numRows - 1):
row[i] = prev[-1][i - 1] + prev[-1][i]
prev.append(row)
return prev
- 초기값을 \[\[1\]\]로 셋팅해준다
- 이후 prev = \[\[\]\] 형태가 되고, prev\[-1\]은 항상 이전 층의 row가 된다.
- 마지막에 현재 row를 prev에 붙여서 내보낸다!
python detail 잡아가기
앞으로 이 코너는 꼭 넣자... ptrhon이 여전히 미흡하다.
1. 배열을 모두 1로 초기화하기
🙅 arr = [1 * wanted_size] = [wanted_size]가 된다.
✅ arr = [1 for i in range(wnated_size)] = [1, 1, 1 ,1 ...]
2. range 범위
🙅 for i range(1, 1):
i = 1통과한다. -> 틀렸다.
✅ i = 1을 거치지 못함
후기
이런 쉬운 문제에도 충분히 배울 수 있는 부분은 많다!!