hyobinn94   4년 전

안녕하세요. 아직 코딩연습이 많이 부족한 사람입니다.

그래서 제가 쓴 코드가 시간이나 공간을 얼마나 잡아먹는지 한눈에 감이 잘 오지 않습니다.

이 문제를 풀 때 재귀함수말고 다른 방법이 떠오르지않아서 결국 입력숫자의 조건을 나눠서 재귀함수를 호출하는 방식으로 작성했습니다.

결과적으로 시간초과가 뜨네요. 이런식으로 재귀함수를 사용하면 최적화에 굉장히 문제가 많은 코드가 되나요?

nahwasa   4년 전

재귀를 사용한 완전탐색도 특정 경우엔 괜찮은 방법이지만, 이 경우엔 비효율적입니다.

이전에 불렀던 것에 대한 캐쉬가 없기때문에, 같은 num에 대한 입력을 매우 여러번 수행하게 됩니다.

거기에 일반적인 완전탐색에 if문으로 비교를 위해서도 또 재귀함수를 부르면서 시간이 엄청나게 늘어났습니다.

물론 횟수가 다른 num에 대해 보시려고 하신거겠지만,

생각을 바꿔보면 특정 'k'까지 최적의 길을 이미 알고있다면 k를 부를 때마다 k까지의 최적의 길을 계속해서 찾을 이유는 없는겁니다.

우선 메모리와 시간의 트레이드오프를 한번 생각해보시고, ( 이 문제는 '메모리를 사용해서 캐슁하면' O(N)으로 가능합니다. )

그다음 잘 모르시겠으면  DP(Dynamic Programming)를 키워드로 검색하셔서 개념을 찾아보시면 다른길이 보이실것같습니다!


hyobinn94   4년 전

아 이전에 이미 계산이 끝났던 최적의 값들을 다시 쓰지않고 다시 처음부터 전부 계산을 해서 낭비되는 시간이 매우 많아졌던거였군요 ㅠㅠ.. 알려주신 키워드로 값을 재사용하는 방법부터 자세히 알아보겠습니다. 효율있는 알고리즘을 짜는 방법에 대해 많이 생각하게되는 계기가 되었네요 ㅠㅠ 도와주셔서 정말 감사합니다! 

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