문제

양수로 이루어진 m x n 그리드를 인자로 드립니다. 상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때, 가장 작은 합을 찾아서 return 해주세요.


한 지점에서 우측이나 아래로만 이동할 수 있습니다.

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

Output: 7

설명: 1→3→1→1→1 의 합이 제일 작음

• Output 출력 데이터 타입: Number

문제 접근 / 정리 / 아이디어들

1. 입력으로 2차원 배열을 받는다. (MxN 배열)
2. 첫번째 low와 column을 이미 지나간 자취라 생각하고 각 요소에 그 값들을 더해준다.
3. 나머지 low와 column을 순차적으로 반복문을 통해 접근하여, 해당 요소의 위, 왼쪽 값 중 작은 값을 더해준다.
4. 최종 적으로 맨 오른쪽 맨 아랫값이 반환할 값이 된다. (Number type)

풀이 코드

위의 문제 접근 방법을 통한 코드이다. 주석과 console.log 를 통해 각 반복문이 어떤 과정을 거치는지 확인할 수 있다.

const minPathSum = grid => { 
    // 첫번째 row, column은 각 인자의 line을 이미 지나왔다고 가정후 더해 놓는다.
    for (let i = 1; i < grid.length; i++) { // 첫번째 column
        grid[i][0] += grid[i-1][0]; 
        console.log("첫번째 for")
        console.log(grid)     
    }
    for (let i = 1; i < grid[0].length; i++) { // 첫번째 low
         grid[0][i] += grid[0][i-1];
         console.log("두번쨰 for")
         console.log(grid)
    }    
    // 위 반복문 후에 문제의 Input 예시는 다음과 같이 변경된다.
    // [1,4,5]
    // [2,7,6]
    // [6,8,7]

    for (let i = 1; i < grid.length; i++) { // column level
        for (let j = 1; j < grid[0].length; j++) { // low level
            grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
            console.log("세번째 for")
            console.log(grid)
        }
    } 
    //대상 인자의 위 혹은 왼쪽 값중 작은 값을 더해줌

    return grid[grid.length-1][grid[0].length-1];
};

느낀 점

지금까지의 Code Kata 문제 중에서 가장 어려웠다고 해도 과언이 아닌 문제였다. 아마 대부분의 사람들이 이 문제를 보면, 접근 방식을 Dynamic programing (모든 경우의 수 중 가장 최적의 값을 도출하는 과정) 관점으로 보지 않을까 생각이 든다. 이 문제에서는 첫번째 row와 column을 미리 거쳤다고 가정만 해주면, 나머지 값들은 대상의 위, 왼쪽 값들만 비교해서 더해주면 결국 배열의 끝 값이 최종적인 최소 경로로 저장이 되기 때문에 논리적 접근을 정확히 한다면, 수월하게 풀 수 있을 거라고 생각했다. (결국 그 논리적 접근이 알고리즘에서 제일 어려운 과정이긴 하지만..)

✌️ All tests have passed 2/2