Jump Game

yssgood·2022년 5월 3일
0

LeetCode

목록 보기
28/47
post-thumbnail

리트코드에서 상당히 유명한 시리즈인 Jump Game 문제를 풀었다. Jump Game 같은 경우에는 DP를 활용한 시리즈가 굉장히 많은데 이 문제 또한 DP를 활용한 정말 유명한 문제중 하나이다. DP에서 사용되는 Memorization 기법이란 반복되는 계산을 방지하고자 Table을 활용해서 해당 값을 저장하는것을 뜻한다. 그리고 이 문제에서 나오는 Jump는 벡터안에 있는 숫자만큼 점프가 가능하다고 봤을때, 가장 마지막 index에 닿을수 있는지 없는지를 물어보는거다.

내가 이 문제를 처음 풀었을때 기억나는 부분중 하나가 저 check 부분을 안쓰고 그냥 기억나는데로 for 룹안에다가
ret = dfs(nums,index+i) 를 썼다가 아무리 해도 맞다 생각했는데도 false가 리턴되던때가 있었다. 가만히 생각해보니 이 코드 자체는 마지막 index에 도달하는 순간 더 이상 계산할 필요도 없었던 코드였다. 그런데도 나는 for 룹을 끝까지 돌렸고 for 룹에서 0이 한번이라도 리턴된 순간 결국 ret는 true 가 됐었다 해도 결국에는 false 로 남게된것이다.

그런 이유때문에 여기서는 check 라는 변수하나로 true 가 나오게 된순간 ret를 리턴해주는게 좋았고 ret = check 라고 쓰는것도 중요했던거 같다. 그렇게 되면 재귀함수가 돌아오는 과정에서 전부다 1로 리턴되기 때문에 정답은 true 가 될수밖에 없었던 것이다.

배운점:
1. ret 함수를 끝내는 타이밍도 알아야한다
2. ret함수에 어떤 값을 지정하는지도 알면은 좋은거같다.

profile
성장하는 사람

0개의 댓글