[LeetCode] 62. Unique Paths

말하는 감자·2024년 11월 21일
dynamic programmingleetcodepython동적 프로그래밍리트코드코딩테스트코딩테스트 준비파이썬
1

LeetCode

목록 보기
14/32
post-thumbnail

오늘 문제는 개인적으로 많이 어려웠지만 배운점이 많은 문제입니다. 한 번 살펴보겠습니다.

1. 오늘의 학습 키워드

  • Graph
  • Dynamic Programming
  • Top-Down
  • Bottom-Up
  • Combinations

2. 문제: 62. Unique Paths

Description

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

  • 1 <= m, n <= 100

3. 문제 풀이

m x n 그리드 위에 로봇이 있습니다. 이 로봇의 처음 위치는 좌측 상단 모서리에 위치해 있으며 우측 하단 모서리로 이동하려고 합니다. 로봇은 한 번에 오른쪽이나 아래쪽으로만 움직일 수 있습니다.

두 정수 m과 n이 주어졌을 때, 로봇이 우측 하단 모서리에 도달할 수 있는 가능한 unique paths의 수를 반환하는 문제입니다.

그리고 테스트 케이스는 답이 2∗1092 * 10^9 이하가 되도록 생성이 된다고 합니다.

문제를 이해하러 가보겠습니다.

Step1. 문제 이해하기

  • Input:
    • 정수 m과 n이 주어지며, 1이상 100이하의 값을 가집니다.
  • Output:
    • 가능한 unique paths의 수를 반환합니다.

해당 문제의 input과 output에서 직접적으로 어떤 알고리즘을 구현해야 하는지 바로 떠오르지 않았습니다. 하지만 문제가 요구하고자 하는 것은 좌측 상단(0,0)에서 우측 하단(m - 1, n - 1)까지 가는 unique 경로를 구하는 것이며, 이동할 때 오른쪽 방향과 아래쪽 방향으로만 움직이는 것을 확인할 수 있습니다.

이것을 통해 완전 탐색으로 바로 구하면 어떨까? 라는 것이 떠올랐습니다.

그럼 문제를 좀 더 자세하게 분석해보겠습니다.

Step2. 문제 분석하기

Step1에서 문제를 읽고 문제가 원하고자 하는 답이 무엇이고, 현재 문제에서 주어진 내용들이 어떤것인지를 파악했습니다. 하지만 아직 마지막 문장을 확인 못했는데요.

바로, 테스트 케이스의 답이 2∗1092 * 10^9 이하라는 내용입니다. 이것이 내포하는 의미가 뭘까요?

저는 이것을 보고 두 가지가 떠올랐습니다.

  1. 나오는 결과가 정수형 값이다.
    1. int형 자료의 범위는 −231-2^{31} ~ 231−12^{31} - 1입니다. 2∗1092 * 10^9 값은 이 안에 포함됩니다.
  2. m과 n의 최댓값은 100, 100 인데 100일 경우에 나오는 반환값이 이 근처로 나오는구나!

생각보다 큰 도움이 된 것 같지는 않지만, 이렇게 문제의 모든 부분을 파악하는 것은 정말 중요하다고 생각합니다.

자, 이제 그럼 실제 예시에서 좀 더 분석을 진행해보겠습니다. 우선 갈 수 있는 모든 경로를 탐색하는 완전 탐색을 통해 혹시 규칙이나 더 나은 알고리즘이 있는지 확인해보겠습니다.

  1. m = 3, n = 2

해당 경우에 unique paths는 총 3개입니다. 그런데 이 3가지 경로에 공통점이 보입니다.

아래로 가는 방향이 2번, 오른쪽으로 가는 방향이 1번인 공통점이 있습니다. 다만 이것을 어떻게 조합하냐에 따라 다른것이죠.

방금 제가 조합이라 했습니다. 조합을 활용하면 구할 수 있을거라는 생각이 듭니다. 하지만 또 다른 예시를 봐야 더 확신이 들겠죠?

다음 예시입니다.

  1. m = 6, n = 3

이 예시에서도 모든 경우를 다루진 않았지만 공통점이 1번 예시와 동일하게 나옵니다.

그렇다는 것은 조합으로 풀수도 있다는 것입니다.

수식적으로 생각해보면 타당하다는 것을 알 수 있습니다.

저희는 좌측 상단 (0,0)에서 우측 하단 (m - 1, n - 1)까지 향하며, 아래 방향과 오른쪽 방향으로만 이동해서 갈 수 있습니다. 이것은 아래 방향 m -1개, 오른쪽 방향 n - 1개에서 m - 1개 또는 n - 1개의 조합을 떠오르는 경우와 같다는 것을 알 수 있습니다.

그렇다면, 1번 예시는 3C2 또는 3C1입니다. 2번 예시는 8C3 또는 8C5입니다. 이것을 수식으로 나타내면 다음과 같습니다.

Cm+n−2m−1=(m+n−2)!(m−1)!⋅(n−1)!C_{m + n - 2}^{m - 1} = \frac{(m + n - 2)!}{(m - 1)! \cdot (n - 1)!}

이렇게, 완전 탐색으로 풀려고 했지만 조합으로 풀릴 수 있는 것을 확인했습니다. 그럼에도 불구하고 완전 탐색을 어떻게 할 수 있을까요?

해당 문제는 아래쪽 방향, 오른쪽 방향으로 이동할 수있습니다. 목적지는 (m - 1, n - 1)입니다. 그럼 목적지의 왼쪽과 위쪽 위치에서의 경로를 다 합하면 목적지까지 가는 unique paths를 알 수 있지 않을까요?

즉, 재귀 함수를 사용하면 되는 것입니다.

첫 번 째 예시를 다시 살펴보겠습니다.

아래 방향을 빨간색, 오른쪽 방향을 파란색으로 표시했습니다. 우측 그림은 재귀 트리라고 보시면 될 것 같습니다.

이렇게 재귀 함수를 사용한다면 코드 구현이 가능합니다. 재귀 함수의 시간 복잡도는 O(2m+n)O(2^{m+n}) 입니다. 그러면 2^200이니까 시간 초과가 날 것으로 보입니다..

하지만! 우측 트리를 보면서 눈치를 채셨나요? 바로 중복되는 값이 있습니다. (0, 0), (1, 0)이 중복되는 것을 확인할 수 있습니다. 그렇다는 것은 Dynamic Programming을 통해서도 구현이 가능하다는 것입니다! 그렇게 되면 아래 처럼 구성되기 때문에 시간 복잡도는 O(m∗n)O(m * n)이 나옵니다.

그럼!! 이제 코드 설계를 해보겠습니다.

Step3. 코드 설계

문제는 다양한 접근법으로 해결할 수 있으며, 각 방법의 효율성은 다릅니다. 아래는 각 방식의 설계 과정을 간략히 설명합니다.

1. 조합을 이용한 접근

이 문제는 "조합"을 활용하여 매우 간단히 해결할 수 있습니다.

  1. 경로의 총 이동 횟수는 (m-1)번 아래로 가는 이동과 (n-1)번 오른쪽으로 가는 이동의 합입니다.
  2. 따라서, 전체 경로 중 (m-1)번의 아래 이동을 선택하는 경우의 수를 계산하면 됩니다.
    • 수식: Cm+n−2m−1=(m+n−2)!(m−1)!(n−1)!C_{m+n-2}^{m-1} = \frac{(m+n-2)!}{(m-1)!(n-1)!}
  3. 시간 복잡도는 O(m + n)이며, 계산 과정에서 factorial 함수를 사용합니다.

2. 완전 탐색을 이용한 접근

완전 탐색은 모든 가능한 경로를 재귀적으로 계산합니다.

  1. 시작 지점 (0, 0)에서 목표 지점 (m-1, n-1)로 이동합니다.
  2. 현재 위치에서 아래로 이동하거나 오른쪽으로 이동하는 두 가지 선택지가 있습니다.
  3. 종료 조건:
    • (0, 0)에 도달하면 경로를 1개로 카운트합니다.
    • 범위를 벗어나면 종료합니다.
  4. 시간 복잡도는 O(2m+n)O(2^{m+n})로 매우 비효율적입니다.

3. Dynamic Programming (Top-Down) - Memoization

재귀적으로 문제를 쪼개되, 중복 계산을 방지하기 위해 메모이제이션을 사용합니다.

  1. 점화식:
    • dp(x, y) = dp(x-1, y) + dp(x, y-1)
  2. Base Case:
    • 시작점 (0, 0)에서 가능한 경로는 1입니다.
  3. Memoization:
    • 이전에 계산된 값을 저장해 중복 계산을 방지합니다.
  4. 시간 복잡도는 O(m⋅n)O(m \cdot n)입니다.

4. Dynamic Programming (Bottom-Up)

Bottom-Up 방식은 반복문을 통해 작은 문제부터 큰 문제로 확장합니다.

  1. 점화식:
    • memo[r][c] = memo[r-1][c] + memo[r][c-1]
  2. Base Case:
    • 첫 번째 행과 첫 번째 열의 경로는 모두 1입니다.
  3. 시간 복잡도는 O(m⋅n)O(m \cdot n)이며, 배열을 사용하여 경로를 저장합니다.

이제 코드를 구현해보겠습니다.

Step4. 코드 구현

조합

class Solution(object):
# # 1. Combinations
    def uniquePaths(self, m, n): # O(m + n)
        # https://leetcode.com/problems/unique-paths/submissions/1458969323
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        from math import factorial
        def comb(x,y): # xCr = x! / (x-y)! * y!
            return factorial(x) // (factorial(x - y) * factorial(y))
        return comb(m + n - 2, m - 1)

코드 설명:

  • 총 이동 횟수는 m+n−2m + n - 2이며, 그중에서 아래로 이동할 횟수는 m−1m - 1입니다.
  • comb 함수는 조합을 계산합니다: Cm+n−2m−1=(m+n−2)!(m−1)!⋅(n−1)!C_{m+n-2}^{m-1} = \frac{(m+n-2)!}{(m-1)! \cdot (n-1)!}
  • factorial을 사용해 조합 값을 계산하고 반환합니다.

시간 복잡도: O(m+n)O(m + n)

결과: https://leetcode.com/problems/unique-paths/submissions/1458969323

완전 탐색

class Solution(object):
    
    # # 2. 완전 탐색
    def uniquePaths(self, m, n): # O(2^(m+n))
        # https://leetcode.com/problems/unique-paths/submissions/1458968943
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        
        def move(x, y):
            if x == 0 and y == 0:
                return 1
            
            paths = 0
            
            if x - 1 >= 0:
                paths += move(x - 1, y)
            if y - 1 >= 0:
                paths += move(x, y - 1)
            
            return paths
        
        return move(m - 1, n - 1)class Solution(object):

코드 설명:

  • 재귀적으로 (x, y)에서 (0, 0)으로 이동할 모든 경로를 탐색합니다.
  • 경로가 격자를 벗어나지 않도록 조건을 설정하고, 도달할 때마다 1을 반환합니다.
  • 두 방향 (아래/오른쪽)으로 이동하며 모든 경로를 계산합니다.

시간 복잡도: O(2m+n)O(2^{m + n})

결과: https://leetcode.com/problems/unique-paths/submissions/1458968943

DP (Top-Down hash table)

class Solution(object):
# 3. Top-Down dp dict
    def uniquePaths(self, m, n): # O(m * n)
        # https://leetcode.com/problems/unique-paths/submissions/1458969837
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        memo = {}
        
        def dp(x, y):
            if x == 0 and y == 0:
                memo[(x,y)] = 1
                return memo[(x,y)]
            
            if (x,y) in memo:
                return memo[(x,y)]
            
            paths = 0
            
            if x - 1 >= 0:
                paths += dp(x - 1, y)
            if y - 1 >= 0:
                paths += dp(x, y - 1)
            memo[(x,y)] = paths
            
            return memo[(x,y)]
        
        return dp(m - 1, n - 1)

코드 설명:

  • memo 딕셔너리를 사용해 중복 계산을 방지합니다.
  • 재귀적으로 (x, y)에서 (0, 0)까지의 경로를 계산합니다.
  • 이전에 계산한 경로 수는 memo에 저장하고, 필요 시 바로 반환합니다.

시간 복잡도: O(m∗n)O(m * n)

결과: https://leetcode.com/problems/unique-paths/submissions/1458969837

DP (Top-Down list)

class Solution(object):
# 4. Top-Down dp list
    def uniquePaths(self, m, n): # O(m*n)
        # https://leetcode.com/problems/unique-paths/submissions/1458967118
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        memo = [[-1] * n for _ in range(m)]
        
        def dp(x, y):
            if x == 0 and y == 0:
                memo[x][y] = 1
                return memo[x][y]
            
            if memo[x][y] != -1:
                return memo[x][y]
            
            paths = 0
            if x - 1 >= 0:
                paths += dp(x - 1, y)
            if y - 1 >= 0:
                paths += dp(x, y - 1)
            memo[x][y] = paths
            return memo[x][y]
        
        return dp(m - 1, n - 1)

코드 설명:

  • 2D 배열 memo를 사용해 중복 계산을 방지합니다.
  • 재귀적으로 (x, y)에서 (0, 0)까지의 경로를 계산하고, 결과를 memo에 저장합니다.

시간 복잡도: O(m∗n)O(m * n)

결과: https://leetcode.com/problems/unique-paths/submissions/1458967118

DP (Bottom-Up)

class Solution(object):
# # 5. Bottom-Up dp
    def uniquePaths(self, m, n): # O(m*n)
        # https://leetcode.com/problems/unique-paths/submissions/1458968642
        """ 
        :type m: int
        :type n: int
        :rtype: int
        """
        memo = [[-1] * n for _ in range(m)]
        
        for r in range(m):
            memo[r][0] = 1
        for c in range(n):
            memo[0][c] = 1
            
        for r in range(1,m):
            for c in range(1,n):
                memo[r][c] = memo[r - 1][c] + memo[r][c - 1]
                
        return memo[m - 1][n - 1]

코드 설명:

  • memo 배열을 초기화하며, 첫 행과 첫 열은 항상 1로 설정합니다.
  • 각 셀 (r, c)의 값은 위쪽 셀과 왼쪽 셀의 값을 더한 결과입니다.
  • 마지막 셀 (m-1, n-1)의 값을 반환합니다.

시간 복잡도: O(m∗n)O(m * n)

결과: https://leetcode.com/problems/unique-paths/submissions/1458968642

4. 마무리

이 문제는 Dynamic Programming, 조합, 그리고 완전 탐색을 모두 활용할 수 있는 문제입니다.

  • 조합은 매우 효율적이며, 빠르게 결과를 반환합니다.
  • Dynamic Programming은 문제를 쪼개어 해결하며 효율성과 직관성을 모두 갖췄습니다.
  • 완전 탐색은 비효율적이지만, 문제의 구조를 파악하기에 좋습니다.

이번 문제를 통해 다양한 접근 방식을 비교하며 효율성을 배울 수 있었습니다. Dynamic Programming 문제는 점진적으로 푸는 연습이 필요하며, 각 접근 방식의 장단점을 이해하는 것이 중요합니다! 😊

전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다!

포기하지 않는 나!!

profile
말하는 감자
할 수 있다
이전 포스트

[LeetCode] 746. Min Cost Climbing Stairs

다음 포스트

[LeetCode] 743. Network Delay Time

0개의 댓글

관련 채용 정보