[leetcode/JS] 70. Climbing Stairs / Javascript

 

문제링크 

https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

 

 

 

 

기억하면 좋을 것 

이 문제는 recursive로 풀면 시간 초과로 통과하지 못한다. 

memoization 을 이용해 빈 배열을 생성하고 , 거기에 결과값을 저장 해 나가며 최종 결과를 반환해야한다.

DP는 하향식(Top-Down 방식), 상향식(Bottom-UP 방식) 두 가지 방식으로 풀 수 있다. 

memoization 을 이용해 푸는 것이 일반적이다. 

 

DP가 사용 될 수 있는 이용 조건은 

1. 최적 구분 구조 : 큰 부분을 작은 부분으로 나눌 수 있는가?

2. 중복되는 부분 문제들로 이루어졌는가?: 동일한 작은 문제를 반복적으로 해결할 수 있는가? 

이다.

 

유튜브의 나동빈강의를 듣고 필기하며 정리 해 봤다. 최대한 다른 방법들을 우선적으로 생각하고 DP 를 적용 할 생각은 나중에 하는 것이 좋다. 강의 뒷 부분 예제 문제부터는 너무 어려워서 이해하지 못했다... ^^

기본을 다진 후 예제 문제도 도전 해 봐야겠다. 

 

 

 

소감

이 문제는 DP로 푸는 문제이다. 난이도가 easy 이면서 정답률이 높음에도

며칠을 끙끙거리다가 힌트를 보고 풀 수 있게 되었다. 

그런데 허무하게도.... 이 문제는 그냥 피보나치 수열과 똑같은 문제였다 .............

그냥 처음부터 손으로 써봤으면 될 문제 였을 것 같은데 .. 

나는 md 파일로 문제를 어떻게 풀어나갈지 정리 하는 것 보다 그냥 손으로 써서 생각 정리를 하는 것이 잘 맞는 것 같다

 

100% 내 생각만으로 그리고 내 힘으로 알고리즘을 풀어야한다는 강박 때문에 문제를 보면 한숨만 나오고 

알고리즘이 싫어졌었는데 

한 문제에 대해 30분 생각 해 봐도 모르겠으면 그 문제는 그 이상 시간을 들여 생각해도 못 푸는 문제라는 조언을 듣고 

아차 싶었다 앞으로는 30분 타이머를 지정 해 놓고 손으로 써서 생각 정리를 하고 모르겠으면 답안 혹은 힌트를 보고 

내 것으로 만들어야겠다. 

산수 문제도 못 푸는데 미적분을 풀려고 백날 천날 들여다보기만 한다고 풀 수 있는게 아니니 말이다.

요즘은 좀 내 수준을 인정하고 진정으로 받아들이게 된 것 같다.

 

해결 코드

 

Submission Detail