[ leetcode 문제풀이 ] Unique Paths

https://leetcode.com/problems/unique-paths/

Unique Paths - LeetCode

(Unique Paths 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Unique Paths 문제 설명 >

 

Unique Paths 문제는 다음과 같다.

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 * 10^9.

 

로봇은 처음에 왼쪽 상단 모서리(grid[0][0])에 위치하여 오른쪽 하단 모서리(grid[m - 1][n - 1])로 이동을 시도한다. 로봇은 아래 또는 오른쪽으로만 이동할 수 있다고 할 때 주어진 m, n에 대해 도달 가능한 경로의 수를 리턴하여라.

다음 두 가지 출력 예시가 주어졌다.

 

주어진 제한 조건은 1 ≤ m, n ≤ 100 이다.

 

 

 

---

< Unique Paths 문제 접근(1) >

 

메모이제이션을 위해 cache[m][n]이라는 배열을 생각하자. cache[i][j]를 i행 j열까지 도달할 수 있는 unique path의 수라고 하면 cache[i][j] = cache[i-1][j] + cache[i][j-1] 관계식이 성립힌다. ((i-1,j)에서 아래로 내려오는 경우 + (i, j-1)에서 오른쪽으로 가는 경우) 이 관계식을 이용해 구현한 알고리즘은 아래와 같다. (Cpp 사용)

 

int uniquePaths(int m, int n) {
    if(m < n)
        return uniquePaths(n, m); // 메모리 사용을 최소화 하기 위함
    
    vector<vector<int>> cache(2,vector<int>(n));
    for(int i=0;i<n;i++)   // 1행과 1열의 값은 1로 정해져 있으므로 먼저 초기화
        cache[0][i] = 1;
    cache[1][0] = 1;
    
    for(int i=1;i<m;i++)  // 최초 초기화한 1행, 1열을 제외한 나머지 부분 할당
        for(int j=1;j<n;j++) 
            cache[i&1][j] = cache[i&1][j-1] + cache[(i-1)&1][j];
     
    return cache[(m-1)&1][n-1];
}

 

위 코드의 경우 사용하는 메모리의 크기를 최소화하기 위해 cache 배열을 2 × min(n,m) 크기로 구성하였다. 

Complexity analysis를 진행하면 time complexity는 O(nm)이고, memory complexity는 O(max(n,m))이다.

 

 

 

---

< Unique Paths 문제 접근(2) >

 

 

이 문제는 또한 조합론에서 대표적으로 다루는 문제 중 하나이다. 우측 하단 위치에 도달할 수 있는 경로를 선택하는 것은 결국 아래로 내려가는 방법(m-1회)과 오른쪽으로 가는 방법(n-1회)을 어떤 순서로 나열할 지를 정하는 것과 동일하다. 따라서 uniquePaths(m, n)의 답은 m+n-2 C n-1로 정해져있다. 이를 코드로 구현하면 아래와 같다. (Cpp 사용)

 

int uniquePaths(int m, int n) {
    // ans: m+n-2 C n-1
    if(m < n)
        return uniquePaths(n, m);
        
    long ans = 1;
    for(int i=1;i<n;i++)
        ans = ans* (m-1+i) / i;
    
    return (int)ans;
}

최대한 연산의 횟수를 줄어주기 위해 m과 n 중 작은 값을 반복문의 반복 횟수로 지정해주었다. 

Complexity analysis를 진행하면 time complexity는 O(max(n,m))이고, memory complexity는 O(1)이다.

 

 

 

---

< Unique Paths 두 접근 방식의 비교 >

 

두 접근 방식 중 어느 것이 시간적으로 유리한 방법일까?

 

time complexity만 보자면 combination을 직접적으로 계산한 두 번째가 더 좋은 방법일 것이다. 그러나, 곱셈/나눗셈 연산은 시간적으로 상당히 손해를 보는 연산이라고 알고 있기에 단순히 time complexity만으로는 확인하기 어렵다. leetcode test case에 대해서는 두 경우 모두 0 ms의 runtime을 나타내었기에 결론을 짓기엔 어려우나 느린 곱셈 연산을 가진 환경에서는 첫 번째 방법을, 빠른 곱셈 연산을 가진 환경에서는 두 번째 방법을 사용하는 것이 좋아보인다.

 

또한 주목할만한 한 가지 실험 결과로 두 번째 방법에 대해 m과 n의 크기를 비교하는 조건문을 지우고 코드를 실행한 결과 5 ms의 runtime을 나타냈다. 크기 비교 조건문을 통해서 m과 n중 더 작은 숫자만큼 곱셈/나눗셈 연산을 진행하도록 하였기 때문에 시간 단축에 도움이 된 것으로 보인다. 비교 조건문이 runtime에 유의미한 영향을 주므로 유사한 문제를 풀 경우 필수적으로 사용해야하는 테크닉이라고 생각된다.