meme0724   1년 전

동적계획법 연습할려고 여기 위키에 적혀있는 예제를 풀었습니다.

위키에 적힌 방법대로 참고해서 나름 맞는 방법으로 풀었다고 생각하는데

시간 초과라고 뜨네요

다른 방법을 써야 되는 건가요?

직접 테스트 해본 것은 아니지만, 위에 부분에서 n-1,n-2 부분에서 재귀로 계속 호출되면 중복되는 부분이 생겨 시간복잡도가 지수로 올라갈 듯 합니다.

동적계획법으로 O(N)에 풀 수 있습니다

wxogus25   1년 전

윗분께서 말씀하신 것처럼 계속 호출되는 부분이 생겨서 그런 것 같습니다. stair(3)을 호출해도 결국 stair(0)과 stair(1)이 호출되고

stair(4)을 호출해도 stair(0)과 stair(1)이 호출됩니다. 이렇게 중복되는 부분이 생기면서 시간이 오래 걸리는 것 같은데요 사실 이런방식은

동적계획법이라기 보다는 재귀호출에 가까워 보입니다. 이미 구한적이 있는 값을 함수를 실행 할 때마다 다시 구하고 있으니까요

이 문제점을 해결하려면 배열을 만들면 됩니다. n의 크기를 가진 배열을 만들고 n[i]에 stair(i)의 값을 저장한다면 이미 구한 값을 다시 구하는

수고를 덜게 되서 실행시간이 더욱 빨라지게 됩니다.

댓글을 작성하려면 로그인해야 합니다.