다음 연결리스트(linked list)로 표현된 그래프를 위한 두 연산… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 12년 1회차
다음 연결리스트(linked list)로 표현된 그래프를 위한 두 연산(A, B)에 대해 ‘최적으로 구현’한다고 할 때, 연산 A, B 각각에 대한 최악의 시간복잡도는? (단, 그래프의 노드의 개수를 n이라고 하고, 각 노드 쌍 사이에는 최대 1개의 간선(edge)이 존재할 수 있다)
연산 (A) : 노드 i에서 노드 j로의 간선을 삽입한다. (단, 삽입 연산은 항상 간선이 존재하지 않는 노드 쌍에 대해서 수행된다)
연산 (B) : 노드 i에서 노드 j로의 간선을 찾아 제거한다.
연산 (A) 연산 (B)
문제 이미지
1
O(1)O(1) O(n)O(n)
2
O(log⁡n)O(\log n) O(1)O(1)
3
O(1)O(1) O(log⁡n)O(\log n)
4
O(n)O(n) O(n)O(n)
해설

인접 리스트에서 간선 삽입은 O(1)O(1), 간선 제거는 O(n)O(n)이다.

삽입은 해당 간선이 없음이 보장되므로 중복 검사 없이 노드 i(무방향이면 j도)의 리스트 맨 앞에 새 노드를 붙이면 되어 상수 시간이다. 제거는 정렬되지 않은 리스트에서 j를 찾아야 하므로 최악의 경우 차수만큼, 즉 최대 n−1개를 훑어야 해 선형 시간이 든다.

  • 삽입 O(log⁡n)O(\log n)·제거 O(1)O(1): 연결리스트는 이진 탐색이 불가하고, 제거는 탐색이 필요해 상수 시간이 될 수 없다.
  • 삽입 O(1)O(1)·제거 O(log⁡n)O(\log n): 연결리스트에서는 위치를 로그 시간에 찾을 수 없어 제거는 선형 탐색이 필요하다.
  • 삽입 O(n)O(n)·제거 O(n)O(n): 존재하지 않는 간선만 삽입한다는 조건이 있어 탐색 없이 맨 앞에 넣으면 되므로 삽입이 선형일 필요가 없다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 12년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기