[LC150] DP를 활용한 Jump Game 1 & 2

 

다이나믹 프로그래밍 진짜 열심히 공부한것 같은데... 착각인가 왜 자꾸 못 풀지.. :(

 

DP를 푸는 방법으로는 하향식과 상향식 방법이 있는데 나는 주로 하향식 방법으로 재귀와 메모이제이션을 사용해서 풀었다.

 

 

Jump Game 문제는

그리디로도 풀 수 있지만 DP top-down으로 풀었다. 이때도 백트래킹이랑 DP랑 헷갈려서 헤매다 결국 풀긴했다. 

 

 

Jump Game 

 

내 코드	정답 코드
실행 순서	실행 순서

 

 

인풋값이 nums = [1, 2, 1, 1, 1] 일때 내가 작성한 코드랑 정답 코드를 비교해보면 인풋값이 wrong answer가 나온다. 

 

실행순서는 똑같은데 dp(0) -> dp(1) -> dp(3) 으로 가는 경로가 제일 짧지만 이걸 반영을 못 해주는 것 같다. 두 코드의 차이는 정답코드는 step을 내부적으로 다루고 (메모에 반영 X), 내 코드는 step을 인자값으로 계속 넘겨주고 있다. 실행 순서대로 노트에 값이 어떻게 넘어가는지 그려보면 내 코드는 더 짧은 경로 전에 이미 memo값을 업데이트 해줬기 때문에 dp(4, 3)을 호출 할때 기존에 저장된 값을 리턴해서 최소값을 업데이트 하지 못한다. 

 

Memoization을 할 때는 상태값이 전부 들어가도록 작성해야 된다. 예를들어 내 코드의 경우 인덱스랑 스텝값을 넘겨주는데 dp(4, 4)일 때랑 dp(4, 3)일때 다르게 저장되어야 하기 때문에 일차원 배열이 아니라 2차원 배열로 memo[인덱스][스텝] 이렇게 저장해주면 memo는 index에 step번 만에 도달한 상태를 캐시하고 있게 된다. 하지만 step을 굳이 memo에 저장할 필요가 없는게 step은 누적값이고 결과에 영향을 주는 요소가 아니기 때문에 배열에는 index값만 가지고 step을 결과로만 사용하면 되기 때문에 정답코드 처럼 작성해야 한다. 근데 저렇게 작성하긴 어려워보이는데 만약에 nums = [2, 3, 0, 1, 4] 가 들어왔을 때 처럼 index 2에서 경로가 끊어지는 경우(dead end) if로 next != Integer.MAX_VALUE 값을 체크해 주지 않으면 overflow가 발생한다. 

 

 

그리고 min = Math.min(min, 1+ next) 여기서 스텝 값을 하나 더 해줌으로써 해당 인덱스에서는 for문을 다 검색한 뒤 최솟값을 저장할 수 있다. 

 

그럼 내가 익숙하지 않은 bottom-up 방법을 보면

 

 

먼저 시작 위치 값을 dp[0] = 0으로 세팅해주고 인덱스 길이만큼 반복문을 돌면서 dp[i + j] 값을 갱신해준다. 그리고 반복문이 다 끝나면 dp[n - 1] 가장 마지막 위치를 리턴한다. 지금까지 bottom-up 방법이 더 어렵다고 생각했는데 괜찮은 것 같기도 하고... 다음 dp 문제는 이 방법으로도 풀어봐야겠다.