[LeetCode][Python3] 62. Unique Paths
2018.11.15 02:44
|
프로그래밍/LeetCode
Problem :
https://leetcode.com/problems/unique-paths
My Solution :
class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
memo = {}
def comb(n, r):
if r == 0 or n == r:
return 1
if r == 1 or n-1 == r:
return n
if (n, r) in memo:
return memo[(n, r)]
memo[(n, r)] = memo[(n, n-r)] = comb(n-1, r-1) + comb(n-1, r)
return memo[(n, r)]
return comb(m+n-2, min(m, n)-1)
Comment :
전형적인 DP 문제인데, 나는 문제를 보는 순간 그냥 단순 조합 문제라고 생각했다. 그래서 m+n-2 중 min(m, n)-1개를 고르는 문제로 풀었다. 물론 math.factorial 을 사용하거나 itertools.combinations를 사용하면 바로 풀린다. (combinations는 큰 수에서 timeout 발생)
하지만 조합을 직접 구현해보는 것에 초점을 맞춰서 위와 같이 풀었다. nCr = n-1Cr-1 + n-1Cr 공식이다.
왜 nCr 조합 문제라고 생각했냐면... 예를 들어 오른쪽으로 7번, 아래쪽으로 3번 움직여야 한다면 총 10번의 움직임 중 아래쪽 3번이 들어갈 자리만 지정하면 끝이다. 즉 10C3 문제라는 뜻이다.
Factorial Example :
class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
from math import factorial as fact
return fact(m+n-2) // fact(m-1) // fact(n-1)
아래는 전형적인 DP 방식 Bottom-up 으로 풀이한 것이다.
굳이 말로 풀어쓰자면 예를 들어 (5,3)에 도착하는 경우는 (4,3)에서 온 경우와 (5,2)에서 온 경우밖에 없다. 따라서 두 경우의 수를 더하면 된다.
My Solution2 :
class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [[1]*m for _ in range(n)]
for i in range(1, n):
for j in range(1, m):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]
'프로그래밍 > LeetCode' 카테고리의 다른 글
| [LeetCode][Python3] 78. Subsets (0) | 2019.01.13 |
|---|---|
| [LeetCode][Python3] 238. Product of Array Except Self (0) | 2019.01.12 |
| [LeetCode][Python3] 347. Top K Frequent Elements (0) | 2019.01.05 |
| [LeetCode][Python3] 94. Binary Tree Inorder Traversal (1) | 2019.01.03 |
| [LeetCode][Python3] 62. Unique Paths (6) | 2018.11.15 |
| [LeetCode][Python3] 55. Jump Game (0) | 2018.11.15 |
| [LeetCode][Python3] 49. Group Anagrams (0) | 2018.11.14 |
| [LeetCode][Python3] 48. Rotate Image (0) | 2018.11.13 |
| [LeetCode][Python3] 46. Permutations (0) | 2018.11.12 |
2018.11.19 04:54 신고
선생님 안녕하세요~
윈도우7 설치에 골치를 앓고 있다가
https://www.snoopybox.co.kr/1549 에 올라온 글을 참고하여
선생님 덕분에 윈도우 설치를 성공적으로 끝냈습니다.
정말 대단히 감사드립니다.
다만 한 가지 여쭤볼 것이 있는데
설치 후 부팅 시 마다 처음 (하드에서 설치하기) 파일을 실행했던 것처럼
윈도우를 설치할 것인지 부팅할 것인지 묻는 화면이 계속해서 노출되고 있습니다.
이제 설치가 완료되었으니 바로 부팅이 되었으면 하는데
어떤 부분을 수정해야 문제를 해결할 수 있을지 조언해주시면 감사하겠습니다.
늘 행복하시고 건강하시길 기원합니다.
감사합니다.
2018.11.19 15:04 신고
msconfig에서 삭제하시면 될건데, 아래 글 참조해보세요.
https://www.snoopybox.co.kr/1386
2018.11.25 00:45 신고
스누피님 항상 강좌글보면서 감사하게 참고하고 있습니다.
하나 여쭤볼께 있는데 "Differencing VHD에서 항상 깨끗한 VHD로 부팅하기" https://www.snoopybox.co.kr/1381?category=316318
강좌글을 참고하여 따라해보려고 하는데 잘되질않네요.
사진 첨부합니다. 무엇이 문제인지 확인점 부탁드립니다 ㅠ
https://postimg.cc/gallery/iooyljm0/
2018.11.26 00:29 신고
bcdedit /default 다음에 나오는 {GUID}가 두 줄 동일하네요. child1 파일을 교체할때는 child1 부팅 GUID를 default로 등록하고, child2 파일을 교체할때는 child2 부팅 GUID를 default로 등록해야겠죠.
child1용 부팅메뉴, child2용 부팅메뉴가 각각 있어야 하고 GUID는 서로 다릅니다.
2018.11.26 14:41 신고
아하 GUID값을 똑같이 입력해서 그렇군요...덕분에 해결되었습니다.
한가지만 더 여쭤봐도 될까요?
이 작업을 여러대를 해야하는데 혹시 GUID값 입력해서하는 명령어말곤 다른 방법은 없을걸까요...?
자식파일 만들면 GUID값이 다를텐데 다른방법도 있을까요???
2018.11.27 17:38 신고
그런건 직접 프로그래밍(스크립팅) 하셔야죠...