TL;DR

이 글은 2025년도 봄학기 KAIST 전산학부 대학원 면접을 준비하며, 면접 참고자료(Algorithm)에 대한 대답을 정리한 글입니다.

문제에 대한 정답이 아니며, 제가 공부하며 생각한 바들을 정리한 것입니다.

후에 같은 목표로 면접을 준비하는 학우분들께 도움이 되기를 바랍니다.

이 풀이노트는 질문만 본 상태에서 답변한 내용에 대한 채점, 그리고 이 면접을 준비하며 이전에 한번 LLM과 함께 작성해본 답안이 이어져 있습니다.

문제

Sorting

Sorting algorithm 들에는 어떤 것들이 있는가? Insertion sort, heap sort, selection sort, quick sort, merge sort 중 optimal 한 것과 optimal 하지 않은 알고리즘은? 그 이유는?

정렬 알고리즘에는 선택정렬, 버블정렬, 삽입정렬, 병합정렬, 퀵정렬 등이 있습니다. 이 중에서 최적의 알고리즘은 병합정렬과 퀵정렬입니다. 나머지 정렬 알고리즘들은 최악의 경우 시간 복잡도가 O(n^2)로, 최적의 알고리즘에 비해 성능이 떨어집니다.

Partially ordered set이란?

대칭성, 반사성, 추이성을 만족하는 관계가 정의된 집합입니다.

Quick sort 에 대해 설명하시오.

퀵정렬은 분할 정복 알고리즘의 일종으로, 다음과 같은 방식으로 동작합니다:

1. 피봇 인덱스를 선택합니다.
2. 피봇 인덱스보다 작은 값은 피봇 왼쪽으로, 큰 값은 피봇 오른쪽으로 이동시킵니다.
3. 피봇 인덱스를 기준으로 양쪽에 생긴 두개의 보조 배열에 대해 재귀적으로 퀵정렬을 수행합니다.

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

쿽정렬은 완전히 랜덤한 피봇을 선택할 경우 O(n^2)의 최악의 경우 시간 복잡도를 가집니다. 하지만 좋은 피봇을 선택하는 알고리즘을 사용하면 최악의 경우 시간 복잡도를 O(n log n)으로 줄일 수 있습니다. 이를 위해 배열의 원소를 5개씩 묶어서 그룹별 중앙값의 중앙값을 피봇으로 선택하는 방법을 사용할 수 있습니다. 이 방법은 피봇을 선택할 때 항상 중앙값에 가까운 값을 선택하게 되어, 최악의 경우 시간 복잡도를 O(n log n)으로 줄일 수 있습니다

Optimal한 정렬 알고리즘의 예를 들어보세요. 그 알고리즘의 complexity를 분석하고 optimal하다는 것을 증명해보세요.

병합 정렬을 설명해 보겠습니다. 병합 정렬은 크기가 절반인 보조 문제를 재귀적으로 풀어야하고, 보조 문제의 결과를 병합하는 과정에서 시간복잡도 O(n)이 걸립니다. 이를 식으로 표현하면 T(n) = 2T(n/2) + O(n)입니다. 이를 다양한 방법으로 해결할 수 있지만, 대표적으로 마스터 정리를 사용하여 O(n log n)으로 시간복잡도를 구할 수 있습니다.

마스터 정리에 따르면 n^(log_b(a)) = n^(log_2(2)) = n^1 = n이므로, k=1입니다. T(n) = Θ(n log n)입니다.

n개의 숫자가 array로 주어졌습니다. 이 중에 Median을 찾는 알고리즘을 설명해보세요. 설명한 알고리즘의 complexity는 무엇입니까? Median을 찾는 optimal한 알고리즘의 complexity는 무엇입니까? optimal하다는 것을 어떻게 증명할 수 있나요? Median을 찾는 알고리즘을 이용하여 n개의 숫자를 정렬해보세요. 이 정렬 알고리즘 의 complexity는 무엇입니까? 두 가지 문제를 통해 Reduction이라는 개념을 설명해 보세요

이는 select 알고리즘을 사용하여 해결할 수 있습니다. 그 복잡도는 O(n)입니다.

모범답안 select 알고리즘은 Quickselect 알고리즘을 사용하여 구현할 수 있습니다. Quickselect 알고리즘은 QuickSort와 유사한 방식으로 동작하지만, 전체 배열을 정렬하지 않고, 원하는 k번째 원소만 찾는 데 초점을 맞춥니다.

1. 피봇을 선택합니다.
2. 피봇을 기준으로 배열을 분할합니다.
3. 피봇의 인덱스가 k와 같으면 피봇을 반환합니다.
4. 피봇의 인덱스가 k보다 작으면 오른쪽 부분에서 k번째 원소를 찾습니다.
5. 피봇의 인덱스이 k보다 크면 왼쪽 부분에서 k번째 원소를 찾습니다. 이 알고리즘의 시간 복잡도는 평균적으로 O(n)입니다. 최악의 경우 O(n^2)이지만, 피봇을 잘 선택하면 O(n)으로 줄일 수 있습니다.

Dynamic Programming

Dynamic Programming이란?

동적 프로그래밍은 큰 문제를 풀기 위해 작은 문제를 해결하고, 그 결과를 저장하여 중복 계산을 피하는 알고리즘 설계 기법입니다. 동적 프로그래밍은 다음과 같은 두 가지 주요 특징을 가지고 있습니다:

1. 최적 부분 구조(Optimal Substructure): 큰 문제의 최적 해가 작은 문제의 최적 해로 구성될 수 있습니다. 즉, 큰 문제를 해결하기 위해 작은 문제를 해결하는 방식으로 접근할 수 있습니다.
2. 중복 부분 문제(Overlapping Subproblems): 큰 문제를 해결하기 위해 동일한 작은 문제를 여러 번 해결해야 하는 경우가 많습니다. 동적 프로그래밍은 이러한 중복 계산을 피하기 위해 작은 문제의 결과를 저장하고 재사용합니다.

Dynamic programming과 Greedy algorithm에 대하여 각각이 무엇인지 설명하고, 공통점과 차이점을 이야기하세요. 구체적으로 Dynamic programming으로 풀 수 있는데 Greedy algorithm으로는 풀 수 없는 문제의 예를 들어보세요. 그 문제가 dynamic programming으로 풀 수 있다는 것을 증명해보세요.

동적 프로그래밍(Dynamic Programming)은 최적 부분 구조와 중복 부분 문제를 이용하여 문제를 해결하는 알고리즘 설계 기법입니다. 그리디 알고리즘와 유사한 점은 부분 문제를 해결하여 전체 문제를 해결한다는 점입니다. 하지만 그리디 알고리즘은 항상 최적의 해를 보장하지 않는 반면, 동적 프로그래밍은 최적의 해를 보장합니다.

예로는 배낭 문제가 있습니다.

Graph Algorithm

그래프의 정의는? 트리의 정의는? 트리와 그래프의 관계는?

그래프는 정점과 간선의 집합으로 정의됩니다. 간선은 정점간의 연결을 나타냅니다. 트리는 사이클이 없는 fully-connected 그래프입니다. 사이클은 서로 다른 간선으로 연결된 정점들이 다시 원래의 정점으로 돌아오는 경로를 의미합니다.

Topological Sorting을 설명하시오

위상 정렬은 방향 그래프에서 정점들을 순서대로 나열하는 방법입니다.

오일러 사이클이란?

오일러 사이클은 그래프의 모든 간선을 정확히 한 번씩 방문하고, 시작 정점으로 돌아오는 경로를 의미합니다. 오일러 사이클이 존재하기 위한 조건은 다음과 같습니다:

1. 그래프가 연결되어 있어야 합니다. 즉, 모든 정점이 서로 연결되어 있어야 합니다.
2. 모든 정점의 차수가 짝수여야 합니다. 즉, 모든 정점에 연결된 간선의 개수가 짝수여야 합니다. 오일러 사이클이 존재하는 그래프는 오일러 그래프라고 합니다 오일러 사이클을 찾는 알고리즘으로는 Hierholzer’s algorithm이 있습니다.

Tree traversal의 3 가지 방식을 설명하시오

전위, 중위, 후위 순회 방식이 있습니다. 전위 순회는 root -> left -> right 순서로 방문하는 방식입니다. 중위 순회는 left -> root -> right 순서로 방문하는 방식입니다. 후위 순회는 left -> right -> root 순서로 방문하는 방식입니다.

Transitive closure란?

한 정점에서 다른 정점에 도달 가능한지 여부를 나타내는 행렬입니다. 즉, 그래프의 모든 정점 쌍에 대해, 한 정점에서 다른 정점으로의 경로가 존재하는지를 나타냅니다. 전이 폐쇄는 그래프의 모든 정점 쌍에 대해, 경로가 존재하는지 여부를 나타내는 행렬로 표현됩니다.

Finite state automata란?

유한 상태 기계(Finite State Automata, FSA)는 유한한 개수의 상태와 상태 전이 규칙으로 구성된 계산 모델입니다. FSA는 입력 문자열을 읽어들이면서 상태를 전이하고, 최종 상태에 도달하면 입력 문자열이 해당 언어에 속한다고 판단합니다.

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

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조입니다. 만약 각 노드가 두 자식을 노드 가지거나 리프 노드일 경우, 리프노드의 개수는 비리프 노드의 개수에 1을 더한 값과 같습니다. 베이스 조건은 루트 노드가 리프 노드인 경우 비리프 노드 0개에 리프 노드 1개가 됩니다. 재귀적으로 특정 리프 노드에 자식을 2개 추가하면 비리프 노드가 1개 증가하고 리프 노드가 1개 증가합니다. 따라서 loop invariant는 비리프 노드의 개수 + 1 = 리프 노드의 개수입니다.

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

MST 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있습니다. 크루스칼 알고리즘은 간선을 정렬해야해서 O(E log E) 시간 복잡도를 가지며, E는 간선의 개수입니다. 프림 알고리즘은 우선순위 큐에서 간선을 선택하는 방식으로 O(E log V) 시간 복잡도를 가지며, V는 정점의 개수입니다.

T가 그래프 G의 minimum spanning tree라고 하자. G에 있는 임의의 두 정점 s와 t에 대해, G에서 s와 t 사이의 최단 경로가 반드시 T에 포함되는가?

그렇지 않습니다. MST는 그래프의 모든 정점을 포함하면서 간선의 가중치 합이 최소가 되는 트리입니다. 따라서 MST에 포함된 간선이 반드시 s와 t 사이의 최단 경로를 포함하지는 않습니다. 예를 들어 a와 b 사이의 최단 경로가 가중치 2인 간선이고, a-c-d-b 사이의 경로가 가중치 3인 간선으로 구성되어 있다면, MST는 a-c-d-b를 포함하지 않을 수 있습니다.

Dijkstra’s algorithm을 설명하고 시간 복잡도를 분석하라.

다익스트라 알고리즘은 그래프에서 두 정점간의 최단 거리를 찾는 알고리즘입니다. 먼저, 모든 정점간의 거리 테이블을 관리해야하고 전부 무한대로 초기화합니다. 그리고 시작 정점의 거리를 0으로 초기화합니다. 시작 정점으로부터 인접 노드를 순회하면서 최단거리를 갱신합니다. 그리고, 해당 노드들 중에서 최단 거리가 가장 짧은 노드를 선택하여 방문합니다. 이 노드에서 앞 과정을 반복합니다. 예를 들어 a노드가 시작점이고 다음 노드가 b일때, a-b 와 b-c의 합이 a-c보다 작다면 a-c의 거리를 갱신합니다. 이 과정을 모든 노드를 방문할 때까지 반복합니다. 시간 복잡도는 O(E log V + VlogV)입니다. E는 간선의 개수, V는 정점의 개수입니다. 알고리즘 과정에서 모든 간선을 한번씩 방문하고, 우선순위 큐에서 정점을 선택하는 과정이 log V의 시간 복잡도를 가지기 때문입니다.

Floyd-Warshall algorithm을 설명하고 시간 복잡도를 분석하라.

플로이드-워셜 알고리즘은 그래프의 모든 정점 쌍 간의 최단 거리를 찾는 알고리즘입니다. 먼저, 모든 정점 간의 거리 테이블을 관리해야하고 전부 무한대로 초기화합니다. 그리고, 각 정점 간의 직접 연결된 간선의 가중치를 초기화합니다. 그 다음, 모든 정점 k에 대해, 각 정점 i와 j에 대해, i에서 j로 가는 최단 거리가 i에서 k를 거쳐 j로 가는 최단 거리보다 작으면 갱신합니다. 즉, i에서 j로 가는 최단 거리를 i에서 k를 거쳐 j로 가는 최단 거리가 더 짧은 경우, 최단 거리를 갱신합니다. 이 과정을 모든 정점에 대해 반복합니다. 시간 복잡도는 O(V^3)입니다.

Advanced data structures

Priority queue란? Heap이란?

우선순위 큐란 원소의 우선순위를 기준으로 원소를 pop하는 자료구조입니다. 주로 힙을 이용하여 구현하곤 합니다. 힙은 이진 트리의 일종으로, 부모 노드가 자식 노드보다 항상 크거나 작은 값을 가지는 특성을 가지고 있습니다. 힙의 Push 연산은 O(log n) 시간 복잡도를 가지며, Pop 연산도 O(log n) 시간 복잡도를 가집니다.

Complexity Theorem

NP Complete의 정의는?

NP-완전(NP-Complete)은 결정 문제의 복잡도 클래스 중 하나로, 다음과 같은 두 가지 조건을 만족하는 문제를 의미합니다:

1. NP에 속함: 문제의 해답을 다항 시간 안에 검증할 수 있어야 합니다. 즉, 주어진 입력에 대해 해답이 올바른지 확인하는 과정이 다항 시간 내에 수행될 수 있어야 합니다.
2. NP-완전 문제로의 다항 시간 환원 가능성: 문제가 NP-완전 문제로 환원될 수 있어야 합니다. 즉, 다른 NP-완전 문제로부터 다항 시간 내에 변환할 수 있어야 합니다. 예를 들어 SAT(논리식의 만족성 문제)는 NP-완전 문제입니다. 다른 문제가 np 완전한지 보이는 대표적인 방법으로 SAT 문제로 환원하는 방법이 있습니다.