그래프(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)를 표현하는 두 가지 대표적 방법의 차이점은?

해설

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

관련 문제

모두를 위한 진짜 쎈 바이브코딩