[CS 면접] 자료구조 및 알고리즘 - 2

보초님의 github에 있는 질문들을 보며 답변을 달아본 것입니다.

문제사항, 잘못된점 혹은 궁금한점이 있다면 댓글로 남겨주시면 감사하겠습니다.

이전 글을 읽지 않았다면 먼저 읽어보시면 좋습니다.

→ 보러가기

[CS 면접] 자료구조 및 알고리즘 - 1

 

BBST(Balnced Binary Search Tree)와 그 종류에 대해 설명해 주세요.

BBST 는 이진탐색트리가 편향되는 단점을 없애기 위해 만들어진 트리로 AVL, Red-Black Tree 등이 있습니다. 해당 트리들은 한쪽으로 편향되기 시작하면 자동으로 재정렬하여 편향을 없애주는 기능을 갖고 있습니다.

Red-Black Tree는 어떻게 균형을 유지할 수 있을까요?

RB Tree는 일정한 규칙들을 가지고 균형을 유지하게 됩니다. 이런 RB Tree의 규칙이 깨지게 된다면 Restructuring, 과 Recoloring 연산을 통해 트리의 균형을 재조정하게 됩니다. 새로운 노드를 삽입하면 빨강색을 가지게 됩니다. 만약 부모와 삼촌(부모의 형제)노드가 모두 빨강색이라면 색을 재조정하는 Recoloring, 부모는 빨강, 삼촌은 검정이라면 트리를 회전시키는 Restructuring이 발생하게 됩니다. 만약 재조정 후에도 규칙이 위반된다면 위반되는 규칙이 없을 때까지 재조정을 반복하게 됩니다.

Red Black Tree의 주요 성질 4가지에 대해 설명해 주세요.

1. 루트노드 는 검정색이다.
2. 빨강노드의 자녀는 검정색이다.
3. 모든 리프노드는 검정색이다.
4. 루트노드부터 빨강노드까지의 검정색노드의 개수는 모두 똑같다.

2-3-4 Tree, AVL Tree 등의 다른 BBST 가 있음에도, 왜 Red Black Tree가 많이 사용될까요?

1. 단순성 : 다른 트리에 비해 구현이 간단하다.
2. 성능 : 삽입, 삭제, 탐색 모두 최악의 경우 O(logN)의 성능을 가지지만 일반적으로 다른 트리보다 더 빠른 성능을 가지고 있다.
3. 유연성 : 모든 종류의 데이터를 저장하는데 사용할 수 있다.
4. 가용성 : 많은 프로그래밍 언어 표준 라이브러리에 RB Tree에 대한 기본제공을 지원합니다.

정렬 알고리즘에 대해 설명해 주세요.

정렬 알고리즘은 자료를 오름차순 혹은 내림차순으로 정렬하기 위해 사용되는 알고리즘입니다. 그 종류로는 Bubble Sort, Quick Sort, Merge Sort, Heap Sort, Insertion Sort 등이 있습니다.

Quick Sort와 Merge Sort를 비교해 주세요.

Quick Sort는 임의의 피벗을 정해 피벗보다 작은 요소는 왼쪽으로 피벗보다 큰 요소는 오른쪽으로 정렬합니다. 이 후 피벗 왼쪽 리스트와 오른쪽 리스트에 대해 모두 정렬될 때 까지 동일한 작업을 반복합니다. Divide -conquer 방법이며 unstable 한 정렬 방법입니다.

Merge Sort는 리스트를 반으로 나누고 정렬하기를 반복하며 정렬하는 방식입니다. divide-conquer 방식이며 stable 한 정렬방법입니다.

퀵정렬은 최악의 경우 O(N^2)의 시간복잡도를 가지지만 병합청렬은 O(NlogN)을 가진다. 하지만, 일반적으로는 퀵정렬이 더빠르다.

Quick Sort에서 O(N^2)이 걸리는 예시를 들고, 이를 개선할 수 있는 방법에 대해 설명해 주세요.

이미 정렬된 데이터 혹은 거의 정렬된 데이터의 경우 O(N^2)의 시간복잡도를 가지게 된다. 이를 개선하기 위해서는 피봇 선택을 랜덤하게 선택하거나 일정 크기 이하로 분할되었을 때는 삽입정렬을 수행해 성능을 개선시킬 수 있습니다.

→삽입정렬은 인플레이스 정렬, 크기가 작은 배열에서는 매우 효율이 좋기 때문입니다.

혹은 배역의 가장 왼쪽, 오른쪽, 중간 값을 이용하여 개선시킬 수 있는 방법이 있습니다.

→ 배월의 가장 왼쪽, 오른쪽, 중간 값을 오름차순으로 정렬한 후 중간 값을 가장 오른쪽 앞의 값과 위치를 바꾼다. 이후 나머지 값들에 대해 퀵정렬을 수행하면 재귀의 깊이를 줄일 수 있어 속도를 개선할 수 있다.

Stable Sort가 무엇이고, 어떤 정렬 알고리즘이 Stable 한지 설명해 주세요.

Stable Sort는 동일한 값에 대해 순서가 유지되는 정렬을 Stable Sort라고 말합니다. 그 예시로는 Merge Sort, Insertion Sort, Bubble Sort, Counting Sort 등이 있습니다.

Merge Sort를 재귀를 사용하지 않고 구현할 수 있을까요?

네 가능합니다. 반복문을 통해서 bottom-up 방식을 통해 구현이 가능합니다.

Radix Sort에 대해 설명해 주세요.

Radix Sort는 자리를 비교하여 정렬을 수행하는 알고리즘 입니다. 각 자리수에 대해 Counting Sort 와 같은 안정정렬 알고리즘을 통해 정렬을 진행합니다. 앞에서부터 비교하는 방식인 MSD와 뒤자리부터 비교하는 방식인 LSD가 있는데 MSD는 요소를 그룹화해서 정렬해야 한다는 단점이 있어 LSD가 주로 사용됩니다.

시간복잡도는 O(d*(k + n)) 으로 d: 자리수 n : 데이터 개수, k : 각 자리에 들어갈 수 있는 가능한 가지수(Ex 10진수 : 10가지)로 일반적으로 d는 상수, k = O(N) 이므로 O(N)의 시간복잡도를 가지게 됩니다.

d 와 k를 변경해 자리수가 큰 데이터에 대해서 더 빠르게 동작할 수 있도록 변경 가능합니다.

Bubble, Selection, Insertion Sort의 속도를 비교해 주세요.

	best	average	worst
Bubble	O(N)	O(N^2)	O(N^2)
Selection	O(N^2)	O(N^2)	O(N^2)
Insertion	O(N)	O(N^2)	O(N^2)

일반적으로 크기가 작은 배열에 대해서는 Insertion Sort가 성능이 제일 좋습니다. 크기가 커질수록 Bubble Sort, Insertion Sort의 성능이 더 좋아집니다.

값이 거의 정렬되어 있거나, 아예 정렬되어 있다면, 위 세 알고리즘의 성능 비교 결과는 달라질까요?

정렬이 되어있는 경우 삽입정렬은 O(N)에 가까운 시간복잡도를 가질 수 있으므로 더 빨라집니다.

사용하는 언어에서 사용하는 정렬 알고리즘?

Java :sort() 에서는 Dual-Pivot Quick Sort 를 통한 정렬을 객체정렬에서는 Tim Sort를 통해서 정렬을 진행합니다.

Python: 역시 Tim Sort를 기본으로 채택해서 사용하고 있다.

정렬해야 하는 데이터는 50G 인데, 메모리가 4G라면, 어떤 방식으로 정렬을 진행할 수 있을까요?

외부병합정렬을 이용하면 됩니다.

1. 메모리에 들어갈 수 있는 양만큼 데이터를 읽어 정렬알고리즘을 이용해 정렬한다.
2. 디스크에 정렬된 청크에서 첫번째 블록을 메모리로 읽고 정렬된 단일블록으로 병합해 디스크에 저장합니다.
3. 모든 청크가 병합될때까지 반복합니다.
4. 이렇게 정렬된 청크를 단일 출력 파일로 병합합니다.

그래프 자료구조에 대해 설명하고, 이를 구현할 수 있는 두 방법에 대해 설명해 주세요.

그래프는 노드와 간선으로 이루어진 자료구조입니다. 이를 구현하는 방법으로는 인접리스트 방식과 인접행렬 방식이 있습니다.

• 각 방법에 대해, "두 정점이 연결되었는지" 확인하는 시간복잡도와 "한 정점에 연결된 모든 정점을 찾는" 시간복잡도, 그리고 공간복잡도를 비교해 주세요.한 정점에 연결된 모든 정점을 찾는 시간 복잡도는 인접리스트는 O(E)가 걸리고 인접행렬의 경우는 O(V)가 걸리게 됩니다. 공간복잡도는 인접리스트의 경우 O(V+E) N은 노드의 개수 M은 간선의 개수 지만 인접행렬의 경우는 O(V^2)를 가지게 됩니다.
• 두 정점이 연결되었는지 확인하는 시간복잡도는 인접리스트 같은 경우는 최악의 경우 O(V)이 걸리지만 인접행렬 방식은 O(1)이 걸립니다.
• 정점의 개수가 N개, 간선의 개수가 N^3 개라면 어떤 방식으로 구현하는 것이 효율적일까요?
• 간선의 개수가 정점의 개수보다 많기 때문에 인접행렬 방식으로 구현하는 것이 효율적입니다.
• 사이클이 없는 그래프는 모두 트리인가요? 그렇지 않다면, 예시를 들어주세요.
• 아닙니다. 트리는 DAG 로 Directed Acyclic Graph 입니다. 따라서 방향성이 없는 그래프는 트리가 될 수 없습니다.

그래프에서, 최단거리를 구하는 방법에 대해 설명해 주세요.

최단거리를 찾기 위해서는 DFS, BFS 등의 방법이 있습니다. DFS 는 깊이 우선 탐색, BFS는 넓이 우선 탑색입니다. 또한 가중치가 있다면 다익스트라나 Bellman-ford, floyd-warshall 알고리즘과 같은 방법등을 사용할 수 있습니다.

트리에서 어떤 방식으로 최단거리를 구할 수 있을까요? (위 방법을 사용하지 않고)

BFS와 같은 방법을 이용하거나 LCA 와 같은 알고리즘을 사용할 수 있습니다.

다익스트라 알고리즘에서, 힙을 사용하지 않고 구현한다면 시간복잡도가 어떻게 변화할까요?

힙을 사용해서 구현한다면 O(E + VlogV)의 시간복잡도를 가지게 되지만 힙을 사용하지 않는다면 순차적으로 모든 경우를 탐색해야 하므로 O(V^2)의 시간복잡도를 가지게 됩니다.

정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 알고리즘이 효율적일까요?

Floyd-Warshall 알고리즘이 효울적입니다. 왜냐하면 Floyd-Warshall의 시간 복잡도는 O(V^3)로 간선의 개수의 영향을 받지 않게 되기 때문입니다.

A* 알고리즘에 대해 설명해 주세요. 이 알고리즘은 다익스트라와 비교해서 어떤 성능을 낼까요?

A* 알고리즘은 그래프에서 최단경로를 찾는데 사용되는 휴리스틱 검색 알고리즘입니다. 시작노드에서 노드에서 도달하는 실제 비용과 목표 노드에 도달하기 위한 남은 비용 추정치를 결합하는 비용 함수를 휴리스틱하게 설정하여 이용합니다. 이 때 결합비용이 가장 낮은 노드를 선택하고 이웃 비용을 업데이트 합니다. 다익스트라에 비해 잘 정의된 문제에 대해서 더효율적인 알고리즘이지만 휴리스틱함수의 품질에 크게 좌우됩니다.

음수 간선이 있을 때와, 음수 사이클이 있을 때 각각 어떤 최단거리 알고리즘을 사용해야 하는지 설명해 주세요.

음수 간선이 있거나 음수 사이클이 있을 때는 Bellman-ford 알고리즘을 사용할 수 있습니다. 음수 사이클이 있는 경우에는 Floyd-Warshall 알고리즘도 사용할 수 있습니다. 하지만 음수 사이클을 감지할 수 있지만 최단거리를 구할 수 는 없습니다.

재귀함수에 대해 설명해 주세요

재귀함수는 자기 자신을 반복적으로 호출하는 함수를 의미합니다. 문제를 더 작은 문제로 분해하여 문제를 해결하는 기법입니다. 종료조건과 기본케이스 처리를 잘 설정해서 함수가 무한호출되어 스택 오버플로 오류가 발생되지 않도록 해야합니다.

재귀함수의 동작 과정을 Call Stack을 활용해서 설명해 주세요.

함수를 호출하면 해당 함수가 활용할 수 있는 Stack 공간이 할당됩니다. 이 함수가 내부에서 재귀적으로 자기자신을 호출하게 되면 또 새로운 Stack 공간이 할당되고 지역변수들이 새로 할당되게 됩니다. 호출마다 새로운 공간이 할당되어 지역변수들의 중복없이 함수가 동작할 수 있게되고 이를 통해 함수를 재귀적으로 구성할 수 있게됩니다. 종료조건이 도달했을 때 Call Stack들이 차례대로 해제되며 현재 결과를 이전 Stack으로 전달해 최종 결과를 얻을 수 있게 됩니다.

언어의 스펙에 따라, 재귀함수의 최적화를 진행해주는 경우가 있습니다. 어떤 경우에 재귀함수의 최적화가 가능하며, 이를 어떻게 최적화 할 수 있을지 설명해 주세요.

Tail Recursion : 마지막으로 호출되는 함수가 최종 결과값을 도출해 더이상 계산을 수행하지 않도록 최적화할 수 있습니다. 이렇게 해서 메모리 오버헤드를 크게 줄일 수 있습니다.

memoization : 중간 결과값들에 대해 캐싱하여 동일한 계산을 여러번 수행하는 재귀함수를 최적화하는데 사용할 수 있습니다.

MST가 무엇이고, 어떻게 구할 수 있을지 설명해 주세요.

Minimum cost Spanning Tree의 약자로 n개의 vertex가 n-1 개의 엣지로 모두 연결되어 있고 사이클이 없는 그래프를 Spanning Tree 라고 합니다. 이 때 가중치의 합이 최소가 되는 Spanning Tree를 MST 라고합니다. Kruskal, Prim 등의 알고리즘을 사용해서 구할 수 있습니다.

Kruskal 알고리즘에서 사용하는 Union-Find 에 대해 설명해 주세요.

Union-Find는 Union 과 Find 함수로 이루어져 disjoint-set을 표현하는 자료구조로 union 함수를 통해 집합을 합치고 Find 함수를 통해 노드가 속한 집합을 찾습니다. 이때 find는 해당 노드가 속한 최상위 노드를 반환합니다. 이런 작업을 통해 두 개의 노드가 같은 그래프에 속해 있는지 판단할 수 있습니다.

Kruskal과 Prim 중 어떤 것이 더 빠를까요?

Kruskal : O(ElogE), Prim : O(VlogV) + O(ElogV) ≤ O(ElogV)

따라서 간선이 많다면 Prim 간선이 적다면 Kruskal이 더 빠르게 동작합니다.

 

---

출처

• vsfe github - tech interview