한국어
메뉴

자료 구조와 알고리즘

정점이 100만 개, 간선이 300만 개 정도인 도로망처럼 정점 수에 비해 간선이 적은(희소한) 그래프를 메모리에 저장하는 방법으로 적절한 것은?

  1. A인접 행렬. 두 정점 사이에 간선이 있는지를 O(1)로 조사할 수 있고, 기억 영역도 가장 적게 든다
  2. B인접 리스트. 기억 영역은 정점 수와 간선 수의 합에 비례하며, 어떤 정점에서 나가는 간선을 차례로 따라가는 데 적합하다
  3. C인접 행렬. 기억 영역은 간선 수에만 비례한다
정답과 해설 보기

정답: B. 인접 리스트. 기억 영역은 정점 수와 간선 수의 합에 비례하며, 어떤 정점에서 나가는 간선을 차례로 따라가는 데 적합하다

인접 행렬은 정점 수 V에 대해 V×V의 표를 사용하므로, 100만 정점에서는 10¹²개의 원소가 필요하며 원소 하나를 1비트로 해도 약 125 GB가 됩니다. 인접 리스트는 각 정점에 이어진 정점만 나열하므로 기억 영역은 O(V + E)이며, 이 예라면 수백만 건 정도로 충분합니다. 인접 행렬은 간선의 유무를 O(1)로 조사할 수 있는 이점이 있어, 간선이 많은(밀집한) 그래프나 정점이 적은 그래프에 적합합니다. 너비 우선 탐색이나 다익스트라 알고리즘처럼 정점에서 나가는 간선을 차례로 따라가는 처리에서는 인접 리스트가 더 효율적으로 동작합니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 간선에 가중치가 없는 그래프에서, 출발점에서 각 정점까지의 최소 간선 수를 구하고 싶다. 적합한 탐색 방법과 그때 사용하는 자료 구조의 조합은?
  2. 간선에 방향이 없는 그래프에서 각 정점의 이웃 정점이 다음과 같다. A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. 정점 A부터 재귀적인 깊이 우선 탐색을 수행한다. 이웃 정점은 여기에 쓴 순서로 조사하고, 아직 방문하지 않은 정점이 발견되면 바로 그 정점으로 나아간다. 정점을 방문하는 순서는?
  3. 간선에 방향이 없는 그래프에서 간선의 가중치(거리)가 S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3, A−T: 6이다. 다익스트라 알고리즘으로 S에서 T까지의 최단 경로를 구했을 때, 그 경로와 길이는?
  4. 다익스트라 알고리즘으로 올바른 최단 경로를 구하기 위한, 그래프에 관한 조건으로 올바른 것은?
  5. 작업 A~E에 'A는 C보다 앞', 'B는 C보다 앞', 'C는 D보다 앞', 'B는 E보다 앞', 'E는 D보다 앞'이라는 순서 제약이 있다. 모든 제약을 만족하는 작업의 순서(위상 정렬의 결과)는?