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

안녕하세요 대기업님ㅎㅎ

잘짜셨네요 ㅎㅎ

네 시간복잡도도 잘 계산하셨습니다.

주요 시간복잡도는

n 곱하기 dfs라고 보면 되구요.

dfs자체도 최대 n번 돌아가기 때문에 최대 10000 * 10000이 되어 1억이 되고출력 등은 무시하셔도 되지만 굳이 따지자면 대기업님 말씀처럼 100,110,000이 됩니다.

감사합니다.

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

코드 효율성 및 시간 복잡도

질문하신 코드의 효율성 및 시간 복잡도에 대해 설명드리겠습니다. 주어진 문제와 관련된 코드가 그래프 탐색 문제로 보입니다. 이럴 경우, 주로 DFS(깊이 우선 탐색)나 BFS(너비 우선 탐색)을 사용하며, 그래프의 정점과 간선의 수에 따라 시간 복잡도가 결정됩니다.

현재 언급한 내용 기반으로 코드의 구조를 추측해보니, 시간 복잡도 평가에 다음과 같은 방식으로 접근할 수 있습니다.

1. while 반복문: 100,000번 수행된다는 것은 아마도 입력을 받아 수행되는 동작이 아닐까 추측됩니다. 다만, 실제 비교 시 주 구성 요소는 아닐 것으로 보입니다.

2. for 및 dfs 반복문: 모든 정점에 대해 탐색을 수행하는 것으로, 한 정점에서 연결된 모든 정점을 탐색하여 각 정점에서 시작하는 깊이우선 탐색을 한다면, 최악의 경우 O(N * M) 즉, O(정점 수 * 간선 수)로 나타낼 수 있습니다. 그런데, 문제마다 이 부분이 어떻게 최적화되는지에 따라 다를 수 있으니 유의하세요.

3. 출력 반복문: 이 또한 일반적으로 전체 정점을 순회하는 정도라면 O(N) 정도로 볼 수 있습니다.

따라서, 가장 큰 주범이 될 수 있는 부분은 dfs를 통해 수행되는 반복 구문의 복잡도이며, 이는 최대 O(N * M)이 될 수 있습니다. 따라서, 최악의 경우에 해당하는 연산이 어느 정도 클 수 있으니, 코드 최적화가 필요할 수 있습니다.

기존 유사한 질문 링크 참고

유사한 문제가 다른 질문에서도 다루어졌기 때문에, 참고할 만한 링크를 공유드립니다:

1. 2-S 1325 질문입니다.

   • 이 질문에서는 DFS를 활용하여 불필요한 중복 호출로 인한 시간초과 문제를 해결하는 방법이 다루어지고 있습니다. 코드를 비교하면서 탐색 호출의 최적화를 생각해 볼 수 있습니다.
     

2. 코드 효율성 질문드려요

   • 시간 복잡도 분석 및 로그리즘 관련 최적화 방법이 포함된 답변을 참조하면 좋습니다.
     

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