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

안녕하세요 대기업님 ㅎㅎ

1번 : 네 맞습니다.

2번 : 최대경로가 D라고 했을 때 대기업님은 매번 반복하기 때문에 O(V * D)이고 제꺼는 O(V + D)가 됩니다.

3번은 교안의 다음 부분 참고부탁드립니다.

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

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

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 대기업목표님.

질문 1: 로직의 타당성 및 시간 복잡도

1. 로직 자체의 타당성: 제시하신 로직을 간략히 분석한 결과, 기본적으로 숨바꼭질 유형 문제에서의 그래프 탐색 방법론을 사용한 것으로 보입니다. 즉, BFS(너비 우선 탐색)를 통해 최단 경로를 찾는 방식인데, 올바르게 구현하셨다면 논리적으로 맞아야 합니다. 하지만 구체적인 코드 구현에 따라 달라질 수 있으니 강사가 제공한 해설 코드와 비교하며 차이점을 확인하는 것이 중요합니다.

2. 시간 복잡도:

   • 일반적으로 이 문제에서 BFS를 사용하면 각 노드를 한 번만 방문하므로 최악의 경우 시간 복잡도는 O(N + M)이며, 여기서 N은 노드의 수, M은 간선의 수입니다. 문제의 특성상 주어진 수의 범위 내에서 관련 노드를 탐색하므로 O(N)형태로 간주할 수 있습니다.
     
   • 강사의 코드도 유사한 복잡도를 가질 것입니다. BFS의 효율성을 최대로 활용한 경우라면 크게 다르지 않겠지만, 구현 디테일에서 성능 차이가 날 수 있습니다.
     

질문 2: 컴파일 오류의 원인

• prev 변수 오류: prev 변수를 사용하는 과정에서 컴파일 오류가 발생했다면, 이 변수의 선언과 초기화, 그리고 사용 위치를 확인하는 것이 중요합니다.
  
  • Declaration Scope: prev 변수를 사용했을 때 해당 변수가 함수 내부에 정확히 여러 번 선언되었거나 범위를 벗어났거나 정확히 초기화되지 않은 것이 원인이 될 수 있습니다. 따라서, 변수를 사용할 때 적절한 범위 내에 선언되었는지, 초기화가 제대로 되었는지 확인해야 합니다.
    
  • Name Conflict: prev가 이미 다른 목적으로 사용되거나 예약어로 설정되어 있을 수 있습니다. 따라서 변수명을 변경하여 해결할 수 있는지 확인해 보세요.
    

기존 유사 질문 참고

이전에 비슷한 문제들이 질문되어 해결된 사례를 참고하시면 도움이 될 것입니다. 다음 링크들을 확인해 보세요:

• 3-H 시간초과 관련 질문
  
  • 이 질문에서는 BFS 로직 개선 및 시간초과를 해결하는 방법이 잘 설명되어 있어서 힌트를 얻을 수 있습니다.
    

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