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

안녕하세요 찬욱님 ㅎㅎ

C++ 이외의 다른 언어로는 질문을 받지 않습니다.

감사합니다.

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

JavaScript에서 맵(Map) 자료형과 배열(Array)를 사용하여 그래프를 구현할 때의 시간 복잡도 차이에 대한 질문을 주셨군요.

일반적으로 맵 자료형은 키-값 쌍을 저장하며, 키를 통해 값을 빠르게 억세스할 수 있어 탐색, 삽입, 삭제 연산에서 평균적으로 O(1)의 시간 복잡도를 가집니다. 반면 배열은 인덱스를 통해 억세스하기 때문에 인덱스에 따라 데이터를 빠르게 접근할 수 있으나, 특정 값을 찾기 위한 탐색에서는 최악의 경우 O(N)의 시간이 소요됩니다.

그러나 그래프 구현에서 두 자료형의 시간 복잡도가 항상 다르게 나타나는 것은 아닙니다. 맵과 배열 모두 그래프의 특정 노드에 연결된 모든 노드를 방문하는 연산은 O(E)의 시간 복잡도를 가진다고 볼 수 있습니다. 문제는 어떻게 그래프 데이터를 접근하고 처리하는가에 달려 있습니다.

제시한 링크의 두 코드 사이에서 발생하는 시간 초과는 그래프를 어떻게 구현했는지도 중요하지만, 그보다는 그래프 탐색 알고리즘의 전체적인 구현 방식과 효율성에 더 크게 좌우될 가능성이 높습니다. 가령, 맵을 사용하는 경우에는 존재하지 않는 키에 접근할 때 바로 ‘undefined’ 등을 반환받을 수 있지만, 배열을 사용하는 경우에는 불필요하게 전체 배열을 확인할 필요가 있을 수도 있습니다. 따라서 전체 코드의 로직을 점검하고 어디에서 비효율적으로 시간이 소요되고 있는지 확인해보는 것이 좋겠습니다.

그리고 말씀하신대로 맵을 이용한 그래프 구현이 탐색에서 더 빠를 수 있으며, 배열을 이용한 경우에는 동일한 연산에서 더 많은 시간이 소요될 수도 있습니다만, 이는 전체적인 알고리즘의 복잡도와도 밀접한 연관이 있습니다. 그래프의 정점(V) 수와 간선(E) 수에 따라 시간 복잡도가 달라지기 때문에 구현 방식에 따라 O(V+E) 또는 O(VE) 등으로 달라질 수 있습니다.

참고로 인프런에서는 알고리즘 관련 질문보다는 강의 이용과 관련된 문의를 메인으로 다루고 있습니다. 코드상의 문제를 해결하고 싶으시다면 문제의 원인을 더 구체적으로 분석해 보시고, 그래프 구현 방식 외에도 전체 로직에서의 최적화 가능성을 살펴보시는 것도 좋을 것 같습니다.

감사합니다!