자료구조 문제 정리 (4) 그래프

[그래프의 순회 : BFS, DFS]

 

(1)

다음 그래프를 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 방법으로 방문할 때

각 정점을 방문하는 순서로 옳은 것은? *시작 정점은 A이다, 알파벳 순서대로 방문한다.

• 너비 우선 탐색(BFS)

시작정점 A와 인접한 노드 B,F를 모두 삽입해야 하므로 A B F가 큐에 삽입되고 이 순서대로 방문한다

A B F C D E 순서대로 방문한다

• 깊이 우선 탐색(DFS)

시작 정점 A의 인접한 노드 중 하나만 선택하는데 알파벳 순서대로 선택하게 되면 A,B가 된다.

A B C D E F 순서대로 방문한다 

 

그래프의 깊이 우선 탐색은 스택을, 너비 우선 탐색은 큐를 이용한다.

 

(2)

다음 그래프의 정점 A에서부터 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 수행할 때, 방문 순서를 옳게 짝지은 것은? 

(단, 방문하지 않은 인접 정점이 2개 이상인 경우 알파벳 오름차순으로 방문한다)

• DFS : A B D G E C F
• BFS : A B C D E G F

 

[최소비용 신장트리]

(3)

정점의 개수가 n인 연결그래프에서 생성 가능한 신장트리의 간선 개수는?

 

신장트리는 그 그래프에서 모든 정점을 포함하며 사이클 없이 정점보다 하나 적은 수의 간선을 선택하여 생성한다.
정점의 개수가 n이라면 신장트리의 간선의 개수는 모두 n-1개이다

 

(4)

다음 가중치 그래프에서 최소 비용 신장트리의 가중치의 합은?

 

최소비용 신장트리를 구하는 크루스컬(kruskal) 알고리즘은 간선을 오름차순 정렬한 후

사이클이 발생하지 않도록 정점-1개의 간선을 선택한다.

정점이 다섯개이므로 가중치가 작은 간선 네개를 사이클 없이 차례대로 선택한다.

가장 비용이 작은 순서로 1,1,2,2가 선택된다.

1+1+2+2=6

 

 

(5)

다음 그래프를 대상으로 크루스컬 알고리즘을 이용한 최소 비용 신장 트리를 구성한다고 할 때

이 트리에 포함된 간선 중에서 다섯 번째로 선택된 간선의 비용으로 옳은 것은?

*크루스컬 알고리즘 : 작은 비용부터 순서대로 선택한다

• 첫번째로 선택되는 간선 : 가중치 3
• 두번째로 선택되는 간선 : 가중치 5
• 세번째로 선택되는 간선 : 가중치 6 
• 네번째로 선택되는 간선 : 가중치 9 (사이클이 생기기 때문에 7은 제외)
• 다섯번째로 선택되는 간선 : 가중치 12 (사이클이 생기기 때문에 10,11은 제외)

(6)

프림(Prim) 알고리즘

#무방향 그래프 #MST기반(최소비용) #임의의 정점을 잡고 확장해나간다

• 프림 알고리즘은 시작 정점을 시작으로 가중치가 작은 간선을 선택하여 하나의 최소비용 신장트리로 확장되어 간다.
• 임의의 최초 정점 선택 -> 최소 비용의 다음 정점 선택 -> 반복 (사이클이 생기지 않을 때까지)
• 선택된 집합 셋에서 연결된 모든 간선을 비교한다.

프림 알고리즘을 이용하여 최소 비용 신장 트리를 구하고자 한다. 다음 그림의 노드 0에서 출발할 경우 가장 마지막에 선택 되는 간선으로 옳은 것은?

 

 

정점이 7개이므로 사이클 없이 6개의 간선을 선택한다.

1. 첫번째 선택되는 간선은 (0,5)이다
2. 두번째 선택되는 간선은 (5,4)이다
3. 세번째 선택되는 간선은 (4,3)이다
4. 네번째 선택되는 간선은 (3,2)이다
5. 다섯번째 선택되는 간선은 (2,1)이다
6. 여섯번째 선택되는 간선은 (1,6)이다

 

(7)

크루스컬 알고리즘 VS 프림 알고리즘

 

프림 알고리즘은 단계적으로 최소비용으로 연결된 점을 추가하면서 최소비용 신장트리까지 자라나게 한다.

크루스컬 알고리즘은 가장 적은 비용을 가진 간선을 추가하면서 트리를 유지하는지 검사하여 최소비용 신장트리를 구한다.

 

크루스컬 알고리즘은 간선 중심으로, 프림은 정점 중심으로 최소신장 트리를 만들어나간다.

크루스컬은 매순간 find 연산 (O(1)의 시간 복잡도를 가진다) 으로 사이클 생성 여부를 판단하며, 속도에 영향을 미치는 것은 처음 간선을 오름차순으로 연결하는 것이다. 

프림은 시작 정점과 가까운 정점들을 연결하면서 그래프를 구성하여 사이클이 생기지 않는다.

 

그래프 내의 간선이 많은 경우는 임의의 정점을 잡고 실행하는 프림 알고리즘,

간선이 적은 경우는 적은 비용을 골라서 실행하는 크루스컬 알고리즘이 유리하다

 

프림 알고리즘은 O(N^2)의 시간복잡도를 가지며 *노드의 개수는 N

크루스컬 알고리즘은 O(ElogE)의 시간 복잡도를 가진다 * 간선의 개수는 E

 

 

(8)

• 동적 계획법은 부분 문제 각각의 해에서 그것들의 원래 문제의 해의 구성법을 얻는 원리, 최적해를 구하는 기법이다.
• NP 문제는 컴퓨터를 이용하여 다항시간에 해결할 수도 있다. 어느 하나의 NP 완전 문제에 대해서 다항식 시간의 알고리즘을 찾아내면 모든 다른 NP 완전 문제도 다항식 시간에 해를 구할 수 있다

(9)

양자 컴퓨팅의 특징

• 양자 중첩 : 둘 이상의 상태가 함께 공존이 가능하다. 0과 1이 동시에 존재할 수 있다
• 양자 얽힘 : 물리적으로 완전히 분리된 두 물질이 상호작용하는 현상으로 얽힘 상태의 양자는 한쪽의 동작에 따라 반대쪽의 동작을 예측 가능하다
• 불확정성 : 두 개의 관측가능량을 동시에 측정할 때, 둘 사이의 정확도에는 물리적 한계가 존재한다는 원리이다.

양자 키분배는 송신자와 수신자 사이에 안전하게 분배하는 기술로 안전한 통신을 위한 암호체계이다.

기존에 있던 대부분의 암호체계가 대부분 수학적 복잡성에 기반하는데 비해, 양자 암호는 자연현상에 기반하고 있는 특징을 띄며, 암호에 사용되는 원타임 패드를 생성하는 이상적인 방법 중 하나다.