[알고리즘][다이나믹(동적 계획법) 기초] 계단 오르기 (백준)

다이나믹(동적 계획법) 알고리즘 기초 문제 : 계단 오르기 (백준)

이번 문제를 풀면서 느낀 점은

다이나믹(동적 계획법) 알고리즘을 풀 때에는

답을 저장하는 DP배열이 꼭 필요하다는 것이다.

답을 담을 변수를 하나만 선언해서 이리저리 굴려보다가 결국 제시간에 풀지 못했다.

동적 계획법은

첫 째, 그 전에 구해놓은 답을 사용하여 현재의 답을 찾는 것!

둘 째, 구한 답을 저장할 DP배열을 사용할 것!

셋 째, 문제를 잘 읽고 규칙을 찾아 내는 것!

지금까지 다이나믹(동적 계획법) 알고리즘을 풀면서 중요하다고 느낀 부분이다.

익숙해질 때까지 반복적으로 문제를 풀어보는 것이 중요할 듯 하다.

계단 오르기 (백준)

문제를 처음 딱 접했는 때에는

DFS 알고리즘으로도 풀 수 있겠다 생각했지만,

동적 계획법으로 푸니 정말 간단하게 답이 나왔다.

짧은 코드로 많은 것을 해내는 코드는 그 만큼 어렵다고 했다.

위의 코드는 매우 간단해보이지만, 이 문제를 DFS 알고리즘으로

푼다고 생각했을 때는, 이렇게 간단한 코드로 끝나지 않을 것이다.

(물론 DFS도 그리 긴 코드는 나오지 않을 것이다.)