Data Structure

Q0. 배열(array)에 대해서 설명하시오

고정된 크기를 갖고 순서대로 번호가 붙은 같은 자료형의 원소들이 연속적인 형태로 구성된 자료구조입니다. 이때 각 원소에 붙은 번호를 흔히 인덱스(index)라고 부릅니다. 원소들이 연속적으로 메모리에 배치되어있기 때문에 임의의 첨자를 통해 원소의 값을 알아내는데 시간 복잡도가 O(1)입니다. 따라서 임의 접근이 가능한 자료구조에 속합니다.

임의의 첨자를 통해 원소의 값을 도출하거나 해당 위치에 새로운 원소를 대입하는 연산은 시간복잡도가 O(1)로 매우 빠르나, 새로운 원소를 삽입하거나 삭제하는 경우 배열의 크기를 조정하여 이전 원소들을 복사해야하는 연산이 실행되기 때문에 시간 복잡도가 O(n)으로 느립니다.

Q1. 배열 리스트(ArrayList)에 대하여 설명하시오

배열을 이용하여 리스트를 구현한 자료구조입니다. 배열의 특성상 데이터를 리스트의 처음이나 중간에 저장하면 이후의 데이터들이 한칸씩 뒤로 물러나야하며 삭제의 경우 삭제하는 데이터 이후 데이터들이 순차적으로 한 칸씩 당겨져야 하기 때문에 비효율적입니다. 하지만 단순히 인덱슬을 이용하여 데이터를 가져오는 경우에는 배열의 특징을 그대로 가지고 있기 때문에 매우 빠른 속도를 보여줍니다.

Q2. 연결 리스트(Linked List)에 대해서 설명하시오

단순 연결 리스트(singly linked list)는 노드에 다음 노드의 주소를 가리키는 정보만 추기되어있는 가장 단순한 형태의 연결 리스트입니다. 가장 마지막 원소를 찾으려면 처음부터 리스트의 끝까지 탐색해야하기 때문에 시간복잡도가 O(n)입니다. 이 자로구조는 가장 첫번쨰 노드의 참조 주소를 잃어버릴 경우 데이터 전체를 못 쓰게되는 단점이 있습니다. 또한 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우에도 리스트가 끊어져 뒤쪽 자료들을 유실할 수 있는 불안정적인 자료구조입니다.

이중 연결 리스트(doubly linked list)는 다음 노드의 참조 뿐만 아니라 이전 노드의 참조도 같이 가리키게한 리스트 자료구조입니다. 단순 연결 리스트와 다르게 뒤에서부터 탐색하는 것도 빠르고 첫 노드나 마지막 노드 중 하나를 가지고 있다면 전체 리스트를 순회할 수 있기에 끊어진 리스트를 복구하는게 가능합니다. 하지만 관리해야 할 참조 주소가 2개이기에 삽입이나 정렬의 경우 작업량이 더 많고 소모되는 메모리의 양도 많습니다.

원형 연결 리스트(circular linked list)는 단순 연결 리스트에서 마지막 원소를 null이 아닌 첫번쨰 노드의 주소를 가리키게 한 것입니다.

Q3. 스택(Stack)에 대해서 설명하시오

스택은 마지막에 삽입된 요소가 가장 먼저 제거되는 후입선출 형태의 자료구조입니다. 새롭게 들어가는 요소의 위치를 스택 포인터라고 지칭합니다. 보통 삽입은 push, 제거는 pop, 가장 위에 있는 요소를 확인하기 위해 peek을 실행합니다. 이러한 스택의 최대 저장량을 초과했을 경우를 스택 오버플로우라 지칭합니다.

Q4. 큐(queue)에 대해서 설명하시오

큐는 먼저 삽입된 요소가 가장 먼저 제거되는 선입선출 형태의 자료구조입니다. 새롭게 들어오는 위치는 큐의 가장 뒤편인 back이며 제거되는 부분의 위치는 front라고 합니다. 보통 연결 리스트를 이용하여 구현합니다. 큐의 특수한 형태로 원형 큐나 덱이 있습니다.

Q5. 덱(dequeue)에 대해서 설명하시오

덱은 외형 구조가 큐와 유사합니다. 그러나 한쪽 방향으로만 넣고 꺼내는 큐와 달리 덱은 양쪽 끝에서 넣고 빼는 것이 가능한 자료구조입니다. 따라서 덱을 스택처럼 사용하는 것이 가능하고 또한 큐처럼 사용하는 것도 가능합니다.

Q6. 힙(heap)에 대해서 설명하시오

완전 이진 트리로 구성된 힙은 두가지로 나뉩니다.

최대 힙은 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같습니다. 즉 루트 노드에 저장된 값이 가장 큽니다.

최소 힙은 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 작거나 같습니다. 즉 루트 노드에 저장된 값이 가장 작습니다.

이때 힙에서 자식 노드에서의 크기에 따른 위치는 따로 없습니다. 예를 들어 최대 힙에서 이진 탐색 트리처럼 왼쪽이 작은 값이 오고, 오른쪽이 큰 값이 오는 그런 것은 만족하지 않아도 되고 단지 부모 노드가 자식 노드보다 값이 크거나 같으면 된다는 조건만 만족하면 됩니다.

최소 힙에서 데이터 삽입 과정은 다음과 같습니다.

완전 이진 트리 순서로 새 데이터를 넣습니다
만약 부모 노드가 존재한다면, 부모 노드보다 자식 노드의 우선순위가 낮다면 부모 노드와 자식 노드의 위치를 바꿉니다
계속해서 루트 노드까지 반복합니다.

최대 힙에서 데이터 삽입 과정은 다음과 같습니다.

완전 이진 트리 순서로 새 데이터를 넣습니다.
만약 부모노드가 존재한다면, 부모 노드보다 자식 노드의 우선순위가 높다면 부모노드와 자식노드의 위치를 바꿉니다
계속해서 루트 노드까지 반복합니다.

최대 힙에서 삭제 과정은 다음과 같습니다.

트리의 루트 노드를 삭제합니다
그리고 완전 이진 트리에서 가장 마지막에 위치한 노드를 루트 노드로 옮깁니다
루트 노드로 올라간 노드는 순차적으로 삽입 과정과 동일하게 비교를 하여 자신의 위치로 찾아갑니다.

삭제과정에서 최소힙에서는 루트 노드로 올라간 노드를 자식 노드와 비교할 때 자식 노드 중 작은 값과 교환하여야 합니다

만약 어떤 루트 노드가 삭제되고 16이 가장 위로 올라왔을 때, 15와 교환이 되면 15는 다시 14와 교환되어야 하는 상황이 일어나기에 최소 힙에서는 자식 노드 중 작은 값과 교환이 되어야 합니다.

당연히 최대 힙에서는 자식 노드 중 큰 값과 교환이 되어야 합니다.

Q7. 우선순위 큐(Priority Queue)에 대해 서 설명하시오

우선순위 큐는 일반 큐와는 다르게 제일 먼저 들어왔던 것이 먼저 제거되는것이 아닌 현재 우선순위 큐 안에서 제일 우선순위가 높은 원소가 먼저 제거됩니다. 우선순위 큐는 보통 Heap을 통해 구현됩니다. 따라서 top이 최댓값인 우선순위 큐를 최대 힙, 최솟값이 우선순위인 큐를 최소 힙이라 부르기도 합니다. 이때 삽입과 삭제 시 시간 복잡도는 $O(logN)$ 입니다.

// 우선순위 큐 순서 바꾸기
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

Q8. 트리(tree)에 대해 설명하시오

트리는 정점(Node)과 간선(Edge)으로 구성된 그래프의 특수한 형태로 그래프 내의 어떠한 두 정점 사이에도 사이클이 형성되지 않는 것을 말합니다.

트리는 다음으로 구성되어 있습니다.

노드(node) : 트리의 구성요소에 해당되는 요소
간선(edge) : 노드와 노드를 연결하는 연결 선
루트 노드(root node) : 트리 구조에서 최상위에 존재하는 노드
단말 노드(terminal node) : 아래로 또 다른 노드가 연결되어 있지 않은 노드
내부 노드(internal node) : 단말 노드를 제외한 모든 노드

부모 노드(parent node) : 노드 A는 노드 B, C, D의 부모 노드이다
자식 노드(child node) : 노드 B, C, D는 노드 A의 자식 노드이다.
형제 노드(sibling node) : 노드 B, C, D는 부모 노드가 같으므로 서로 형제노드라고 한다.

서브 트리(sub tree) : 하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리를 가리켜 서브 트리라고 한다. 서브 트리 역시 서브 트리로 이루어져 있고, 그 서브 트리 또한 다른 서브 트리로 이루어 져 있다. 즉 트리는 재귀적이다.

이진 트리(binary tree) : 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다. 나뉘어지는 두 서브 트리 또한 이진트리이다.

이진 트리의 완벽한 모습을 하고 있지 않고, 공집합 노드를 가지고 있어도 이진 트리라고 할 수 있다. 즉 공집합도 이진 트리에서는 노드로 간주한다.
즉 위와 같은 형태도 이진 트리로 간주한다.
트리는 각 레벨이 존재하고 위에서부터 아래로 올 수록 레벨이 증가한다.
또한 트리의 높이는 레벨의 최댓값과 같다.
모든 레벨에 노드가 꽉 차있다면 포화 이진 트리라고 말한다.
완전 이진 트리는 노드가 왼쪽에서 오른쪽 순서대로 형성되어 있다면 완전 이진 트리라고 한다. 결국 포화 이진트리이면 완전 이진트리이고 완전 이진 트리이면 포화 이진 트리 일 수도 있고 아닐 수도 있다.

Q9. 인접 행렬(adjacency matrix)에 대해서 설명하시오

인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다. 인접 행렬을 $adj[][]$ 라고 한다면 $adj[i][j]$ 는 노드 i에서 노드 j로 가는 간선이 있으면 1, 없으면 0으로 정의할 수 있습니다.

인접 행렬의 장점은 단순히 노드 i와 노드 j가 연결되어 있는지 확인하고 싶을때는 $adj[i][j]$ 만 확인하면 되기에 O(1)이라는 시간 복잡도를 가진다는 것입니다. 하지만 단점은 전체 노드의 갯수를 V라 했을 때 노드 i에 연결된 모든 노드들을 방문해 보고 싶은 경우 $adj[i][1]$ 부터 $adj[i][V]$ 까지 모두 확인해 보아야 하기에 총 $O(V)$ 의 시간이 걸린다는 것입니다.

Q10. 인접 리스트(adjacency list)에 대해서 설명하시오

인접 리스트는 그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 표현하는 방식입니다. 즉 각 정점마다 하나의 연결 리스트를 갖는 방식으로 구현합니다.

인접리스트는 실제로 연결된 노드들에 대한 정보만 저장하기에 모든 노드들의 연결리스트 갯수의 합이 간선의 개수와 같습니다. 즉 간선의 개수에 비례하는 메모리만 차지합니다. 또한 한 노드에서 연결된 모든 노드를 알고 싶은 경우 그 노드의 연결리스트만 확인해보면 됩니다. 하지만 인접 리스트는 노트 i와 노드 j가 연결되어 있는지 알고 싶을 때 해당 노드의 연결리스트를 전부 돌며 j가 포함되어 있는지 확인해야 합니다.

Rena Makise