재귀를 사용한 완전탐색도 특정 경우엔 괜찮은 방법이지만, 이 경우엔 비효율적입니다.
이전에 불렀던 것에 대한 캐쉬가 없기때문에, 같은 num에 대한 입력을 매우 여러번 수행하게 됩니다.
거기에 일반적인 완전탐색에 if문으로 비교를 위해서도 또 재귀함수를 부르면서 시간이 엄청나게 늘어났습니다.
물론 횟수가 다른 num에 대해 보시려고 하신거겠지만,
생각을 바꿔보면 특정 'k'까지 최적의 길을 이미 알고있다면 k를 부를 때마다 k까지의 최적의 길을 계속해서 찾을 이유는 없는겁니다.
우선 메모리와 시간의 트레이드오프를 한번 생각해보시고, ( 이 문제는 '메모리를 사용해서 캐슁하면' O(N)으로 가능합니다. )
그다음 잘 모르시겠으면 DP(Dynamic Programming)를 키워드로 검색하셔서 개념을 찾아보시면 다른길이 보이실것같습니다!
hyobinn94 4년 전
안녕하세요. 아직 코딩연습이 많이 부족한 사람입니다.
그래서 제가 쓴 코드가 시간이나 공간을 얼마나 잡아먹는지 한눈에 감이 잘 오지 않습니다.
이 문제를 풀 때 재귀함수말고 다른 방법이 떠오르지않아서 결국 입력숫자의 조건을 나눠서 재귀함수를 호출하는 방식으로 작성했습니다.
결과적으로 시간초과가 뜨네요. 이런식으로 재귀함수를 사용하면 최적화에 굉장히 문제가 많은 코드가 되나요?