datastructure.md

⁉️ Datastructure QnA

Array vs. LinkedList

Array와 LinkedList의 차이점을 설명하세요

먼저 원하는 원소에 접근할때 Array는 random access를 지원합니다.

인덱스를 통해 O(1)의 시간복잡도로 접근할 수 있습니다.

반면 Linkedlist는 sequential access를 지원합니다. 원하는 요소에 접근할 때 순차적으로 검색하며 찾아야해서 시간복잡도는 O(n)이 됩니다.

삽입/삭제의 경우 배열은 O(n)의 시간복잡도가 걸리고, 링크트리스트는 O(1)이 소요됩니다.

저장 방식도 배열에서 요소들은 인접한 메모리 위치에 연이어 저장됩니다. 반면 링크트리스트에서는 새로운 요소에 할당된 메모리 위치 주소가 링크트리스트의 이전 요소에 저장됩니다.

배열에서 메모리는 배열이 선언되자마자 compile time에 할당되어 집니다. (정적 메모리 할당)

링크트리스트에서 새로운 노드가 추가될 때 메모리를 runtime에 할당합니다. (동적 메모리 할당)

배열은 stack 섹션에 메모리 할당이 이루어지고 링크트 리스트는 heap 섹션에 메모리 할당이 이루어집니다.

array(list)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명하세요.

array

배열의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점입니다.

데이터에 순서가 있기 때문에 0부터 시작하는 인덱스가 존재하며, 인덱스를 사용해 특정 요소를 찾고 조작이 가능하다는 것이 array의 장점입니다.

반면에 이에 따른 단점도 존재하는데, 순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소들을 한칸씩 밀거나 당겨줘야하는 단점이 있습니다.

이런 경우 메모리 상에서 이루어지는 작업이 다른 자료구조에 비해 커지기 때문에 배열은 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절치 않습니다.

list

리스트는 순서대로 저장하는 자료구조입니다.

구현 방식에 따라 크게 array list와 linked list로 나누어집니다.

array list

배열을 이용하여 리스트를 구현한 것을 의미합니다.

따라서 가장 큰 특징은 배열과 같이 순차적으로 데이터를 저장한다는 점입니다.

인덱스를 이용해서 특정 원소에 접근이 빠르다는 장점이 있고 데이터의 추가와 삭제가 느리다는 단점이 있습니다.

또한 리스트의 크기보다 저장할 데이터의 양이 많을 때 메모리의 사이즈를 다시 조정해야하는 문제가 발생합니다. 새로운 메모리를 찾아 복제해야하므로 시간이 오래 걸립니다.

linked list

가장 큰 특징은 각 노드에 다음 노드의 주소를 저장한다는 점입니다.

고정된 크기를 갖지 않기 때문에 동적으로 메모리 사용이 가능합니다. 또한 삽입/삭제 연산 시 O(1)의 시간복잡도를 갖는 장점이 있습니다.

반면에 특정 위치의 데이터를 검색할때 순차적으로 검색하여 찾아야하므로 O(n)의 시간복잡도를 갖는 단점이 있습니다.

array를 적용시키면 좋을 데이터의 예를 구체적으로 들어주세요. 구체적 예시와 함께 array를 적용하면 좋은 이유, 그리고 array를 사용하지 않으면 어떻게 되는지 함께 서술해주세요.

달 별 주식 차트 데이터가 있습니다.

달 별 주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날자별로 주식 가격이 차례대로 저장되어야 하는 데이터 입니다.

순서가 중요한 데이터이므로 배열과 같이 순서를 보존해주는 자료구조를 사용하는 것이 좋습니다.

순서가 없는 자료구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어렵고, 매번 전체 자료를 읽어 들이고 비교해야 하는 문제가 발생합니다.

Tree

BST와 binary tree에 대해서 설명하시오.

binary search tree는 binary tree의 성질을 자식노드를 최대 2개까지 가지는 성질과 트리의 성질을 만족하고, 새로운 정의인 왼쪽 자식 노드에는 자기 자신보다 작은 키값을 오른 쪽은 자기 자신보다 큰 키값을 가지는 노드를 가지는 tree 구조입니다. 이런 성질과 함께 균형 잡힌 트리의 경우에 O(logn)의 시간 복잡도를 가진다. 균형 잡힌 트리를 구성하기 위해서 Red-black tree나 AVL tree를 이용한다.

중위 순회 코드를 작성해보시오.

```def inorder(self, node): if self.node == None: return self.inorder(node.left) print(node.key, end= ' ') self.inorder(node.right) ```

full binary tree와 complete binary tree의 특징을 말하시오.

full binary tree는 잎새 노드를 제외한 모든 노드가 자식 노드를 2개 아니면 0개 가지고 있다. complete binary tree는 마지막 레벨을 제외한 모든 레벨에서 노드들이 왼쪽 단말 노드부터 꽉 채워진ㄴ 이진트리이다. complete binary tree는 1차원 배열로도 표현이 가능하다.

트리의 정의 최소 3가지를 말하시오.

트리는 사이클을 가지지 않고 노드에서 모든 정점이 연결된 구조를 가지며, 간선의 개수가 노드의 개수-1이다. 또 간선 하나를 자르면 트리가 두 개로 분리된다. 마지막으로 임의의 노드에서 다른 노드로 가는 경로는 유일하다.

Stack and Queue

Stack, Queue, LinkedList의 차이점을 설명하세요

Stack은 먼저 들어간 데이터가 가장 늦게 나오는 LIFO 구조입니다. Queue는 먼저 들어간 데이터가 먼저 나오는 FIFO 구조입니다. LinkedList는 각각의 데이터가 그 다음 데이터를 가리키는 하나의 참조만 갖는 구조입니다.

Stack에 대해 설명하세요

스택은 LIFO의 원리로 동작하는 선형적인 자료구조입니다. 스택은 데이터를 한쪽으로 삽입하고 삭제하기 때문에 데이터는 들어간 반대 순서로 나오는 특징을 가집니다. 스택의 이러한 특징을 활용하여 “웹 브라우저 뒤로가기”,”후위 표기법 계산”, “수식의 괄호 검사” 을 할 수 있습니다.

Queue에 대해 설명하세요

큐는 FIFO의 원리로 동작하는 자료구조입니다. 큐는 데이터를 한쪽에서 삽입하고 다른 한쪽에서 삭제하기 때문에 데이터가 들어간 순서대로 나오는 특징을 가집니다. 큐의 이러한 특징을 활용하여 “BFS 그래프 탐색”, “CPU 프로세스 스케쥴링” 을 할 수 있습니다

Stack Overflow에 대해 설명해보세요

운영체제의 메모리 영역중 함수의 지역변수, 매개변수가 저장되는 스택영역이 있습니다. 함수가 과도하게 호출되어 스택영역공간이 가득차게 되면 stack overflow가 발생할 수 있습니다.

Heap

Priority Queue의 동작 원리에 대해서 설명하시오.

우선순위 큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다. 우선순위 큐를 구현하기 위해서 힙으로 구현하는 것이 가장 효율적입니다. 따라서 힙에 대해 설명드리면 힙은 완전 이진 트리의 일종으로 루트 노드의 값이 최대면 최대힙, 최소면 최소힙으로 표현합니다. 힙의 이러한 특징으로 힙의 루트노드를 꺼낸다면 우선순위 큐의 목적인 우선순위가 가장 높은 데이터를 얻을 수 있는 것입니다. 힙은 모든 노드가 자신의 자식 노드보다 우선순위가 높다는 성질을 가지고 있어 이 성질을 통해 삽입과 삭제 연산 모두 O(logN)의 시간복잡도를 가지게 되는데 이는 배열, 연결리스트로 구현한 우선순위 큐보다 효율적입니다.

Heap의 종류와 각각의 특징을 설명하시오.

힙의 종류에는 최소힙과 최대힙이 있습니다. 최소힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리입니다. 따라서 루트 노드가 가장 작은 값을 가지게 됩니다. 이와 반대로 최대힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리입니다. 따라서 루트 노드가 가장 큰 값을 가지게 됩니다.

Max Heap에서의 Heapify 과정을 설명하시오.

원소 삽입 과정을 예로 들면 먼저 가장 말단의 노드에 원소를 삽입합니다. 다음 부모 노드와 비교해서 자식 노드가 크다면 교환하고 작다면 해당 부분에서 정지해 Heapify가 완료됩니다. 이런 로직을 최대힙의 성질을 만족할 때까지 반복합니다. 원소 삭제 과정에서는 먼저 루트 노드를 삭제하고 마지막 원소를 루트로 이동 후에 큰 값을 가진 자식과 위치를 교환해 가며 힙 구조를 완성시킵니다.

Red-BlackTree

red black tree의 정의, 성질 4가지를 말하시오

red black tree는 다음 네가지의 조건을 만족해야한다. 루트 노드의 색깔은 검정이다(root property). 모든 leaf노드는 검정이다(external property). 빨강노드의 자식은 반드시 검정이다(internal property). 마지막으로 리프노드에서 루트 노드까지 가는 경로에서 만나는 블랙 노드의 개수는 같다.(depth property)

recoloring과 restructing을 시간 복잡도와 함께 설명하시오

restructing은 부모의 형제 노드가 검정색일 때 수행한다. restructing은 삽입된 노드, 부모 노드, 조부모 노드 이 세가지를 정렬하고 bst 성질에 맞게 트리구조로 바꾼 뒤에 중간 값을 루트로 달고 검정색으로 칠한뒤 나머지 노드는 빨강색으로 칠한다. 삽입을 하기 위해서 위치를 검색하는 시간 복잡도가 O(logn)이고 삽입과 정렬 모두 상수 시간이 들어서 최종적으로 restructing은 O(logn)의 시간 복잡도를 가진다. recoloring은 부모의 형제 노드의 색깔이 빨강색일때 진행한다. 부모와 부모의 형제의 색깔을 검정으로 만들어주고 삽입된 노드의 부모의 부모는 빨강색으로 바꾼다. 만약 부모가 root node라면 부모의 부모 색깔은 검정이 되고, 만약에 어떤 트리의 일부분인 서브트리라면 부모의 형제 색깔을 보고 restructing이나 recoloring을 다시 수행한다. 이에 따른 시간 복잡도는 restructing과 마찬가지로 insert해줄 위치를 찾는데 O(logn)시간이 걸리며 색깔만 바꿔주는데 상수시간이 걸려 최종적인 recoloring의 시간 복잡도는 O(logn)이다.

hash에서 red-black 트리가 사용되는 경우가 있는데, 사용하는 이유와 언제 사용하는지 설명하시오.

hash의 seperate chaining을 할 때, red-black tree로 링크드 리스트를 대체할 때가 있다. threshold가 8이상인 경우에 chaining하는 부분을 red-black tree로 구성하는 것이다. 그 이유는 링크드 리스트의 경우 검색의 시간 복잡도가 O(n)인데, red-black tree로 치환하게 되면 O(logn)으로 해시 충돌 시 더 빠른 검색을 보장하기 때문이다.

Hash Table

해시 테이블에 데이터를 저장하는 과정을 설명해보세요

해시 테이블은 배열로 이루어져있고 key-value 쌍의 데이터를 저장하는 자료구조입니다.

해시 함수를 통해 데이터의 key값으로 해시값을 얻을 수 있습니다. 이렇게 얻은 데이터의 해시값은 해시 bucket의 index로 사용되고, 해당 index에 데이터가 저장됩니다.

해시 충돌과 이를 해결하기 위한 방안에 대해 설명해보세요

해시 충돌을 설명하기전에 해시 함수에 대해 알아야 합니다.

해시 함수는 임의 크기의 데이터를 고정 크기의 값으로 매핑하는데 사용되는 함수입니다. 임의 크기의 데이터를 고정 크기의 해시값으로 변환하는 과정에서 서로 다른 데이터가 동일한 해시값을 갖는 해시 충돌이 발생할 수 있습니다.

해시 충돌을 해결하는데에 Open Addressing, Seperate Chaining 방식이 사용됩니다.

Open Addressing은 해시 충돌이 발생하면 비어있는 bucket을 찾아 데이터를 삽입하는 방식입니다. 비어있는 bucket을 찾는 방식에는 linear probing, quadratic probing, double hashing 이 있습니다.

linear probing은 해시 충돌이 발생한 위치로부터 고정폭만큼 이동하면서 비어있는 bucket을 찾는 방식입니다. quadratic probing은 해시 충돌이 발생한 위치로부터 n^2 만큼 이동하면서 비어있는 bucket을 찾는 방식입니다. 마지막으로 double hashing 방식은 데이터의 해시값을 다른 해시 함수로 해싱하여 비어있는 bucket을 찾는 방식입니다.

Seperate Chaining은 해시 bucket을 LinkedList를 가리키는 포인터로 구성하여 해시 충돌 발생시 해당 bucket의 LinkedList에 데이터를 추가하는 방식입니다.

특정 버킷에 해당하는 LinkedList의 데이터가 8개가 되면 Red Black Tree로 구조를 변경합니다. 그 이유는 데이터가 많아지면 LinkedList 의 탐색 속도가 느려지기 때문입니다.

데이터가 6개로 줄어들면 다시 LinkedList로 구조를 변경합니다. 그 이유는 Red black Tree를 사용하므로써 가질 수 있는 속도 측면의 이점이 크지 않고, 오히려 메모리 소요가 더 크기 때문입니다.

데이터 삭제시 발생할 수 있는 Open Addressing의 문제점에 대해 설명해보세요

Open Addressing 의 타겟 데이터 탐색 알고리즘은 다음과 같습니다. 현재 방문한 버킷이 비어있다면 탐색을 종료하고, 비어있지 않을 경우 버킷속 데이터가 타겟 데이터와 동일한지 확인합니다.

이러한 Open Addressing의 탐색 방식으로 인해 삭제하고자 하는 데이터를 찾는 과정에서 빈 버킷을 만나면 탐색이 종료되는 문제가 나타날 수 있습니다.

이 문제를 해결하기 위해 삭제된 버킷에 dummy node를 채우거나 flag를 활용하여 탐색 과정에서 빈 버킷을 만나더라도 탐색을 이어가도록 할 수 있습니다

LinkedList와 Red-Black Tree로 Seperate Chaining을 구현할 때 얻을 수 있는 이점에 대해 각각 설명해보세요

Seperate Chaining 방식을 따르는 해시 테이블에서 해싱 충돌이 발생한 데이터가 8개 되면 LinkedList에서 Red Black Tree로 구조를 변경합니다.

데이터의 개수가 많을 수록 O(N)의 시간복잡도를 가진 LinkedList의 탐색 속도는 느려지지만, Red Black Tree는 O(logN)으로 비교적 준수한 탐색 속도를 가집니다.

해시 출돌이 발생한 데이터가 6개로 줄어들면 Red Black Tree에서 LinkedLisf로 구조를 변경합니다.

데이터 개수가 6개 정도이면 Red Black Tree를 사용하므로써 가질 수 있는 속도 측면의 이점이 그리 크지 않고, 오히려 메모리 소요가 크기 때문에 LinkedList로 구조를 변경합니다.

Graph

그래프를 구현하는 방식들의 장단점을 비교하시오.

그래프를 구현하는 방식에는 인접행렬로 구현하는 방법과 인접리스트로 구현하는 방법이 있습니다. 먼저 인접행렬은 2차원 배열로 그래프의 연결 관계를 모두 표현하는 방법입니다. 따라서 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 0(1)의 시간복잡도면 가능하다는 장점이 있지만 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야하고 정점의 개수가 n개인 그래프는 간선의 수와 무관하게 항상 n^2의 메모리 공간이 필요하다는 단점이 있습니다. 다음으로 인접리스트는 각각의 정점에 인접한 정점들을 리스트로 표시하는 방법입니다. 필요한 만큼의 공간만 사용하기 때문에 인접행렬에 비해 공간의 낭비가 적고 정점들의 연결 정보를 탐색할 때 간선의 개수를 n개라고 했을때 O(n)의 시간이면 가능하다는 장점이 있지만 특정 두점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸린다는 단점이 있습니다.

그래프와 트리의 차이점에 대해서 설명하시오.

첫번째로 트리는 두 개의 정점 사이에 하나의 경로만 존재하는 반면 그래프는 노드 사이에 단방향 및 양방향 경로를 가질 수 있습니다. 두번쨰로 그래프에는 루프와 자체 루프가 있을 수 있지만 트리에는 루프와 자체 루프가 있을 수 없습니다. 세번째, 트리에는 계층적 구조가 있고 그래프는 네트워크 모델입니다.

BFS와 DFS의 차이점에 대해서 설명하시오.

DFS는 깊이 우선 탐색으로 탐색 노드의 인접 노드의 자식들을 모두 탐색하고, 다시 돌아와서 탐색 노드의 다른 인접 노드 자식들을 모드 탐색하는 방법으로 스택이나 재귀함수로 구현할 수 있습니다. 반면 BFS는 너비 우선 탐색으로 탐색 노드의 인접한 노드를 먼저 탐색하는 방법으로 큐를 이용해서 구현합니다. 두 방식 모두 조건 내의 모든 노드를 검색한다라면 인접 리스트로 구현하면 O(V+E), 인접 행렬로 구현하면 O(V^2)로 시간 복잡도는 동일합니다.

MinimumSpanningTree

최소 스패닝 트리에 대해서 설명해주세요.

그래프의 스패닝 트리 중 가선의 가중치(edge weight) 값이 최소인 스패닝 트리를 최소 스패닝 트리라고 합니다.

스패닝 트리란 그래프의 모든 정점이 사이클없이 연결된 형퇴를 말합니다.

크루스칼과 프림을 통해서 MST를 구현할 수 있습니다.

크루스칼과 프림 알고리즘의 시간복잡도에 대해 설명해주세요.

크루스칼의 경우 그래프의 간선들을 오름차순으로 정렬하여 가장 낮은 가중치의 간선부터 차례로 MST 집합에 추가하는 그리디 알고리즘 방식을 사용합니다.

union-find를 이용해서 사이클이 생성여부를 확인하면(추가하고자 하는 간선의 양 끝 정점이 같은 집합에 속해있는지 확인) 크루스칼 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우됩니다. 퀵 정렬을 사용해서 정렬한다면 O(ElogE) 의 시간복잡도를 가지게 됩니다.

프림의 경우는 시작 정점부터 인접한 간선들 중 낮은 가중치를 선택해가며 단계적으로 트리를 확장해가는 방식입니다.

모든 노드에 대해 탐색을 진행하므로 O(V) 입니다. 우선순위 큐(힙)을 사용하여 매 노드마다 최소 간선을 찾는 시간은 O(logV) 걸립니다. 따라서 탐색과정에는 O(VlogV)가 소요됩니다.

노드의 인접 간선을 찾는 시간은 O(E) 이 걸리고, 각 간선에 대해 힙을 업데이트해주는 과정에 O(logV) 가 걸려 우선순위 큐 구성에 O(ElogV) 의 시간복잡도가 소요됩니다. 따라서 O(VlogV+ElogV) = O((V+E)logV) 로 O(ElogV) 가 됩니다.

(∵E가 일반적으로 V보다 크기 때문)

만약 우선순위 큐가 아닌 배열로 구성한다면, 각 정점에 최소 간선을 찾는 탐색과정에 O(V^2) 이 걸리고, 탐색 결과를 기반으로 인접한 간선을 찾아 배열에 넣어주면 되므로 O(E*1) 이 소요됩니다. 따라서 시간복잡도는 (O(V^2)이 됩니다.

크루스칼 알고리즘과 프림 알고리즘의 차이점에 대해 설명해주세요.

크루스칼은 간선 위주의 알고리즘이고, 프림은 정점 위주의 알고리즘 입니다.

크루스칼의 경우 그래프의 간선들을 오름차순으로 정렬하여 가장 낮은 가중치의 간선부터 차례로 MST 집합에 추가하는 그리디 알고리즘을 사용하는 방식이고,

프림의 경우는 시작 정점부터 인접한 간선들 중 낮은 가중치를 선택해가며 단계적으로 트리를 확장해가는 방식입니다.

간선의 개수가 적은 경우에는 크루스칼을 간선의 개수가 많은 경우네는 프림 알고리즘을 사용하는 것이 좋습니다.