[Grind75-LeetCode] Unique Paths JAVA

반응형

728x90

[Grind75-LeetCode] Unique Paths - Medium

---

접근

• dp
• 조합

---

풀이

m x n 좌표 평면 위에서 왼쪽 상단 (0,0)에서 출발해 오른쪽 하단 (m-1, n-1)까지 갈 수 있는 고유의 경로를 구하는 문제이다. 고유 경로는 겹치지 않는 모든 이동 경로를 말하며 이동은 오른쪽, 아래 방향으로만 가능하다. dfs를 통해서도 찾을 순 있지만 중복 계산이 많이 발생하고 모든 경로 탐색으로 최적화를 위해 메모이제이션 배열을 사용하게 될 텐데 그럼 그냥 처음부터 dp를 통해 푸는 것이 효율적이다. 

    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }

        for(int j = 0; j < n; j++){
            dp[0][j] = 1;
        }

dp 배열을 생성하고 각 경로의 첫 번째 열을 따라가는 경우를 모두 1로 초기화시켜준다. 오직 아래로만 내려가던가 오른쪽으로만 가는 경로는 하나이기 때문이다.

	for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];

그리고 반복을 통해 해당 좌표 까지의 방문을 위한 경로의 수를 더해준다. 어떤 특정 위치로 가기 위해선 오른쪽으로 이동해 가는 법과 아래로 이동해 가는 두 가지 경로가 존재하기 때문에 각 경로의 경우의 수를 더해주는 것이다. 그리고 만들어진 배열을 통해 최종 목적지의 경우의 수를 반환해 준다. 

---

수학의 조합을 통해 푸는 방법으로 고등학교 수학 시간에 조합 공식으로 nCr을 떠올리면 된다. n개의 경우 중에 r 개를 선택하는 방법으로 우린 전체 이동 횟수에서 아래로 가는 횟수를 고른다고 보면 된다. 

 

전체 이동 횟수는 m x n 범위 이므로 (m - 1) + (n - 1) = m + n - 2가 된다. 그리고 오른쪽으로 가는 경우를 고르거나 아래로 가는 경우 둘 중 하나를 고르면 되는데 아래로 가는 경우 횟수는 좌표의 끝인 m - 1로 (m + n - 2)C(m-1)을 하면 된다. 조합의 경우 nCr과 nC(n-r)의 값이 같은데 약분을 통해 겹치는 부분이 사라지기 때문이다. 공식 그대로 옮겨 코드를 만들어봤기 때문에 약분 과정을 건너뛰어 계산하기 편하게 작은 값을 골라줬다. 그러나 이 방법은 오버플로우가 나는 방법이었다. 

    public int uniquePaths(int m, int n) {
        int a = m + n - 2;
        int temp1 = Math.min(m - 1, a - (m - 1));
        int temp2 = Math.min(n - 1, a - (n - 1));
        int b = Math.min(temp1, temp2);

        long resA = 1;
        long resB = 1;

        for (int i = a, j = b; j > 0; j--, i--) {	//오버플로우 발생
            resA *= i;
            resB *= j;
        }

        return (int) (resA / resB);
    }

아무리 연산 수를 줄이고 long 타입을 사용해도 나눗셈을 마지막에 하게 될 경우 오버플로우가 발생한다. 중간중간 계속 나눗셈을 같이 하며 진행해주어야 한다. 

    public int uniquePaths(int m, int n) {
        int a = m + n - 2;
        int b = m - 1;

        long result = 1;

        for (int i = 1; i <= b; i++) {
            result = result * (a - (b - i)) / i;
        }

        return (int) result;
    }

나눗셈을 하며 진행하는 코드이다. 계속 값을 나눠 오버플로우가 일어나지 않게 해 준다. 기존 식을 변형해 수학적 방법으로 변형한 것으로 이 변형은 gpt가 복잡한 풀이로 설명해 주어 사실 이해가 가진 않았다. 팩토리얼을 분해해 대입하고 소거하고 하여 결과적으로 아래의 식이 나온다는데 봐도 모르겠다. 

변형식

  변형된 식을 통해 b 팩토리얼을 분모로 계속 나누고 있는 형태로 변경하여 계산마다 수를 줄일 수 있게 되는 것이라고 한다. 

---

전체 코드

dp

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }

        for(int j = 0; j < n; j++){
            dp[0][j] = 1;
        }

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }
}

 

조합

class Solution {
    public int uniquePaths(int m, int n) {
        int a = m + n - 2;
        int b = m - 1;

        long result = 1;

        for (int i = 1; i <= b; i++) {
            result = result * (a - (b - i)) / i;
        }

        return (int) result;
    }
}