<자료구조> 트리 쪽지 시험 후기 + 그래프(1):그래프 용어 정리

>>트리 쪽지 시험 후기

 매 단원마다 우리 교수님은 항상 쪽지 시험을 치셨는데 한번도 기록을 한적이 없어 이번 기회에 한번 해보고자 한다. 우선 성적을 말하자면 96%인데 시험이 80점 만점이고 프로그램에서는 퍼센트로 알려주는 신박한(?) 점수 채점법이기에 그냥 퍼센트로 외운다... 등수는 1등이긴하나 사실 등수모단 모두 맞는 것에 목표를 두고 있기에 오답과 문제 풀이 후기 위주에 가깝다.

 종합적으로 보았을 때 문제 난이도는 그다지 어렵지 않았는데 전체 문제 개요는 아래와 같다.

1. 일정 순서로 Max heap을 입력하였을 때 6번째 인덱스의 수

2. 일정한 순서로 이진 검색 트리를 입력한 후 postorder로 읽기

3. 전체 노드의 수를 구하는 recursion 함수

4. 이진 트리의 성질 

5. winner 기반의 선택트리에서 pop 3번했을 때 index 1,2의 수의 합

6. postorder와 inorder을 주고 원래 이진 트리를 그린뒤 리프노드 입력

7. 좌우 노드를 반대로 가지는 트리를 복사하는 recursion 함수

8.  inpred함수에서 초기값의 포인터

 

내가 틀린 부분은 이진 트리의 성질 중에서 노드의 갯수와 link 수의 관계를 틀렸다. 3개중 2개만 체크.

후기 : 항상 느끼는 거지만 코테처럼 함수 정의만 주고 코드를 짜라 했으면 어려웠겠으나 그렇지 않았기에 10분만에 풀기엔 나쁘지 않은 문제였다. 6번 문제를 postorder의 특성처럼 뒤부터 읽는게 아니라 inorder 앞의 3개 노드로 작은 트리를 그리고 거기에 덧붙이는 방식을 택했는데 시간이 너무 오래 걸려 다음부터 이렇게 풀면 안되겠다 라는 생각을 했다.

 

 

>>그래프(1)

아무래도 교수님이 쪽지 시험을 치신 것도 있고 오답도 하신다고 그다지 길게 하시지 않아 용어 정리만 하였다.

 

1. 그래프란

 그래프는 객체 간의 관계를 표현하는 자료구조이다. 객체 간의 관계를 표현하는 것이 트리처럼 작은게 아니라 거의 밀림 수준으로 얽혀있다. 이 그래프가 활용된 사례로 유명한 것은 facebook의 사람들과의 트리와 네비게이션, 통신망이 가장 유명한데. 보면서 내 알고리즘에 나왔던 "이건 A* 알고리즘이야!"라고 외치던 공포게임 화면이 생각났다.. 실제로 그래프의 활용형이라 한다.

 교수님의 예제로는 과거 오일러가 풀었던 퀘니스베르그의 다리라는 문제가 나왔고 이는 말이 어렵지 그냥 한붓그리기다.

 

2. 그래프와 관련된 용어

V(G) = 그래프 G에 포함된 vertex(정점)들의 집합

E(G) = 그래프 G에 포함된 edge(간선, 엣지)들의 집합

무방향성 그래프 = Vectex의 쌍을 나타내는 edge가 방향이 없음 -> 표기 : (a,b)

방향성 그래프 = 각 edge가 방향성이 존재함 -> 표기 : <a,b>, 이때 a를 tail, b를 head라 한다.

 

완전 그래프 : edge 수가 최대인 그래프

인접 : 무방향성 그래프에서 egde일 경우 인접한다. / 방향성 그래프에서는 a는 b에 인접한다 or b는 a에 인접한다.

부분 그래프 : G'의 vertex와 edge가 G에 포함된 경우 G'는 G의 부분 그래프

 

경로 : a에서 시작해서 b로 끝나는 경우의 수 (최적 X)

단순 경로 : 처음과 마지막을 제외한 vertex가 다른 경로

사이클 : 처음과 마지막이 동일한 단순 경로

연결 : a,b가 연결될 경우 연결 / 방향성이었다면 strongly connected라 한다! 

연결 요소 : maximal connected subgraph 이만큼 완벽한 설명이 없다

 

트리 : 사이클이 없는 연결 그래프

차수 : 한 vertec에 부속된 edge의 수 / in-degree : 내차수 / out-degree : 외차수

Digraph : Directed Graph의 준말