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]


  1. 질문자
    2018.11.19 04:54

    선생님 안녕하세요~
    윈도우7 설치에 골치를 앓고 있다가
    https://www.snoopybox.co.kr/1549 에 올라온 글을 참고하여
    선생님 덕분에 윈도우 설치를 성공적으로 끝냈습니다.
    정말 대단히 감사드립니다.
    다만 한 가지 여쭤볼 것이 있는데
    설치 후 부팅 시 마다 처음 (하드에서 설치하기) 파일을 실행했던 것처럼
    윈도우를 설치할 것인지 부팅할 것인지 묻는 화면이 계속해서 노출되고 있습니다.
    이제 설치가 완료되었으니 바로 부팅이 되었으면 하는데
    어떤 부분을 수정해야 문제를 해결할 수 있을지 조언해주시면 감사하겠습니다.
    늘 행복하시고 건강하시길 기원합니다.
    감사합니다.

  2. BlogIcon sH..
    2018.11.25 00:45 신고

    스누피님 항상 강좌글보면서 감사하게 참고하고 있습니다.
    하나 여쭤볼께 있는데 "Differencing VHD에서 항상 깨끗한 VHD로 부팅하기" https://www.snoopybox.co.kr/1381?category=316318
    강좌글을 참고하여 따라해보려고 하는데 잘되질않네요.
    사진 첨부합니다. 무엇이 문제인지 확인점 부탁드립니다 ㅠ
    https://postimg.cc/gallery/iooyljm0/

    • BlogIcon snoopybox
      2018.11.26 00:29 신고
      수정 및 삭제

      bcdedit /default 다음에 나오는 {GUID}가 두 줄 동일하네요. child1 파일을 교체할때는 child1 부팅 GUID를 default로 등록하고, child2 파일을 교체할때는 child2 부팅 GUID를 default로 등록해야겠죠.

      child1용 부팅메뉴, child2용 부팅메뉴가 각각 있어야 하고 GUID는 서로 다릅니다.

  3. BlogIcon sH..
    2018.11.26 14:41 신고

    아하 GUID값을 똑같이 입력해서 그렇군요...덕분에 해결되었습니다.
    한가지만 더 여쭤봐도 될까요?
    이 작업을 여러대를 해야하는데 혹시 GUID값 입력해서하는 명령어말곤 다른 방법은 없을걸까요...?
    자식파일 만들면 GUID값이 다를텐데 다른방법도 있을까요???