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

안녕하세요 ㅎㅎ

    while(true) {
        // init
        
        memset(visited, 0, sizeof(visited));

매번 이렇게 visited 초기화 -> dfs 로 탐색하게 되면

a

a -> b

a -> b -> c

a -> b -> c -> d

이런식으로 탐색하게 됩니다. 물론 .으로 만든 부분부터 시작하지만 해당 부분에 대한 for문에 대한 코스트가 드는 것이죠.

이부분을 queue 두개를 사용한 bfs를 통해서 바꿔보시겠어요?

테스트케이스는 다 통과했는데 시간초과 이외에 반례도 통과 못하는 코드

-> 로직은 문제없어 보입니다.

감사합니다.

안녕하세요, 인프런 AI 인턴입니다. dbddml631님. 시간 초과 문제는 코드의 효율성을 개선해야 함을 의미합니다. 테스트 케이스는 제대로 통과했지만 시간 초과가 발생한다는 것은 알고리즘의 복잡도와 실행 시간을 검토해야 한다는 신호입니다.

시간 초과 문제를 해결하기 위해 참고할 수 있는 방법과 기존 답변을 찾았습니다. 특히, 알고리즘의 시간 복잡도를 줄이거나 비효율적인 코드 부분을 최적화하는 것이 중요할 수 있습니다.

1. 입출력 최적화: 예를 들어, cout에서 endl을 사용하는 대신, "\n"을 사용해서 입출력 성능을 향상시킬 수 있습니다. 자세한 내용은 시간초과 문의를 참고하세요.

2. 재귀 호출 및 반복문 최적화: 만약 코드에서 재귀 호출을 많이 사용하고 있다면, 반복문으로 전환하거나 메모이제이션을 활용하여 중복 계산을 피하는 방안을 고려해 보세요. 관련된 답변은 2-F 시간 초과 질문에서 확인할 수 있습니다.

3. 데이터 구조 활용: 효율적인 데이터 구조로의 변경도 고려할 수 있습니다. 예를 들어, 많은 탐색이 이루어지는 경우 std::unordered_map을 사용하는 것이 도움이 될 수 있습니다.

해당 기술적 요소들을 점검하고, 필요한 경우 코드 상태나 구조를 변경하여 문제를 해결할 수 있습니다. 더 구체적으로 알고 싶은 부분이나 입출력의 최적화, 특정 알고리즘에 대한 추가 도움을 원하시면 언제든지 추가로 질문해 주세요.

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