다음과 같은 재귀적(recursive) 그래프 탐색 알고리즘을 반복적(… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 09년 1회차
다음과 같은 재귀적(recursive) 그래프 탐색 알고리즘을 반복적(iterative) 알고리즘으로 구현하고자 한다. 그래프가 인접리스트(adjacency list)에 저장되어 있다고 가정할 때, 구현을 위하여 필요한 자료구조와 전체 그래프를 순회(traversal)하는 알고리즘의 시간복잡도(time complexity)를 옳게 나타낸 것은? (단, 정점의 집합은 V, 간선의 집합은 E라고 가정한다)
(알고리즘)
void search( vertex v )
{
visited[v] = 1 ;
for each vertex w adjacent to v
if ( !visited[w] ) search( w ) ;
}
1
queue, O( |E| )
2
stack, O( ∣V∣2|V|^2 )
3
stack, O( |V| + |E| )
4
queue, O( ∣V∣2|V|^2 )
해설

필요한 자료구조는 스택, 시간복잡도는 O(|V| + |E|)이다.

주어진 알고리즘은 방문하지 않은 인접 정점으로 재귀 호출을 이어 가는 깊이우선탐색이므로, 반복형으로 바꾸면 재귀 호출 스택을 명시적 스택으로 대신한다. 인접리스트에서는 각 정점을 한 번 방문하고 각 간선을 상수 번 검사하므로 정점 수와 간선 수의 합에 비례한다.

  • 큐와 O(|E|)의 조합: 큐는 너비우선탐색에 쓰는 자료구조이며, 정점 방문 비용인 |V| 항도 빠져 있다.
  • 스택과 O(∣V∣2)O(|V|^2)의 조합: 자료구조는 맞지만 제곱 시간은 인접행렬로 표현했을 때의 수행시간이다.
  • 큐와 O(∣V∣2)O(|V|^2)의 조합: 자료구조와 시간복잡도 모두 인접행렬 기반 너비우선탐색에 해당한다.

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

이어서 풀어보기

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