다음 연결리스트(linked list)로 표현된 그래프를 위한 두 연산… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 12년 1회차
다음 연결리스트(linked list)로 표현된 그래프를 위한 두 연산(A, B)에 대해 ‘최적으로 구현’한다고 할 때, 연산 A, B 각각에 대한 최악의 시간복잡도는? (단, 그래프의 노드의 개수를 n이라고 하고, 각 노드 쌍 사이에는 최대 1개의 간선(edge)이 존재할 수 있다)연산 (A) : 노드 i에서 노드 j로의 간선을 삽입한다. (단, 삽입 연산은 항상 간선이 존재하지 않는 노드 쌍에 대해서 수행된다)연산 (A) 연산 (B)
연산 (B) : 노드 i에서 노드 j로의 간선을 찾아 제거한다.
1
2
3
4
해설
인접 리스트에서 간선 삽입은 , 간선 제거는 이다.
삽입은 해당 간선이 없음이 보장되므로 중복 검사 없이 노드 i(무방향이면 j도)의 리스트 맨 앞에 새 노드를 붙이면 되어 상수 시간이다. 제거는 정렬되지 않은 리스트에서 j를 찾아야 하므로 최악의 경우 차수만큼, 즉 최대 n−1개를 훑어야 해 선형 시간이 든다.
- 삽입 ·제거 : 연결리스트는 이진 탐색이 불가하고, 제거는 탐색이 필요해 상수 시간이 될 수 없다.
- 삽입 ·제거 : 연결리스트에서는 위치를 로그 시간에 찾을 수 없어 제거는 선형 탐색이 필요하다.
- 삽입 ·제거 : 존재하지 않는 간선만 삽입한다는 조건이 있어 탐색 없이 맨 앞에 넣으면 되므로 삽입이 선형일 필요가 없다.
오류나 개정된 내용이 보이면 알려주세요
