인프런 커뮤니티 질문&답변

안녕하세요 대식님 ㅎㅎ

    for(int i = idx + 1; i<n; i++){
        res = res + vec[i];
        dfs(i,res,lv+1);

이렇게 재귀함수를 작성하면 시간복잡도가 어느정도일까요?

n 곱하기 n - 1 ... 이렇게 되지 않을까요? n의 최대범위는 15,000 이기 때문에 시간복잡도가 너무 크게 됩니다. 이 때문에 시간초과가 나는 것 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 대식님.

재귀 알고리즘을 사용한 풀이에서 시간 초과가 발생하는 주요 원인 중 일부와 해결 방법에 대한 조언을 드리겠습니다.

1. 중복 탐색: 재귀 호출에서 동일한 상태를 여러 번 탐색하게 되면 시간 초과가 발생할 수 있습니다. 이를 해결하기 위해 메모이제이션(Memoization)을 도입하여 이미 계산된 결과를 저장하고 재사용하는 것이 좋습니다.

2. 베이스 케이스 미흡: 베이스 케이스 조건이 명확하지 않으면 불필요한 깊은 탐색이 일어날 수 있습니다. 따라서 확실한 종료 조건을 설정하는 것이 중요합니다.

3. 연산 복잡도: 각 재귀 호출 내의 연산 비용이 크다면 이를 줄이는 방법도 고려해야 합니다. 불필요한 변수 선언이나 복잡한 연산을 줄여야 합니다.

기존에 비슷한 문제와 관련하여 시간 초과가 발생했던 사례에 대해선 다음과 같은 답변이 있었습니다. 이 질문에서 다른 수강생분들도 비슷한 문제를 해결하였으니 참고해 보시길 추천드립니다.

• 1-O 다른 방법으로 풀었는데, 시간초과가 납니다
  해당 질문에서는 Long long 정수로 변환하면서 발생하는 시간 초과 문제에 대해 해결 방법이 제시되어 있습니다.

• 3-E 재귀 시간초과
  백트래킹과 BFS를 비교하며 시간 초과 문제를 해결하기 위한 조언이 있습니다.

해당 링크들을 통해 시간 초과 해결에 필요한 추가 힌트를 얻길 바라겠습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.