2-S 자바스크립트 코드 질문있습니다!

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요.
2-S 문제를 자바스크립트로 구현해보았는데
첫번째 링크의 코드와 두번째 링크 코드의 차이는 그래프를 맵으로 구현한 것과 배열로 구현한 것 차이라고 생각합니다.
맵 자료형의 Value에 해당하는 부분도 배열로 구현했기에 두 코드의 시간복잡도가 동일하다고 생각했는데 첫번째 링크는 통과하고 두번째 링크는 시간초과가 나옵니다.
맵으로 구현한 코드가 O(V+E)라면 배열로 구현한 코드가 O(V*E)라서 시간초과가 나는걸까요??

감사합니다!

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

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

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

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

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

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

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

감사합니다!

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