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

안녕하세요 ㅎㅎ

코드 잘 짜셨네요. ㅎㅎ 문제는 없어보이고 저와 로직도 동일합니다.

저런 조합함수는 재귀함수이며 재귀함수는 반복문보다는 보통 시간이 많이 걸립니다.

이 때문에 시간초과가 발생한 것 같습니다.

따라서, 이런식으로 반복문으로 바꿔보시겠어요?

    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (N[i] + N[j] == m) {
                cnt++;
            }
        }
    }

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

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

감사합니다.

강사 큰돌 올림.

ios_base부분 오타있는 것을 확인했습니다. 하지만 그것을 바꾼뒤에도 시간초과 문제는 변함이 없네요.

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

재귀 함수를 이용한 문제 해결에서는 일반적으로 재귀 호출로 인한 깊어진 함수 호출 스택과 메모리 사용 때문에 시간초과가 발생할 수 있습니다. 특히, 조합이나 순열과 같은 연산에서는 재귀보다 반복문을 사용한 방법이 더 효율적일 수 있습니다.

관련하여 유사한 질문들이 있었으며, 여기서 시간초과 문제를 해결하는데 도움이 될 수 있는 몇 가지 팁을 소개해드리겠습니다:

1. 반복문 사용: 재귀보다 반복문이 더 빠른 경우가 많습니다. 작은 크기의 nCr 연산 (r <= 3)에서는 중첩 for문을 사용하는 것이 유리할 수 있습니다.

2. 시간 복잡도 고려: 특히 nCr 같은 경우 n의 크기가 클 때, 불필요한 계산을 줄이는 것이 중요합니다. Memoization이나 DP를 통해 중복 연산을 줄일 수 있는지 확인해보세요.

3. 최적화 기술: 가능한 경우 중간 계산 결과를 저장하고, 불필요한 계산을 피하기 위해 기존 값을 재사용하십시오.

비슷한 사례들을 통해 유용한 논의를 확인해 볼 수 있습니다. 아래 링크를 참조하세요:

• 1-L 시간초과 질문: 여기서는 재귀적으로 구현한 nCr 함수가 시간초과 문제를 겪고 있어, 반복문을 통한 해결 방안을 제안해 드리고 있습니다.

• 3-O 사다리 조작: 재귀보다 효율적인 방법을 찾기 위한 논의가 진행되었습니다. 최적화 전후의 코드를 비교해 보시면 도움이 될 수 있습니다.

제가 추가로 도움을 드리기 위해 지식공유자님의 기존 답변을 바탕으로 문제 해결 방법을 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.