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_J
    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_J
    2018.11.26 14:41 신고

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