2. 자료구조와 알고리즘 [기출, 핵심, 응용]

 

이 파트는 매우 매우 중요하다.

 

* 참고 교재: 쉽게 배우는 알고리즘, 개정판 (문병로)

* 참고 교재: C++로 구현하는 자료구조와 알고리즘, 2판(M.T. Goodrich)

 

[기출편]

Q. 트리를 정의하라. 이진 트리, 이진 탐색 트리를 정의하라.

기출+: 그래프의 정의는? 트리의 정의는? 트리와 그래프의 관계는?

기출+: Binary tree란? binary tree에서 각 node는 두 개의 children을 갖거나 혹은 leaf node 이거나 둘 중에 하나라고 할 때, non-leaf node와 leaf node 개수의 관계식은 어떻게 되는가?

 

Q. 트리, 이진트리의 순회방법에는 무엇이 있는가? 순회를 간단한 재귀코드로 표현해보라.

기출+: Tree traversal의 3 가지 방식을 설명하시오.

 

Q. 우선순위 큐와 힙에 대해 설명하라. 힙의 노드 추가/제거 과정을 설명해보라.

기출+: Priority queue란? Heap 이란?

 

Q. Selection Sort, Bubble Sort, Insertion Sort를 시간복잡도와 함께 말해보라.

기출+: Sorting algorithm 들에는 어떤 것들이 있는가?

 

Q. Merge Sort, Quick Sort, Heap Sort를 시간복잡도와 함께 설명하라.

기출+: Sorting algorithm 들에는 어떤 것들이 있는가?

기출+: Quick sort 에 대해 설명하시오.

기출+: Show how you can make Quicksort to have O(n lg n) worst-case running time.

 

Q. 그래프를 정의해보라. 트리 순회 면에서 DFS와 BFS를 비교하라.

기출+: 그래프의 정의는? 트리의 정의는? 트리와 그래프의 관계는?

 

Q. Dynamic Programming에 대해 설명해보라. DP를 적용하기 위해서는 어떤 요건이 필요한가?

기출+: Dynamic Programming이란?

 

Q. 오일러 사이클, 해밀턴 사이클은 무엇인가?

기출+: 오일러 사이클이란?

 

Q. 프림 알고리즘, 크루스칼 알고리즘에 대해 설명하라. 이의 시간복잡도를 말해보라.

기출+: Minimum spanning tree를 구하는 알고리즘과, 그 알고리즘의 복잡도는?

 

Q. 위상 정렬에 대해 시간복잡도와 함께 설명하라.

기출+: Topological Sorting을 설명하시오.

 

Q. 다익스트라 알고리즘, 벨만포드 알고리즘에 대해 설명하라. 이의 시간복잡도를 말해보라.

기출+: Describe Dijkstra’s algorithm and analyze its running time.

 

Q. 모든 Vertex 쌍의 최단 거리를 구할 때, DP 방법으로 해결해보라. 플로이드-워셜 알고리즘을 설명하라. 두 방법의 시간복잡도를 비교하라.

기출+: Describe Floyd-Warshall algorithm and analyze its running time.

 

Q. P, NP, NP-Hard, NP-Complete, Polynomial reduction이 무엇인지 설명하라.

기출+: NP Complete의 정의는?

 

[핵심편]

Q. 힙을 이용한 우선순위 큐의 정렬 시간복잡도를 Selection-sort, Insertion-sort와 비교하여 말해보라.

 

Q. 점근적 표기: big Theta, big O, big Omega notation에 대해 설명하라.

 

Q. 레드블랙트리/AVL트리를 설명하라. 노드가 칠해지는 법을 간단히 설명해보라. 이진 탐색 트리와 비교하여 탐색에서의 시간복잡도를 설명해보라.

 

Q. 레드 블랙 트리가 approximately balanced일 수 있는 이유를 특성과 함께 설명하라.

 

Q. B-Tree에 대해 시간복잡도와 함께 설명하고, underflow, overflow의 조건을 설명하라.

 

Q. 신장트리, 최소 신장 트리 (Minimum Spanning Tree)은 무엇인가?

 

Q. 그리디 알고리즘에 대해 설명하라. 그래프 알고리즘 중 탐욕적인 알고리즘을 말해보고, 그 이유를 설명하라.

 

Q. SAT, CLIQUE 문제에 대해 설명하라.

 

Q. 상태 공간 트리에 대해 설명하라.

 

Q. 백트래킹과 한정분기(Branch and Bound)의 차이는 무엇인가?

 

Q. Best First Search, A* 알고리즘에 대해 설명해보라. A*와 다익스트라 알고리즘의 차이는 무엇인가?

 

[응용편]

Q. 스택을 이용하여 다음 간단한 수식을 계산하려고 한다. 어떻게 계산이 수행되는지 설명하라.

14 - 3 * 2 + 7

 

Q. C++ 벡터를 Array로 구현한 버전, DoublyLinkedList로 구현한 버전이 있다고 하자. 그렇다면 두가지 버전의 (1) at(idx) (2) insertBack(), eraseBack(), (3) insertFront(), eraseFront(), (4) insert(idx) 함수의 시간복잡도를 비교하라.

 

Q. 다음 식을 이진 트리로 표현하라. 나타낸 이진트리를 다시 식으로 나타내는 알고리즘, 계산하는 알고리즘을 간단한 재귀코드로 표현해보라.

((2 * (a - 1) + (3 * b))

 

Q. Counting Sort, Radix Sort를 시간복잡도와 함께 설명하라.

 

Q. 해시 테이블에 대해 공간, 시간복잡도와 함께 설명하라.

 

Q. 해시 테이블을 사용하면서 발생하는 collision은 무엇인가? collision을 해결하기 위해 어떤 방법을 사용하는가?

 

Q. 조약돌 놓기, Matrix-Chain Multiplication, LCS 문제를 DP로 어떻게 해결하는지 간략히 설명하라. 이의 시간복잡도를 함께 설명하라.

 

Q. 회의실이 1개 있고, 여러 부서에서 회의실 사용을 요청한다고 하자. 부서에서는 요청 시 시작과 종료시간을 명시한다. 가장 많은 수의 회의를 소화하는 것이 목표라면 어떤 탐욕적인 방법이 최적의 해를 보장할 것인지 생각해보라.

 

Q. 0-1 Knapsack (or Fractional) 문제를 설명하라. DP적 해결법과 이의 시간복잡도를 설명하라.

 

Q. 문자열 매칭 시 라빈카프 알고리즘, KMP 알고리즘, 보이어 무어 알고리즘에 대해 설명하라.

 

Q. 백트래킹을 통해 미로찾기 문제, 색칠 문제(인접한 구역은 같은 색깔로 칠하지 않을 때, k개의 색으로 가능한가?) 를 해결하는 과정을 설명해보라.

 

Q. TSP 문제를 설명하고, A*, DP적 방법으로 풀어보라.