[CS 면접 질문] 자료구조
시간 복잡도와 공간 복잡도
시간 복잡도는 입력 크기에 대한 알고리즘의 실행 시간을 나타내는 것이고, 공간 복잡도는 입력 크기에 대한 알고리즘 실행에 필요한 메모리 사용량을 나타내는 것이다. 일반적으로 최악의 경우를 기준으로 하는 빅오(big-O) 표기법을 사용한다.
배열(Array) vs 연결리스트(LinkedList)
배열(Array)
데이터가 순차적으로 저장되는 정적 자료구조이다. index를 사용해 특정 원소에 접근할 수 있기 때문에 찾고자 하는 원소의 인덱스를 알 경우 O(1)에 접근할 수 있다. 하지만 삽입, 삭제시 원소들을 shift 해야하는 비용이 발생하기 때문에 O(n)의 시간 복잡도를 가지는 단점이 있다.
Array vs ArrayList
Array는 크기가 고정적이고, ArrayList는 가변적이다. Array는 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르고, ArrayList는 데이터 추가, 삭제 시 메모리를 재할당하기 때문에 Array보다 느리다.
연결리스트(LinkedList)
배열의 삽입, 삭제 문제를 해결하기 위한 자료구조로, 크기가 정해져 있지 않은 동적 자료구조이다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있고, 이 부분만 다른 값으로 바꿔주면 삽입과 삭제를 O(1)로 해결할 수 있다. 하지만 원하는 위치에 한 번에 접근할 수 없다는 단점이 있다. 특정 데이터를 검색하려면 첫 번째 노드부터 하나씩 확인해야 하기 때문에 O(n) 시간 복잡도를 갖는다.
스택(Stack)
선형 자료구조의 하나로, 마지막에 들어간 원소가 먼저 나오는(LIFO, Last In First Out) 자료구조이다. 실행 취소(Ctrl+Z 등)와 같은 작업에 사용된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Stack {
int size;
Object[] stack;
int top = -1;
public Stack(int size) {
this.size = size;
stack = new Object[size];
}
public void push(Object item) throws Exception {
if (isFull()) {
throw new Exception("스택이 가득참");
}
stack[++top] = item;
}
public Object pop() throws Exception {
if (isEmpty()) {
throw new Exception("스택이 비었음");
}
return stack[top--];
}
public Object peek() throws Exception {
if (isEmpty()) {
throw new Exception("스택이 비었음");
}
return stack[top];
}
public boolean isFull() {
return top == size-1;
}
public boolean isEmpty() {
return top == -1;
}
}
연결리스트로 스택 만들기
1
2
3
4
5
6
7
8
9
public class Node {
Object data;
Node next;
public Node(Object data) {
this.data = data;
this.next = null;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class ListStack {
Node top;
public void push(Object item) {
Node newNode = new Node(item);
newNode.next = top;
top = newNode;
}
public Objcet pop() throws Exception {
if (isEmpty()) {
throw new Exception("스택이 비었음");
}
Object item = top.data;
top = top.next;
return item;
}
public Object peek() throws Exception {
if (isEmpty()) {
throw new Exception("스택이 비었음");
}
return top.data;
}
public boolean isEmpty() {
return top == null;
}
}
큐(Queue)
선형 자료구조의 하나로, 먼저 들어간 원소가 먼저(FIFO, First In First Out) 나오는 구조이다. 프로세스 스케줄링시 사용할 수 있다.
1
2
3
4
5
6
7
8
public class Node {
Object data;
Node next;
public Node(Object data) {
this.data = data;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Queue {
Node first;
Node last;
public void enqueue(Object item) {
Node newNode = new Node(item);
if (last != null) {
last.next = newNode;
}
last = newNode;
if (isEmpty()) {
first = newNode;
}
}
public Object dequeue() throws Exception {
if (isEmpty()) {
throw new Exception("큐가 비었음");
}
Object item = first.data;
first = first.next;
if (first == null) {
last = null;
}
return item;
}
public Object peek() throws Exception {
if (isEmpty()) {
throw new Exception("큐가 비었음");
}
return first.data;
}
public boolean isEmpty() {
return first == null;
}
}
스택 2개로 큐 만들기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class StackQueue {
Stack newStack, oldStack;
public StackQueue() {
newStack = new Stack();
oldStack = new Stack();
}
public void enqueue(Object item) {
oldStack.push(item);
}
public Object dequeue() {
Object item = null;
if (newStack.isEmpty()) {
while(!oldStack.isEmpty()) {
newStack.push(oldStack.pop());
}
item = newStack.pop();
}
if (!newStack.isEmpty()) {
while(!newStack.isEmpty()) {
oldStack.push(newStack.pop());
}
}
return item;
}
}
이진 탐색 트리(BST)
이진 탐색과 연결 리스트를 결합한 자료구조로, 효율적인 탐색과 빈번한 삽입, 삭제가 가능하다는 장점이 있다. 왼쪽 서브 트리의 값들은 부모 노드보다 작고 오른쪽 서브 트리의 값들은 부모 노드보다 크다는 특징이 있다. 검색시 균형이 잡힌 트리일 경우 O(logN)의 시간 복잡도를 가진다. 그러나 한쪽으로 치우친 불균형 트리일 경우 O(n)의 시간 복잡도를 가지는데, 이러한 문제를 해결하기 위한 방식으로 balanced BST인 레드-블랙 트리와 AVL 트리가 있다.
레드-블랙 트리(RBT)
레드-블랙 트리(Red-Black Tree)는 노드가 검은색 또는 빨간색인 트리로, 정해진 규칙을 만족하며 균형을 유지하는 이진 탐색 트리이다. 삽입, 삭제 연산 과정에서 조건에 따라 회전과 색 변환을 통해 노드를 재배치하며 균형을 유지한다.
레드-블랙 트리의 속성
- 모든 노드는 검은색 또는 빨간색이다.
- 루트 노드는 검은색이다.
- 모든 단말 노드(NIL)는 검은색이다. (단말 노드는 트리의 끝을 나타내며 값을 갖지 않는다.)
- 빨간색의 자식 노드는 모두 검은색이다. 빨간색 노드는 연속으로 나올 수 없다.
- 루트에서 임의의 단말 노드로 가는 경로에 있는 검은색 노드 개수는 모두 동일하다.
AVL 트리
AVL 트리는 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이를 통해 균형을 유지하는 트리이다. 불균형 상황에 따라 왼쪽 또는 오른쪽 회전을 수행한다.
왜 RB 트리를 사용할까?
AVL 트리는 엄격한 균형을 이루기 때문에 빠른 검색에 유리하지만 잦은 회전이 발생할 수 있다. RB 트리는 색깔만 바꾸는 등의 방식으로 느슨한 균형을 이루기 때문에 상대적으로 회전이 적게 발생한다. 즉 RB 트리가 삽입, 삭제시 더 유리한 것이다. Java의 TreeMap, TreeSet도 RB 트리로 구현되었으며 HashMap의 해시 충돌 전략으로도 사용된다.
주어진 트리가 BST인지 확인하는 법
이진 탐색 트리라는 것은 ‘왼쪽 서브트리의 최댓값이 현재 노드보다 작거나 같고, 오른쪽 서브트리의 최솟값이 현재 노드보다 크다’는 조건을 만족해야 한다.
이는 현재 노드를 기준으로 왼쪽, 오른쪽 서브트리를 탐색할 때 각 서브트리의 노드들이 현재까지의 최솟값 ~ 최댓값 범위 내에 있는지 확인하여 검증할 수 있다. 즉, 최솟값과 최댓값을 아래로 전달해가면서 좁은 범위에 대한 검증을 반복하는 것이다. 이는 재귀적으로 구현할 수 있다.
+) 설명을 덧붙이자면, 트리를 훑어나갈 때 왼쪽으로 분기하면 max 값을 갱신하고, 오른쪽으로 분기하면 min 값을 갱신해 나가는 것이다. 처음 루트에서 시작할 땐 (min = NULL, max = NULL)에서 시작(루트 노드에서는 최댓값과 최솟값이 없음)한다. 만약 루트 노드가 20이라면 왼쪽 노드들은 (min = NULL, max = 20) 범위 안에, 오른쪽 노드들은 (min = 20, max = NULL) 범위 안에 있어야 한다. 범위를 벗어나는 노드가 있다면 즉시 트리 순회를 중단한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
boolean checkBST(TreeNode n) {
return checkBST(n, null, null);
}
boolean checkBST(TreeNode n, Integer min, Integer max) {
if (n == null) {
return true;
}
if ((min != null && n.data <= min) || (max != null && n.data > max)) {
return false;
}
if (!checkBST(n.left, min, n.data) || !checkBST(n.right, n.data, max)) {
return false;
}
return true;
}
우선순위 큐(Priority Queue)
우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터부터 꺼내는 자료구조이다. 일반적으로 가장 효율적인 힙을 사용해 구현하며 삽입, 삭제 연산시 O(logN)의 시간 복잡도를 갖는다.
힙(Heap)
완전 이진 트리1로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조이다. 최대 힙과 최소 힙 두 종류가 있다. 원소의 삽입, 삭제시 heapify 과정이 필요하기 때문에 O(logN)의 시간복잡도를 갖게 된다.
힙 구현
힙은 완전 이진 트리이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다. index를 통해 특정 원소에 random access가 가능하기 때문이다. (좀 더 넓은 의미로, 힙의 구현을 위해서는 index를 이용해 접근 가능한 자료구조로 구현해야 한다. java의 경우 ArrayList를 사용할 수 있다.)
0번째 인덱스는 계산의 편의를 위해 사용하지 않는다. 부모노드의 인덱스가 1이 된다. 부모와 자식 간의 인덱스 관계는 부모가 인덱스가 N일 때 왼쪽 자식은 2N, 오른쪽 자식은 2N+1이 된다.
삽입 연산은 가장 마지막 인덱스에 원소를 추가하고, 부모 노드와 비교를 반복하며 heapify를 수행한다. 삭제 연산은 루트 노드를 삭제하고 맨 마지막 노드를 루트 노드로 대체한다. 이후 heapify를 수행한다.
최소 힙
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class MinHeap {
ArrayList<Integer> heap;
public MinHeap() {
heap = new ArrayList<Integer>();
heap.add(0);
}
public void push(int item) {
heap.add(item);
int n = heap.size()-1;
while (n > 1 && heap.get(n/2) > heap.get(n)) {
int tmp = heap.get(n/2);
heap.set(n/2, item);
heap.set(n, tmp);
n /= 2;
}
}
public int pop() {
if (heap.isEmpty()) {
return 0;
}
int item = heap.get(1);
heap.set(1, heap.get(heap.size()-1));
heap.remove(heap.get(heap.size()-1);
int n = 1;
while (true) {
int left = n*2;
int right = n*2+1;
if (left >= heap.size()) break;
int min = heap.get(left);
int minIdx = left;
if ((right < heap.size()) && heap.get(right) < min) {
min = heap.get(right);
minIdx = right;
}
if (min > heap.get(n)) break
int tmp = heap.get(n);
heap.set(n, min);
heap.set(minIdx, tmp);
n = minIdx;
}
return item;
}
}
해시테이블(Hash Table)
해시테이블은 (Key, Value)로 데이터를 저장하는 형태의 자료구조로 빠르게 데이터를 검색할 수 있다. Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으며 평균 O(1)의 시간 복잡도로 데이터를 조회한다. 하지만 해시 충돌이 발생할 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(N)까지 증가할 수 있다.
해시 충돌 해결 방법
체이닝 (chaining)
같은 해시가 나오는 키 값들을 연결 리스트에 저장하는 방식. 동일한 해시에 chaining되는 데이터가 많아질 경우 효율성이 떨어지는 단점이 있다.개방 주소법 (open addressing)
해당 해시가 아닌 다른 주소에 데이터를 저장하는 방식으로, 데이터를 저장할 다른 장소를 찾는다. 개방 주소법을 구현하는 방법으로 선형 조사법, 이차 조사법, 이중 해싱이 있다.- 선형 조사법 : 인덱스 n에서 충돌이 발생했다면 n+1, n+2 … 와 같이 다음 인덱스로 이동하면서 빈 공간을 찾는 방식이다.
- 이차 조사법 : 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고, 그 다음 충돌부터 2^2, 3^2 … 만큼 이동한다.
- 이중 해싱 : 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다.
참고 자료
Interview_Question_for_Beginner
신입 개발자 기술면접 질문 정리 - 자료구조
Notes
완전 이진 트리 : 트리의 마지막 레벨을 제외한 나머지 레벨에 모든 노드가 채워진 트리. 마지막 레벨은 왼쪽에서부터 오른쪽으로 노드가 채워져 있다. ↩︎