그래프(Graph)를 표현하는 두 가지 대표적 방법의 차이점은?

어려움 freeCodeCamp

보기 및 정답

A 인접 행렬(Adjacency Matrix)은 2D 배열로, 인접 리스트(Adjacency List)는 연결된 노드 목록으로 표현하며, 인접 리스트가 희소 그래프에 유리하다

B 인접 행렬(Adjacency Matrix)은 트리 구조만 표현할 수 있고, 인접 리스트(Adjacency List)는 일반 그래프만 표현할 수 있으며, 두 방법은 서로 호환되지 않는다

C 인접 행렬(Adjacency Matrix)은 항상 인접 리스트(Adjacency List)보다 메모리를 적게 사용하며, 모든 종류의 그래프에서 인접 행렬이 더 효율적이다

D 인접 행렬과 인접 리스트는 동일한 방식으로 그래프를 표현하며 메모리 사용량과 탐색 시간 복잡도가 완전히 같아서 어떤 것을 선택해도 차이가 없다

해설

인접 행렬은 V x V 크기의 2D 배열로 모든 노드 쌍의 연결 여부를 저장합니다(O(V^2) 공간). 인접 리스트는 각 노드마다 연결된 노드 목록만 저장합니다(O(V+E) 공간). 간선이 적은 희소 그래프에는 인접 리스트가, 간선이 많은 밀집 그래프에는 인접 행렬이 효율적입니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

그래프(Graph)를 표현하는 두 가지 대표적 방법의 차이점은?

해설

코딩, 제대로 배우고 싶다면?

관련 문제

시장과 사람의 답을 봤다면,다음 결과물의 구조를 고릅니다.

시장과 사람의 답을 봤다면,
다음 결과물의 구조를 고릅니다.