Socrative 풀이 - Data Structure Part 3 (Graph & Tree & Binary Search Tree)

이번 소크라티브는 15문제로 문제 양이 꽤 많다.
꽤 많지만 풀이를 해보려고 한다.

1. 그래프에 대한 설명으로 틀린 것을 모두 고르면?

A. 정점(vertex)과 간선(edge)로 이루어져 있다.
B. 간선이 방향을 가지는 방향 그래프와, 간선에 방향이 없는 무향 그래프로 나뉜다.
C. 순환 구조를 가질 수 있다.
D. 루트 정점이 존재한다.
E. 그래프의 간선은 모두 같은 가중치 값을 가져야 한다.

풀이)
A. 정점(vertex)과 간선(edge)로 이루어져 있다.
-> O, 정점(vertex)는 노드(node)와 같은말이다. 그래프는 이 정점과 간선으로 구성되어 있다.
B. 간선이 방향을 가지는 방향 그래프와, 간선에 방향이 없는 무향 그래프로 나뉜다.
-> O, 그래프의 대표적인 종류는 방향 그래프와 무향(무방향)그래프가 있다.
나같은 경우는 그래프는 무방하다. 라고 생각했다. (무방하다 = 무방향 방향)
C. 순환 구조를 가질 수 있다.
-> O, 그래프의 구성도를 보면 서로 순환한다는것을 알 수 있다.
D. 루트 정점이 존재한다.
-> X, 정점(vertex)는 노드(node)라고도 불리는데, 그래프는 루트 노드라는 개념이 없다.
즉, 루트 정점이 존재하지 않는다.
E. 그래프의 간선은 모두 같은 가중치 값을 가져야 한다.
-> X, 그래프의 종류 중에서는 가중그래프가 존재하는데 이 그래프는 정점 사이의 잇는 간선에 가중치가 주어진 그래프로, 가중치는 어떠한 값을 비교하기 위해 존재하며 그 값은 같을 수도 있고 다를 수 있다.

따라서 답은 D,E이다.

2. 정점의 개수가 5개인 방향 그래프의 최대 간선 개수는? (단, 자기 간선, self edge, self loop은 없다고 가정한다.)

A. 5
B. 10
C. 20
D. 25

풀이)
정점의 개수가 n개인 방향 그래프의 최대 간선의 개수를 구하는 공식은 n(n-1)이다.
여기에 n에 5를 대입하면 5*4=20이다.
참고로 정점의 개수가 n개인 무방향 그래프의 최대 간선의 개수를 구하는 공식은 n(n-1)/2이다.

따라서 답은 C이다.

3. 다음 그래프에서 Vertex C의 in degree와 out degree의 합은?
   

A. 1
B. 2
C. 3
D. 4
E. 5

풀이)
C로 들어오는 진입차수(in degree)는 A와 B로 2개이고, C에서 나가는 진출차수(out degree)는 D로 1개이다. 그래서 2+1=3이다.

따라서 답은 C이다.

4. 그래프를 인접 행렬(Adjacent Matrix)로 구현할 때의 공간 복잡도는? (V = Vertex, E = Edge)

A. O(V^2)
B. O(V^2 + E)
C. O(V + E)
D. O(V + 2E)

풀이)
인접 행렬 (Adjacent Matrix)은 정방 행렬을 사용하는 방법이다.

해당하는 위치의 value 값을 통해서 Vertex 간의 연결 관계를 O(1) 로 파악할 수 있으며 Edge 개수와는 무관하게 O(V^2) 의 공간복잡도를 갖는다.

그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph) 의 경우에 이 방법을 쓰면 유리하다.
두 정점을 연결하는 간선의 존재 여부를 O(1) 안에 즉시 알 수 있지만 그래프에 존재하는 모든 간선의 수는 O(V^2) 안에 알 수 있다.

따라서 답은 A이다.

5. 그래프를 인접 리스트(Adjacent List)로 구현할 때의 공간 복잡도는? (V = Vertex, E = Edge)

A. O(V^2)
B. O(V^2 + E)
C. O(V + E)
D. O(V + 2E)

풀이)
인접 리스트 (Adjacent List)는 연결 리스트를 사용하는 방법이다.

Vertex 의 인접 리스트를 확인해봐야 하므로 Vertex 간 연결되어있는지를 각각 확인해야하며 공간복잡도는 O(V+E) 를 갖는다.

그래프 내에 간선의 숫자가 적은 희소 그래프(Sparse Graph) 의 경우에 이 방법을 쓰면 유리하다.
그래프에 존재하는 모든 간선의 수는 O(V+E) 안에 알 수 있지만 두 정점 사이에 간선의 존재 여부는 해당 정점의 차수만큼의 시간이 필요하다.

따라서 답은 C이다.

6. 그래프의 시간 복잡도와 관련하여, 각 빈칸에 들어갈 말로 가장 적합한 것을 고르시오.

- 정점의 추가는 ( ) 방식이 효율적이다.
- 정점의 삭제는 ( ) 방식이 효율적이다.
- 간선의 추가와 삭제가 빈번히 일어나는 경우에는 ( ) 방식이 효율적이다.

A. (인접 행렬, 인접 리스트, 인접 리스트)
B. (인접 행렬, 인접 리스트, 인접 행렬)
C. (인접 리스트, 인접 행렬, 인접 행렬)
D. (인접 리스트, 인접 리스트, 인접 행렬)
E. (인접 리스트, 인접 행렬, 인접 리스트)

풀이)
인접행렬에서 정점은 추상화된다.
위의 문제 풀이에서 말했듯이 간선이 많이 존재하는 밀집 그래프에는 인접행렬이 유리하고, 일반적인 간선의 추가/삭제는 행렬보다 리스트가 효율적이다.

따라서 답은 D이다.

7. 다음 중 트리의 특성이 아닌 것을 모두 고르면?

A. 트리는 그래프의 한 종류이다.
B. 하나의 부모 노드만 가질 수 있다.
C. 순환 구조를 가질 수 있다.
D. 자식 노드는 최대 2개까지 가질 수 있다.

풀이)
A. 트리는 그래프의 한 종류이다.
-> O, 그래프의 종류에는 방향그래프와 무방향그래프가 있는데, 트리는 무방향그래프의 예시이다.
B. 하나의 부모 노드만 가질 수 있다.
-> O, 각각 하나의 부모 노드만 가질 수 있다. 모르겠으면 트리의 구성도를 찾아보면 알 수 있다.
C. 순환 구조를 가질 수 있다.
-> X, 트리는 비순환 구조이고 그래프는 순환 구조이다.
D. 자식 노드는 최대 2개까지 가질 수 있다.
-> X, 이진 트리의 특성이다. 이 문제는 그냥 트리의 특성을 물어보고 있다.

따라서 답은 C,D이다.

8. 다음과 같은 트리의 높이(height)는? (root Node의 depth는 0으로 간주한다.)
   ※ root Node의 depth를 1로 간주할 수도 있습니다. 이 문제의 핵심은 '특정 기
   준에서 트리가 얼마큼의 깊이를 가지고 있느냐' 입니다.
   

A. 1
B. 2
C. 3
D. 4

풀이)
트리에서는 depth = height = level 이다.

root Node의 depth는 0으로 간주한다.-> 트리의 높이를 구하라는 뜻이다.
만약 root Node의 depth를 1로 간주할 수도 있습니다.-> 이말이 나오면 노드의 높이를 구하라는 뜻이다.

여기서 주의할점은 트리의 height와 노드의 height는 다른 말이라는 것이다.
★ 트리의 높이는 0부터 시작하고, 노드의 높이는 1부터 시작한다.

이 문제에서는 트리의 높이를 구하라고 했다.
따라서 1번 줄 높이 : 0
1번줄에서 2,3번줄까지의 높이 : 1
1번줄에서 4,5번줄까지의 높이 : 2
1번줄에서 6,7번줄까지의 높이 : 3

따라서 답은 C이다.

9. 다음과 같은 트리의 리프(leaf) 노드 개수는?
   

A. 1
B. 2
C. 3
D. 4

풀이)
리프(leaf)노드는 더이상 뻗어나가는 차수가 없는 노드를 말한다.
여기서의 리프노드는 3,4,6,7로 총 4개다.

따라서 답은 D이다.

10. 다음과 같은 트리를 "중위순회"한 결과는?
    

A. A-B-D-G-H-E-C-F
B. G-D-H-B-E-A-C-F
C. G-H-D-E-B-F-C-A
D. B-A-C-G-D-H-E-F

풀이)
중위순회의 순서는 왼쪽 -> 루트 -> 오른쪽이다.
왼쪽부터 중위순회 순서대로 나가면 G-D-H, 이 G-D-H를 한 덩어리로 묶고
H를 왼쪽의 노드라고 치자. 그러면 G-D-H-B-E, 이 G-D-H-B-E를 한 덩어리로 묶자.
그리고 E를 왼쪽의 노드리고 친뒤 또 중위순회를 한다. 그러면 G-D-H-B-E-A-C-F이다.

따라서 답은 B이다.

11. 다음과 같은 이진 트리에 해당하는 이진 트리의 종류를 모두 고르면?
    

A. 정 이진 트리 (Full Binary Tree)
B. 완전 이진 트리 (Complete Binary Tree)
C. 포화 이진 트리 (Perfect Binary Tree)

풀이)
정 이진 트리 (Full Binary Tree): 모든 노드의 차수가 0 또는 2인 트리
완전 이진 트리 (Complete Binary Tree): 왼쪽 자식노드부터 채워지며 마지막 레벨을 제외하고는 모든 자식노드가 채워져있는 트리
포화 이진 트리 (perfect Binary Tree): 모든 레벨에서 0개 혹은 2개의 자식노드를 가진 노드가 꽉 채워진 트리. 한마디로 좌우대칭.ㅋㅋ

여기서 노드들의 차수는 0인 것도 있고(G), 나머지는 다 2이다. 그리고 C의 트리를 보면 G의 마지막 레벨에서는 차수가 없어서 F쪽이 왼쪽으로 치우쳐져 있다.

따라서 답은 A,B이다.

12. 다음 이진 탐색 트리에 대한 설명 중 틀린 것을 모두 고르면?

A. 자식 노드를 최대 2개까지 가질 수 있다.
B. 항상 왼쪽 서브트리에는 작은 값이, 오른쪽 서브트리에는 큰 값이 존재한다.
C. 이진 탐색 트리는 항상 완전 이진 트리이다.
D. 원하는 값을 찾기 위해서 최대 트리의 높이(h)만큼의 탐색이 필요하다.
E. 자식 노드의 값 보다 부모 노드의 값이 항상 크다.

풀이)
A. 자식 노드를 최대 2개까지 가질 수 있다.
-> O, 자식 노드가 아예 없을 수도 있고, 있더라도 최대 2개까지만 가능하다.
B. 항상 왼쪽 서브트리에는 작은 값이, 오른쪽 서브트리에는 큰 값이 존재한다.
-> O, 좌소우대 라고 외우면 될것같다.ㅋㅋㅋㅋ 나의 줄임말 탄생
C. 이진 탐색 트리는 항상 완전 이진 트리이다.
-> X, 이진 탐색 트리의 종류에는 정 이진 트리, 완전 이진 트리, 포화 이진 트리가 있으며, 케바케이다. 그러므로 항상 완전 이진 트리라고 할순 없다.
D. 원하는 값을 찾기 위해서 최대 트리의 높이(h)만큼의 탐색이 필요하다.
-> O, 원하는 값을 찾기 위해선 트리의 최대 깊이만큼 파고들어서 찾아야 한다.
E. 자식 노드의 값 보다 부모 노드의 값이 항상 크다.
-> X, 부모 노드의 왼쪽에 있는 자식 노드의 값은 부모 노드의 값보다 항상 작고, 부모 노드의 오른쪽에 있는 자식 노드의 값은 부모 노드의 값보다 항상 크다. 따라서 무조건 자식 노드의 값보다 부모 노드의 값이 항상 크다고 할순 없다.

따라서 답은 C,E이다.

13. 이진 탐색 트리를 정렬하여 출력하기 위한 순회 방법은?

A. Pre-order Traversal (전위순회)
B. In-order Traversal (중위순회)
C. Post-order Traversal (후위순회)
D. None of the above

풀이)
이진 탐색 트리는 왼쪽->루트->오른쪽으로 순회한다.
그러므로 중위순회라고 생각하면 된다.

따라서 답은 B이다.

14. 이진 탐색 트리에서 child가 2개인 노드를 삭제하는 방법은 일반적으로 2가지가 있다.
    이 방법을 적용하여 아래 이진 탐색 트리에서 21을 삭제했을 때, 새로운 루트 노드가 되는 값은 각각 무엇인가? (순서무관)
    

A. 17, 40
B. 19, 25
C. 11, 49
D. 19, 49
E. 11, 25

풀이)
21을 삭제하고난뒤 오른쪽 서브트리의 최소값을 새로운 루트 노드로 변경했을 때 이진 탐색 트리의 형태는 아래의 그림과 같다.

어떻게 된 것인가?
삭제 루틴은 삭제할 노드의 자식이 0,1,2개인 경우로 나눠서 설명할 수 있다.

0개인 경우 : 그냥 삭제하면 끝
1개인 경우 : 자기를 지우고 자기 자식을 부모랑 연결
2개인 경우 : 왼쪽 서브트리에서 가장 큰값을 찾거나 오른쪽 서브트리에서 가장 작은값을 찾아서 내 자리로 올려놓으면 된다.

위의 경우는 21을 삭제하면서 왼쪽 서브트리의 가장 큰값은 19, 오른쪽 서브트리에서 가장 작은 값은 25가 된다.
그런데 만약 21을 삭제한 자리에 19를 넣게되면 오른쪽 서브트리의 값을 싹다 바꿔야하는 불상사가 생기고 만다.;;
그래서 왼쪽 서브트리의 균형과 오른쪽 서버트리의 값을 최대한 유지하게 할 수 있는 25가 최상단 루트노드에 온다.

삭제한 21과 비교했을 때 왼쪽 서브트리에서 21과 가장 근접한 값은 19, 오른쪽 서브트리에서 21과 가장 근접한 값은 25이다.

따라서 답은 B이다.

15. 이진 탐색 트리에서 노드의 추가(insertion), 삭제(deletion), 조회(retrieval)의 시간 복잡도를 순서대로 나열한 것은?

A. O(logN) , O(logN) , O(N)
B. O(logN) , O(N) , O(logN)
C. O(N) , O(N) , O(N)
D. O(logN) , O(logN) , O(logN)

풀이)
A. O(logN) , O(logN) , O(N)
-> X, 이건 뭐 듣보잡 조합이다.;;;
B. O(logN) , O(N) , O(logN)
-> X, 이것도 역시 듣보잡 조합이다.;;;
C. O(N) , O(N) , O(N)
-> O, 일반적인 이진 탐색 트리에서는 깊이만큼 시간이 걸린다.
D. O(logN) , O(logN) , O(logN)
-> X, 밸런스가 잘 맞춰진 포화 이진 트리에서 가능

따라서 답은 C이다.