반응형
https://leetcode.com/problems/triangle/
문제:
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
삼각형 모양의 배열을 입력받아 순차적으로 내려가면서 i, i+1중에 이동하면서 최솟값을 찾아 더해줍니다. 처음 문제를 봤을 때 DP로 풀어야 할 것 같아 점화식을 먼저 찾아보았습니다.
간단하게 보자면 윗 레벨의 위치에서 바로 아래 레벨의 i, i+1번째 중 최소값을 찾아 더 해주면 되겠네요
def minimumTotal(self, triangle: List[List[int]]) -> int:
# DP로 풀기~
n = len(triangle)
dp = [[0]*(n+1) for _ in range(n+1)]
for level in range(n-1,-1,-1):
for i in range(level+1):
dp[level][i] = triangle[level][i] + min(dp[level+1][i], dp[level+1][i+1])
return dp[0][0]
bottom -> top으로 올라가면서 + 해준 값을 상위 레벨의 값을 더 해주고 최종적으로 맨꼭대기에 있는 것을 반환해주면 됩니다.
DFS로 풀어보면
def minimumTotal(self, triangle: List[List[int]]) -> int:
@cache
def dfs(level, i):
return 0 if level >= len(triangle) else triangle[level][i]+ min(dfs(level+1,i), dfs(level+1,i+1))
return dfs(0,0)
이런 식으로 풀어볼 수 있겠네요
@cache를 사용해주지 않으면
이처럼 타임아웃 납니다. DFS 인접 행렬로 풀었을 경우 시간 복잡도가 O(N^2)이기 때문에 문제에서 제한한 O(N)에 미치지 못합니다. 하지만 @cache를 사용하면 캐싱을 통해 메모이제이션 기법을 사용하여 최적화를 하여 DFS로 풀 수 있습니다. (근데 이렇게 풀어도되나?...)
반응형
'혼자 공부하는 것들 > 알고리즘' 카테고리의 다른 글
221. Maximal Square (0) | 2023.01.09 |
---|---|
11. Container With Most Water (+Python) (0) | 2021.11.08 |
94. Binary Tree Inorder Traversal (leetcode Python) +DFS로 풀기 (0) | 2021.11.02 |
200. Number of Islands (leetcode python) +DFS로 풀기 (0) | 2021.10.29 |
2. Add Two Numbers (leetcode python) (0) | 2021.10.27 |
댓글