3주 차 후기
기존 스터디장의 건강상의 이유로 이번주부터 스터디장을 맡아서 진행했다
반 정도의 인원이 빠지고 새로운 멤버가 들어오는 변화가 있었고
새로운 멤버분도 범상치 않은 분이라(2분 중 1분은 못 오심) 4주 차도 기대가 된다
Array
Array vs List 차이점
- 배열(Array)은 크기가 고정되어 있으며, 인덱스로 원소에 접근할 수 있습니다.
- 리스트(List)는 크기가 가변적이며, 순서가 있습니다. 일반적으로 리스트에는 인덱스 대신에 순서를 이용하여 원소에 접근합니다.
ArrayList와 LinkedList를 설명하세요.
- ArrayList: 크기를 동적으로 변경할 수 있는 배열 구조입니다. 배열과 마찬가지로 인덱스를 사용하여 원소에 접근할 수 있고, 빠른 검색이 가능합니다. 단점은 삽입과 삭제가 느리다는 점입니다.
- LinkedList: 각각의 원소가 자신의 다음 원소의 주소를 가지고 있는 구조입니다. 노드(Node)라는 개념을 사용하여 각각의 원소를 표현합니다. 삽입과 삭제가 빠르지만, 검색이 느립니다.
링크드 리스트에 대해 설명해 주세요.
- 링크드 리스트(linked list)는 각 노드(node)가 데이터와 다음 노드를 가리키는 포인터로 이루어진 선형 자료구조입니다.
- 각 노드는 데이터와 포인터를 저장하는데, 이 포인터는 다음 노드를 가리키며, 마지막 노드는 NULL을 가리킵니다.
- 링크드 리스트는 삽입, 삭제, 검색이 일반 배열보다 더욱 효율적이며, 크기를 동적으로 조절할 수 있습니다. 하지만 인덱싱을 지원하지 않으므로, 특정 위치의 요소를 검색하려면 전체 노드를 순회해야 합니다.
- 링크드 리스트에는 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked List)가 있으며, 이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있습니다.
- 이중 연결 리스트는 단일 연결 리스트에 비해 검색 및 삭제가 더욱 효율적입니다.
일반 배열과, 링크드 리스트를 비교해 주세요.
- 일반 배열과 링크드 리스트는 원소를 저장하는 방식에서 차이가 있습니다. 일반 배열은 인덱스를 사용하여 각각의 원소에 접근하고, 링크드 리스트는 각각의 원소가 자신의 다음 원소를 가리키는 방식으로 원소를 저장합니다.
- 링크드 리스트는 각각의 원소가 메모리 상에서 분산되어 저장되기 때문에, 삽입과 삭제가 빠릅니다. 삽입과 삭제를 할 때에는 원소를 이동시키지 않아도 되기 때문입니다.
- 반면, 검색을 할 때에는 첫 번째 원소부터 순차적으로 탐색해야 하기 때문에 일반 배열보다 느립니다.
링크드 리스트를 사용해서 구현할 수 있는 다른 자료구조에 대해 설명해 주세요
- 링크드 리스트는 이중 연결 리스트(Double Linked List)로 구현할 수도 있습니다. 이중 연결 리스트는 각각의 원소가 다음 원소와 이전 원소의 주소를 가지고 있어서, 양쪽 방향으로 순회가 가능합니다.
- 링크드 리스트는 큐(Queue)와 스택(Stack)을 구현할 때에도 사용됩니다. 큐를 구현할 때에는 선입선출(FIFO)의 특성을 갖도록 하고, 스택을 구현할 때에는 후입선출(LIFO)의 특성을 갖도록 합니다.
Stack & Queue
스택과 큐에 대해 설명해주세요
- 스택(Stack): 후입선출(LIFO, Last-In-First-Out)의 원리를 따르는 자료구조입니다. 새로운 원소를 스택의 가장 위에 삽입(push)하고, 가장 위의 원소를 삭제(pop)합니다. 사용 예시로는 함수 호출 스택이 있습니다.
- 큐(Queue): 선입선출(FIFO, First-In-First-Out)의 원리를 따르는 자료구조입니다. 새로운 원소를 큐의 뒤에 삽입(enqueue)하고, 가장 앞에 있는 원소를 삭제(dequeue)합니다. 사용 예시로는 작업 대기열이 있습니다.
스택과 큐를 비교하고, 구현 방법에 대해 설명해 주세요.
- 스택과 큐는 각각 후입선출과 선입선출의 구조를 갖습니다.
- 스택은 배열이나 연결 리스트로 구현할 수 있습니다. 배열로 구현할 경우 삽입과 삭제가 O(1)의 시간복잡도를 갖지만, 크기가 고정되어 있습니다. 연결 리스트로 구현할 경우 크기가 가변적이지만, 검색 시간이 O(n)입니다.
- 큐는 배열, 연결 리스트, 혹은 원형 큐(circular queue)로 구현할 수 있습니다. 배열과 연결 리스트는 스택과 마찬가지로 각각의 장단점을 가지고 있습니다. 원형 큐는 배열로 구현하며, 큐의 뒤와 앞이 연결되어 있어서 배열의 끝에 도달하면 다시 배열의 처음으로 돌아가는 방식입니다.
Circular Queue
- 원형 큐(circular queue)는 큐의 뒤와 앞이 연결된 원형 구조를 갖는 큐입니다.
- 일반적인 큐에서는 큐의 끝에 도달하면 더 이상 원소를 추가할 수 없습니다. 하지만 원형 큐에서는 큐의 끝에 도달하면 다시 큐의 앞으로 돌아가서 원소를 추가할 수 있습니다.
- 원형 큐는 배열로 구현할 수 있으며, 큐의 끝에 도달하면 다시 큐의 처음으로 돌아가기 때문에 큐의 크기를 고정하지 않아도 됩니다.
스택 2개로 큐를, 큐 2개로 스택을 만드는 방법과, 그 시간복잡도에 대해 설명해 주세요.
- 스택 2개로 큐를 구현하는 방법은 다음과 같습니다.
- 스택1에 새로운 데이터를 추가합니다.
- 스택2를 비웁니다.
- 스택1에서 데이터를 하나씩 꺼내서 스택2에 넣습니다.
- 스택1에서 데이터를 모두 꺼낸 후, 스택2에서 데이터를 하나씩 꺼내서 반환합니다.
- 삽입: O(1)
- 삭제: O(n)
- 탐색: O(n)
- 큐1에 새로운 데이터를 추가합니다.
- 큐2를 비웁니다.
- 큐1에서 데이터를 하나씩 꺼내서 큐2에 넣습니다.
- 큐1에서 데이터를 모두 꺼낸 후, 마지막으로 큐2에서 데이터를 하나씩 꺼내서 반환합니다.
- 삽입: O(1)
- 삭제: O(n)
- 탐색: O(n)
- 따라서, 큐 2개로 스택을 구현하는 시간 복잡도는 다음과 같습니다.
- 따라서, 스택 2개로 큐를 구현하는 시간 복잡도는 다음과 같습니다.
시간복잡도를 유지하면서, 배열로 스택과 큐를 구현할 수 있을까요?
- 스택을 배열로 구현하는 경우
class Stack:
def __init__(self):
self.stack = []
def push(self, x):
self.stack.append(x)
def pop(self):
if not self.stack:
return None
return self.stack.pop()
def top(self):
if not self.stack:
return None
return self.stack[-1]
def is_empty(self):
return not bool(self.stack)- 큐를 배열로 구현하는 경우
class Queue:
def __init__(self):
self.queue = []
def push(self, x):
self.queue.append(x)
def pop(self):
if not self.queue:
return None
return self.queue.pop(0)
def front(self):
if not self.queue:
return None
return self.queue[0]
def is_empty(self):
return not bool(self.queue)Prefix, Infix, Postfix에 대해 설명하고, 이를 스택을 활용해서 계산/하는 방법에 대해 설명해 주세요.
- Prefix, Infix, Postfix는 수식을 표현하는 방법 중 하나입니다.
- Infix는 일반적인 수식의 표현 방법으로, 연산자가 피연산자 사이에 위치합니다.
- Prefix는 연산자가 피연산자 앞에 위치하는 표기법입니다. 예를 들어, (3 + 4) * 5는 * + 3 4 5로 표현할 수 있습니다.
- Postfix는 연산자가 피연산자 뒤에 위치하는 표기법으로, (3 + 4) * 5는 3 4 + 5 *로 표현할 수 있습니다.
- 스택을 이용하여 계산할 때는, 수식을 앞에서부터 차례대로 읽어가면서 피연산자를 스택에 넣고, 연산자를 만나면 스택에서 피연산자를 꺼내 계산을 수행합니다.
- 이렇게 계산하면 Prefix와 Postfix는 연산자의 우선순위를 고려하지 않아도 됩니다.
Deque는 어떻게 구현할 수 있을까요?
- Deque는 Double Ended Queue의 약어로, 양 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다.
- 일반적으로 Deque는 이중 연결 리스트로 구현됩니다. 각 노드는 앞 노드와 뒤 노드에 대한 포인터를 가지고 있으며, 이를 통해 양 방향으로 순회가 가능합니다.
- Deque의 삽입과 삭제는 상수 시간(O(1))에 이루어집니다. 양 끝에서의 삽입과 삭제가 가능하기 때문에, 스택이나 큐와 유사한 동작을 수행할 수 있습니다.
- 배열 기반의 Deque 구현도 가능하지만, 중간에 삽입과 삭제가 일어날 경우, 이동 연산이 필요하므로 비효율적입니다.
- Deque는 스택과 큐의 기능을 모두 가진 자료구조로, 상황에 따라 다양하게 활용될 수 있습니다.
(C++ 한정) Deque의 Random Access 시간복잡도는 O(1)입니다. 이게 어떻게 가능한 걸까요?
- C++에서 Deque는 배열과 비슷한 방식으로 구현됩니다.
- 하지만 Deque는 블록 단위로 배열을 관리하며, 각 블록은 일정 크기의 원소들을 담고 있습니다.
- 이때, Deque는 포인터와 인덱스를 이용해 블록과 원소를 참조합니다. 이러한 방식으로 인덱스를 이용한 임의 접근 시간복잡도는 O(1)이 됩니다.
- 또한 Deque는 동적 배열과 달리 크기가 고정되어 있지 않으므로, 크기가 커지거나 작아질 때마다 메모리를 재할당할 필요가 없어, 메모리 관리 측면에서도 효율적입니다.
Deque은 어떤 식으로 구현할 수 있을까요?
- Deque (Double Ended Queue)는 양쪽 끝에서 삽입과 삭제가 가능한 선형 자료 구조입니다.
- Deque는 배열이나 연결 리스트를 이용해 구현할 수 있습니다.
- C++의 STL(Standard Template Library)에서는 deque 클래스를 제공하며, 동적 배열로 구현되어 있습니다. 내부적으로는 중앙에 있는 포인터를 이용해 앞과 뒤에 각각의 요소를 가리키며, 필요에 따라 중앙 포인터를 이동시켜 삽입과 삭제를 수행합니다.
- deque 클래스는 스택과 큐의 기능을 모두 지원하며, 임의 위치에 요소를 삽입하거나 삭제할 수 있는 insert()와 erase() 함수를 지원합니다.
- 인덱스를 이용한 랜덤 액세스에 대해서도 O(1)의 시간복잡도를 보장합니다. 따라서, 대부분의 상황에서 deque을 이용해 구현할 수 있습니다.
Heap
힙에 대해 설명하고, Heap Sort에 대해 설명해 주세요.
- 힙(Heap)은 트리(Tree) 자료구조의 일종으로, 부모 노드와 자식 노드 간의 대소 관계를 유지하는 이진트리(Binary Tree)입니다.
- 대개 우선순위 큐(Priority Queue)나 힙 정렬(Heap Sort)에서 사용됩니다. 이진 힙은 완전 이진트리의 한 종류로, 배열을 이용해서 구현할 수 있습니다.
- Heap Sort는 힙을 이용한 정렬 알고리즘으로, 최소 힙(Min Heap)이나 최대 힙(Max Heap)을 이용해서 정렬합니다. 먼저 입력된 배열을 힙으로 만든 후, 힙에서 최솟값 혹은 최댓값을 꺼내어 배열의 가장 마지막 위치로 이동시킵니다. 그리고 다시 힙을 만들어 꺼내고, 이를 반복하면 정렬된 배열을 얻을 수 있습니다.
Heap Sort 공간복잡도, 시간복잡도
Heap Sort의 공간복잡도는 O(1)입니다. 정렬할 배열 내부에서 원소 위치를 바꾸는 in-place 정렬 알고리즘으로, 추가적인 공간이 필요하지 않습니다.
힙을 배열로 구현한다고 가정하면, 어떻게 값을 저장할 수 있을까요?
힙을 배열로 구현하면, 각 노드의 인덱스와 값을 연결해서 저장합니다. 이때, 배열의 0번 인덱스는 사용하지 않으며, 인덱스 1부터 시작합니다.
힙의 삽입, 삭제 방식에 대해 설명하고, 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해 주세요.
힙의 삽입은 항상 마지막 노드에 새로운 값을 넣고, 부모노드와 우선순위를 비교하여 자리를 바꿔가면서 진행합니다.
삭제는 루트노드를 삭제한 후, 마지막 노드를 루트로 옮긴 후, 자식노드 중 우선순위가 높은 노드와 자리를 바꿔가면서 진행합니다.
이진탐색트리와 달리, 힙은 부모노드의 우선순위가 자식노드의 우선순위보다 높아야 하므로, 우선순위가 높은 자식노드를 왼쪽 자식으로 할당하게 됩니다. 이에 따라 균형 잡힌 트리 구조를 유지하며, 편향이 발생하지 않습니다.
힙 정렬의 시간복잡도는 어떻게 되나요? Stable 한가요?
힙 정렬(Heap Sort)의 시간복잡도는 O(n log n)입니다. 이는 힙을 구성하는데 O(n) 시간이 소요되고, 최대 힙에서 루트 노드를 제거하고 다시 최대 힙을 구성하는 연산이 n-1번 필요하기 때문입니다.
힙 정렬은 unstable 한 정렬 알고리즘입니다. 즉, 동일한 값의 원소들의 상대적인 순서가 정렬 이전과 정렬 이후에도 유지되지 않을 수 있습니다. 이는 최대 힙에서 루트 노드를 꺼내 정렬할 때, 힙 내에서 원소들의 상대적인 순서가 보장되지 않기 때문입니다.
Tree
Binary Tree
이진트리(Binary Tree)는 각 노드가 최대 2개의 자식 노드를 갖는 트리 구조를 말합니다. 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드를 가질 수 있습니다.
이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾아내는 알고리즘으로, 중앙값을 기준으로 탐색하고자 하는 값과 비교하여 다음 탐색할 구간을 좁혀가며 찾는 과정을 반복합니다.
이진 탐색의 시간 복잡도는 O(log n)입니다. 이는 배열의 크기가 n일 때, 이진 탐색이 최대 log₂n 단계까지 진행되기 때문입니다. 이진 탐색은 분할 정복 알고리즘의 하나로, 각 단계마다 탐색 대상이 절반으로 줄어드는 특성 때문에 시간 복잡도가 로그 시간에 수렴합니다.
이진 탐색 알고리즘은 반드시 정렬된 배열에서 사용해야 하므로, 정렬에 소요되는 시간이 추가로 필요합니다. 따라서 이진 탐색의 총 시간 복잡도는 O(n log n)이 됩니다. 하지만, 배열이 한 번 정렬된 이후에는 삽입, 삭제 등의 연산을 수행할 때마다 다시 정렬할 필요 없이 이진 탐색을 진행할 수 있어, 이진 탐색의 장점을 살려 사용할 수 있습니다.
Full Binary Tree
트리가 Full Binary Tree인 경우, 모든 레벨에서 노드가 꽉 차있는 이진트리를 말합니다. 즉, 모든 노드가 0개 또는 2개의 자식 노드를 가지고 있습니다.
Complete Binary Tree
Complete Binary Tree는 마지막 레벨을 제외한 모든 레벨에서 노드가 꽉 차있는 이진트리입니다. 마지막 레벨에서는 왼쪽부터 노드가 차례로 채워져 있습니다. Complete Binary Tree는 힙(Heap)이나 이진탐색트리(Binary Search Tree)를 구현할 때 유용하게 사용됩니다.
BST (Binary Search Tree)
이진탐색트리(Binary Search Tree, BST)는 이진트리의 일종으로, 왼쪽 서브트리의 모든 노드의 값은 루트 노드의 값보다 작고, 오른쪽 서브트리의 모든 노드의 값은 루트 노드의 값보다 큰 특징을 가지고 있습니다.
Lower Bound, Upper Bound는 무엇이고, 이를 어떻게 구현할 수 있을까요?
Lower Bound와 Upper Bound는 각각 찾고자 하는 값보다 크거나 같은 가장 작은 값과, 찾고자 하는 값보다 작은 가장 큰 값입니다. BST에서는 이를 각각 가장 작은 큰 값을 찾는 탐색과, 가장 큰 작은 값을 찾는 탐색으로 구현할 수 있습니다.
이진탐색의 논리를 적용하여 삼진탐색을 작성한다고 가정한다면, 시간복잡도는 어떻게 변화할까요?
이진탐색에서는 각 단계마다 탐색 대상이 반으로 줄어듭니다. 삼진탐색에서는 탐색 대상이 1/3로 줄어들기 때문에 시간복잡도가 이진탐색보다 더 큰 값이 나올 것입니다.
기존 이진탐색 로직에서 부등호의 범위가 바뀐다면, (ex. <= 라면 <로, <이라면 <= 로) 결과가 달라질까요?
BST는 루트보다 작은 값은 왼쪽, 큰 값은 오른쪽에 위치하게 됩니다. 따라서 부등호의 범위에 따라 검색하는 노드가 달라지므로 결과가 달라질 수 있습니다.
삭제, 삽입, 탐색 시간복잡도
삽입, 삭제, 탐색 모두 BST에서는 최악의 경우에는 모든 노드를 다 돌아봐야 할 수 있기 때문에 O(n)이 될 수 있습니다. 하지만, 노드를 삽입할 때나 삭제할 때 평균적으로는 O(log n)의 시간복잡도를 가집니다.
이진탐색트리에서 중위 탐색을 하게 되면, 그 결과는 어떤 의미를 가지나요?
이진탐색트리에서 중위 탐색을 하게 되면, 루트보다 작은 값들을 오름차순으로 탐색할 수 있습니다.
이진탐색트리의 주요 연산에 대한 시간복잡도를 설명하고, 왜 그런 시간복잡도가 도출되는지 설명해 주세요.
이진탐색트리의 주요 연산인 탐색, 삽입, 삭제 연산의 시간복잡도는 모두 O(log n)입니다
이는 트리의 높이와 관련이 있으며, 이진탐색트리는 항상 균형을 유지하지 않기 때문에 최악의 경우 편향 트리가 되어 시간복잡도가 O(n)이 될 수도 있습니다. 이진탐색트리의 삽입, 삭제 연산에서는 트리를 재구성하거나 재배치하는 작업이 필요할 때가 있기 때문에 시간복잡도가 O(log n)으로 유지되도록 구현해야 합니다.
이진탐색트리의 한계점에 대해 설명해 주세요.
이진탐색트리의 한계점은 트리의 균형을 유지하지 않을 경우에 성능이 나빠질 수 있다는 것입니다. 이는 삽입, 삭제 연산 시에 트리가 편향되는 경우 발생할 수 있는데, 이러한 경우 시간복잡도가 O(n)이 되어서 성능이 매우 나빠질 수 있습니다. 이를 보완하기 위한 대안으로 AVL 트리, 레드-블랙 트리, B-트리 등이 제안되었습니다.
이진탐색트리의 값 삽입, 삭제 방법에 대해 설명하고, 어떤 식으로 값을 삽입하면 편향이 발생할까요?
먼저, 삽입 시에는 삽입할 값을 탐색하여 해당 위치에 노드를 삽입합니다.
삭제 시에는 삭제할 노드의 자식 노드를 조합하여 새로운 트리를 만들어야 하는데, 삭제할 노드가 자식 노드를 하나만 가지고 있을 경우에는 해당 자식 노드를 삭제할 위치로 올리면 됩니다. 그러나 삭제할 노드가 두 개의 자식 노드를 가지고 있는 경우에는 자식 노드 중에서 대체 노드를 선택해야 하며, 이때 대체 노드를 선택하는 방법에 따라 편향 트리가 발생할 수 있습니다. 값이 일정한 순서로 삽입되는 경우, 편향 트리가 발생할 가능성이 높으므로 트리가 균형을 유지할 수 있도록 삽입 방법을 개선해야 합니다.
Binary Heap란
Binary Heap은 완전 이진트리(Complete Binary Tree)의 일종으로, 부모 노드와 자식 노드 간의 대소관계가 성립하는 자료구조입니다. 또한, 부모 노드의 값이 항상 자식 노드의 값보다 큰 경우를 Max Heap이라 하고, 반대로 부모 노드의 값이 항상 자식 노드의 값보다 작은 경우를 Min Heap이라고 합니다.
Red Black Tree
Red Black Tree는 이진 탐색 트리의 일종으로, 각 노드에 빨간색 또는 검은색을 칠하여 균형을 유지하는 트리입니다. 이 트리는 균형을 맞추기 위해 노드를 삽입하거나 삭제할 때 색상을 변경하고 회전하는 과정을 거치며, 노드의 삽입과 삭제가 빈번히 일어나는 경우에도 효율적으로 동작합니다.
Red Black Tree에 대해 설명해 주세요.
- 이진 탐색 트리의 일종으로, 각 노드는 최대 두 개의 자식 노드를 갖습니다.
- 루트 노드부터 임의의 노드까지 경로 상에 있는 노드들의 색깔은 모두 같습니다.
- 루트 노드는 검은색입니다.
- 노드가 빨간색일 경우, 해당 노드의 자식 노드는 모두 검은색입니다.
- 각 리프 노드에서부터 루트 노드까지의 모든 경로에는 검은색 노드가 동일한 개수만큼 존재합니다.
8(B)
/ \
3(R) 10(R)
/ \ \
1(B) 6(B) 14(B)
/ \ /
4(R) 7(R) 13(R)- 루트는 검은색(B)
- 빨간색 노드의 부모와 자식은 모두 검은색
- 모든 리프 노드는 검은색이며, NIL 노드는 검은색으로 취급
Red Black Tree는 어떻게 균형을 유지할 수 있을까요?
Red Black Tree는 노드에 대한 5가지 규칙을 통해 균형을 유지합니다.
모든 노드는 Red 또는 Black 중 하나의 색을 가집니다.
Root node는 Black입니다.
모든 leaf node는 Black입니다. (즉, NULL pointer는 Black으로 간주합니다.)
Red 노드의 자식들은 반드시 Black입니다.
Black 노드의 자식들은 Red일 수도, Black일 수도 있습니다.
Red Black Tree의 주요 성질 4가지
루트에서 리프까지의 모든 경로는 리프 중 가장 긴 경로의 길이의 2배를 넘지 않습니다.
모든 leaf node는 Black입니다.
Red 노드의 자식은 반드시 Black입니다.
모든 노드에 대해, 해당 노드를 루트로 하는 서브트리에서, 어떤 leaf node에 도달하는 경로에는 모두 동일한 개수의 Black 노드가 존재합니다.
2-3-4 Tree, AVL Tree 등의 다른 BBST 가 있음에도, 왜 Red Black Tree가 많이 사용될까요?
Red Black Tree는 회전이라는 간단한 연산만을 사용하면 되기 때문에 구현이 쉬우면서도 빠르게 수행할 수 있습니다. 이에 비해 2-3-Tree, AVL Tree 등의 BBST는 각 노드에 대한 정보를 저장해야 하기 때문에 메모리 사용이 더 많고, 복잡한 연산이 필요합니다. 또한 Red Black Tree는 대부분의 경우에 대해 균형을 잘 유지할 수 있기 때문에, 데이터 삽입, 삭제 시 Red Black Tree를 사용하는 것이 적절한 경우가 많습니다.
BBST에 대해 설명하고, RBT, B/B+Tree를 제외한 BBST의 예시를 설명해 주세요.
BBST(Balanced Binary Search Tree)란, 이진탐색트리에서 삽입, 삭제 연산 시에도 검색 시와 같은 O(log n) 시간복잡도를 유지하면서, 노드의 균형을 조정하는 자료구조를 의미합니다. 대표적인 BBST로는 Red Black Tree, 2-3-4 Tree, AVL Tree, B/B+Tree 등이 있습니다. RBT, B/B+Tree를 제외한 BBST의 예시로는 Weight Balanced Tree, Treap 등이 있습니다. Weight Balanced Tree는 트리의 높이에 가중치를 부여하여 균형을 유지하는 트리로, 이진탐색트리에 가중치를 더한 구조입니다. Treap은 BST의 키 값에 우선순위를 추가하여 BST의 성질을 만족하면서 랜덤 한 우선순위를 통해 균형을 유지하는 자료구조입니다.
Minimum Spanning Tree가 무엇이고, 어떻게 구할 수 있을지 설명해 보세요.
Minimum Spanning Tree(MST)란 가중치 그래프에서 모든 노드를 연결하면서 가장 작은 총가중치를 갖는 트리를 말합니다. 즉, 그래프에서 일부 간선을 선택해 트리 형태로 연결하는 것을 말합니다.
Kruskal이란
MST를 구하는 방법 중 하나는 Kruskal 알고리즘입니다. Kruskal 알고리즘은 간선의 가중치를 기준으로 오름차순으로 정렬한 후, 작은 가중치부터 선택하면서 트리를 확장해 가는 방법입니다. 선택한 간선이 트리에 사이클을 형성하지 않으면 선택합니다.
트리와 그래프의 차이는 무엇인가요?
트리는 그래프의 일종으로, 여러 개의 노드가 간선으로 연결되어 있고, 사이클이 없는 구조를 말합니다. 그래프는 노드와 간선으로 이루어진 자료구조로, 사이클이 없는 그래프를 트리라고 부를 수 있습니다. 하지만 트리는 루트 노드가 존재하며, 모든 노드는 루트 노드에서부터 유일한 경로로 접근 가능한 구조를 가집니다. 그래프는 사이클이 있을 수 있지만, 트리는 사이클이 없습니다.
Graph
Graph 용어정리
그래프(Graph) : 정점과 간선으로 이루어진 자료구조
정점(Vertex) : 그래프에서 한 점을 나타내는 개념 (또는 노드(Node))
간선(Edge) : 그래프에서 두 정점을 연결하는 선
가중치(Weight) : 간선에 부여된 값으로, 보통 두 정점 간의 거리나 비용을 나타냄
방향성(Directedness) : 간선이 한쪽 방향으로만 이어져 있는 그래프를 '방향 그래프'라고 함
인접 정점(Adjacent Vertex) : 두 정점이 간선으로 연결되어 있는 경우, 이 두 정점을 '인접 정점'이라고 함
차수(Degree) : 하나의 정점에 연결된 간선의 수를 나타내는 개념
Graph 구현
그래프를 구현하는 방법은 크게 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)로 나눌 수 있습니다.
인접 행렬 : 2차원 배열을 사용하여 구현, 각 정점의 인접 관계를 배열에 저장하는 방식입니다. 구현이 간단하고, 두 정점 간의 연결 여부를 빠르게 확인할 수 있습니다. 하지만, 정점과 간선의 개수가 많을 경우 공간복잡도가 크게 증가하게 됩니다.
인접 리스트 : 연결 리스트를 사용하여 구현, 각 정점과 이에 인접한 정점들을 연결리스트로 구현하는 방식입니다. 인접한 정점들만 저장하기 때문에, 공간복잡도가 인접 행렬에 비해 작습니다. 하지만, 간선의 개수에 비례하는 시간복잡도를 가지므로, 간선의 개수가 적을 경우 인접 행렬보다 성능이 떨어질 수 있습니다.
Graph 탐색
그래프 탐색은 그래프 자료구조에서 정점들을 탐색하는 것을 의미합니다. 대표적인 두 가지 방법으로 DFS(Depth-First Search)와 BFS(Breadth-First Search)가 있습니다.
DFS는 한 정점에서 시작하여, 그 정점과 인접한 모든 정점들을 순서대로 방문하고, 그다음에 그 인접한 정점들의 인접한 정점들을 탐색하는 방법입니다. 이때, 방문한 정점은 스택에 저장됩니다.
BFS는 한 정점에서 시작하여, 그 정점과 인접한 모든 정점들을 먼저 방문하고, 그 다음에 인접한 정점들의 인접한 정점들을 순서대로 탐색하는 방법입니다. 이 때, 방문한 정점은 큐에 저장됩니다.
Minimum Spanning Tree
최소 신장 트리(Minimum Spanning Tree, MST)는 가중치 그래프에서 모든 정점을 포함하면서 간선 가중치의 합이 최소인 트리를 의미합니다. 대표적인 두 가지 알고리즘으로는 Kruskal 알고리즘과 Prim 알고리즘이 있습니다.
Kruskal 알고리즘
간선을 가중치의 오름차순으로 정렬한 후, 작은 가중치의 간선부터 하나씩 선택하여 사이클을 만들지 않는 간선만을 선택하여 트리를 구성합니다.
Prim 알고리즘
임의의 정점을 선택한 후, 해당 정점에 연결된 간선들 중 최소 가중치를 갖는 간선을 선택하여 트리를 구성합니다. 이후 선택된 간선들과 연결된 정점들 중에서 최소 가중치를 갖는 간선을 선택하여 트리를 확장합니다.
그래프를 구현하는 두 가지 방식에 대해 설명해 주세요.
그래프를 구현하는 두 가지 방식은 인접 행렬과 인접 리스트입니다.
인접 행렬: 그래프의 정점을 2차원 배열로 나타낸 것입니다. 배열의 i번째 행과 j번째 열은 정점 i와 정점 j 사이의 간선이 존재하는지를 나타냅니다. 만약 간선이 존재하면 1로, 존재하지 않으면 0으로 표시됩니다.
인접 리스트: 그래프의 정점을 연결 리스트로 나타낸 것입니다. 리스트의 i번째 원소는 정점 i와 연결된 모든 간선을 저장합니다.
Kruskal 할 때 사용하는 자료구조
Kruskal algorithm에서는 Union-Find 자료구조를 사용합니다. 이 자료구조는 집합들을 관리하는 자료구조로, 각 집합의 대표 원소를 트리의 루트 노드로 설정하며, 두 집합을 합치거나 같은 집합에 속하는지를 확인할 수 있습니다.
Kruskal algorithm과 Prim algorithm의 시간복잡도
Kruskal algorithm과 Prim algorithm의 시간복잡도는 둘 다 O(E log E)입니다. 공간복잡도는 Kruskal algorithm이 O(E)이고, Prim algorithm이 O(V)입니다. 이때, E는 간선의 개수, V는 정점의 개수입니다. Kruskal algorithm은 정렬 알고리즘의 시간복잡도에 따라 다르지만, 일반적으로 Quicksort와 같은 O(E log E)의 시간복잡도를 갖습니다.
node의 개수가 N개, edge의 개수가 N^3 일 경우, 무엇이 더 효율적일까
node의 개수가 N개, edge의 개수가 N^3 일 경우, Prim algorithm이 더 효율적입니다. 이는 Kruskal algorithm의 시간복잡도가 O(E log E)인 반면, Prim algorithm의 시간복잡도가 O(E + V log V)이기 때문입니다. edge의 개수가 N^3이라면, E는 N^3이 되며, V는 N이므로, Kruskal algorithm의 시간복잡도는 O(N^3 log N)이 되고, Prim algorithm의 시간복잡도는 O(N^3 + N log N)이 됩니다. 따라서, Prim algorithm이 더 효율적입니다.
그래프 자료구조에 대해 설명하고, 이를 구현할 수 있는 두 방법에 대해 설명해 주세요.
그래프는 노드(Vertex)와 간선(Edge)으로 이루어진 자료구조로, 노드들 간의 관계를 표현할 수 있습니다. 이를 구현하는 두 가지 방법은 인접 행렬과 인접 리스트입니다.
각 방법에 대해, "두 정점이 연결되었는지" 확인하는 시간복잡도와 "한 정점에 연결된 모든 정점을 찾는" 시간복잡도, 그리고 공간복잡도를 비교해 주세요.
그래프 자료구조를 구현하는 두 가지 방법은 인접 행렬과 인접 리스트입니다.
인접 행렬
각 노드들을 2차원 배열로 표현하여, 노드 간의 연결 정보를 행렬로 저장하는 방법입니다.
두 정점이 연결되어 있는지 확인하는 시간복잡도: O(1)
한 정점에 연결된 모든 정점을 찾는 시간복잡도: O(V) (V는 전체 노드의 개수)
공간복잡도: O(V^2) (모든 노드 쌍에 대한 연결 정보를 저장하기 때문에)
인접 리스트
노드들을 연결리스트 형태로 표현하여, 각 노드에 연결된 노드들의 정보를 저장하는 방법입니다.
두 정점이 연결되어 있는지 확인하는 시간복잡도: 연결리스트 탐색 시간인 O(degree) (degree는 해당 노드의 차수, 즉 해당 노드와 연결된 노드의 개수)
한 정점에 연결된 모든 정점을 찾는 시간복잡도: O(degree)
공간복잡도: O(E+V) (E는 간선의 개수, V는 노드의 개수)
인접 행렬은 노드 수가 적을 때는 간편하게 사용할 수 있으나, 노드 수가 많아질수록 공간복잡도가 커지는 단점이 있습니다. 반면 인접 리스트는 간선 수가 많을 때 유리하며, 공간을 더 효율적으로 사용할 수 있습니다.
정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 방식으로 구현하는 것이 효율적일까요?
정점의 개수가 N개, 간선의 개수가 N^3 개라면, 인접 리스트를 사용하는 것이 더 효율적입니다. 인접 행렬의 공간복잡도가 O(N^2)이므로, N이 크면 매우 많은 공간을 차지하게 됩니다.
사이클이 없는 그래프는 모두 트리인가요? 그렇지 않다면, 예시를 들어주세요.
사이클이 없는 그래프가 모두 트리는 아닙니다. 사이클이 없는 연결 그래프(Connected Graph)는 Spanning Tree이며, Spanning Tree는 사이클이 없는 그래프입니다. 하지만, 사이클이 없는 비연결 그래프(Disconnected Graph)는 여러 개의 Spanning Tree를 가질 수 있습니다.
그래프에서 최단거리를 구하는 방법은 여러 가지가 있지만, 대표적인 방법으로는 Dijkstra 알고리즘과 Bellman-Ford 알고리즘이 있습니다. Dijkstra 알고리즘은 가중치가 양수인 그래프에서, Bellman-Ford 알고리즘은 음수 가중치가 있을 때도 사용할 수 있습니다. 둘 다 다익스트라 알고리즘보다 시간복잡도가 높습니다.
자료구조, 시간복잡도/공간복잡도
자바스크립트(Javascript) 자료구조
배열(Array): 순서가 있는 데이터를 저장하는 자료구조로, 인덱스를 이용해 접근한다. 동적으로 크기를 변경할 수 있으며, 중간에 값을 추가하거나 삭제할 때 다른 값들을 밀거나 당겨야 하는 단점이 있습니다.
객체(Object): Key-Value 쌍으로 데이터를 저장하는 자료구조로, 객체 내의 속성에 접근할 때 대괄호([])나 마침표(.)를 사용한다. 동적으로 속성을 추가하거나 삭제할 수 있습니다.
파이썬(Python) 자료구조
리스트(List): 순서가 있는 데이터를 저장하는 자료구조로, 자바스크립트의 배열과 비슷하다. 인덱스를 이용해 접근하며, 동적으로 크기를 변경할 수 있습니다.
딕셔너리(Dictionary): Key-Value 쌍으로 데이터를 저장하는 자료구조로, 자바스크립트의 객체와 비슷하다. 딕셔너리 내의 키에 접근할 때 대괄호([])를 사용하며, 동적으로 키-값 쌍을 추가하거나 삭제할 수 있습니다.
구성
자바스크립트와 파이썬에서는 배열과 리스트가 동적으로 크기를 변경할 수 있다는 점에서, 메모리 관리 측면에서 유연하다. 하지만 이러한 유연성 때문에 연속된 메모리 공간에 데이터를 저장하는 C나 Java와 같은 언어보다는 성능이 떨어질 수 있습니다.
객체와 딕셔너리는 해시 테이블(Hash Table)을 사용해 구현되어 있다. 해시 테이블은 키(key)와 값(value)을 해시 함수(Hash Function)를 이용해 일정한 규칙으로 연결하고, 이를 검색과 삽입에 이용하는 자료구조입니다. 해시 테이블은 검색과 삽입에 빠른 속도를 보이지만, 해시 함수가 충돌할 경우(두 개 이상의 키가 동일한 위치에 매핑되는 경우) 성능이 저하될 수 있습니다.
Thread Safe 한 자료구조가 있을까요? 없다면, 어떻게 Thread Safe 하게 구성할 수 있을까요?
Thread Safe 한 자료구조란 여러 개의 스레드가 동시에 자료구조에 접근하더라도 예상한 대로 동작하도록 보장하는 자료구조를 말합니다.
자바에서는 Vector와 Hashtable 등이 Thread Safe 한 자료구조입니다. 이들 자료구조는 내부적으로 synchronized를 이용하여 스레드 동기화를 제공합니다.
파이썬에서는 기본적으로 Thread Safe한 자료구조를 제공하지 않습니다. 따라서 멀티스레드 환경에서 사용하기 위해서는 Thread Safe한 Wrapped Data Structure를 사용해야 합니다. 예를 들어, 파이썬에서는 threading 모듈과 queue 모듈을 사용하여 Thread Safe한 큐 자료구조를 구현할 수 있습니다.
배열의 길이를 알고 있다면, 조금 더 빠른 Thread Safe 한 연산을 만들 순 없을까요?
배열의 길이를 알고 있다면, 배열의 길이 내에서 인덱스를 직접 계산하는 등의 방법으로, 더 빠른 Thread Safe한 연산을 구현할 수 있습니다. 그러나 이 경우에도 여전히 스레드 동기화에 주의해야 합니다.
사용하고 있는 언어의 자료구조는 Thread Safe 한가요? 그렇지 않다면, Thread Safe 한 Wrapped Data Structure를 제공하고 있나요?
자바스크립트의 대부분의 내장 자료구조는 Thread Safe 하지 않습니다. 그러나 몇몇 라이브러리와 모듈은 Thread Safe 한 Wrapped Data Structure를 제공합니다. 예를 들면, Immutable.js 라이브러리는 Immutable List, Set, Map, Stack, Queue 등의 자료구조를 제공하며, 이들은 Thread Safe 하게 구현되어 있습니다. 또한, Node.js에서는 cluster 모듈을 사용하여 멀티 프로세싱을 지원하므로, 이를 이용하여 Thread Safe 하게 구현할 수도 있습니다.
파이썬의 내장 자료구조는 GIL(Global Interpreter Lock)에 의해 Thread Safe 합니다. 그러나 이는 파이썬이 한 번에 하나의 스레드만 실행하도록 제한하는 기능이기 때문에, 멀티스레드 환경에서 높은 성능을 기대하기 어렵습니다. 따라서 파이썬에서도 멀티스레드 환경에서 안전하게 사용할 수 있는 Thread Safe 한 Wrapped Data Structure를 사용해야 합니다. 예를 들어, 파이썬에서는 threading 모듈과 queue 모듈을 사용하여 Thread Safe한 큐 자료구조를 구현할 수 있습니다.
주소를 검색할 때 사용하는 자료구조
주소를 검색할 때 사용하는 자료구조에는 해시 테이블과 트라이(Trie)가 있습니다.
해시 테이블
해시 테이블은 키-값(key-value) 쌍을 저장하는 자료구조입니다.
키(key)는 주소를 나타내는 문자열이고, 값(value)은 해당 주소에 대한 정보입니다.
해시 함수(hash function)를 사용하여 키를 해시 값(hash value)으로 변환하고, 이를 인덱스로 사용하여 배열에 저장합니다.
이렇게 저장된 데이터를 검색할 때는, 검색하고자 하는 주소의 키를 해시 함수로 변환하여 해당 인덱스를 찾은 뒤, 배열에서 값을 가져옵니다.
이러한 과정에서 해시 충돌(hash collision)이 발생할 수 있으므로, 충돌 해결 방법으로 개방주소방식과 체이닝 방식이 있습니다.
트라이(Trie)
트라이는 문자열 검색에 특화된 자료구조입니다.
각 노드는 문자를 저장하며, 각 노드에서부터 이어지는 모든 문자열을 저장합니다.
이렇게 저장된 데이터를 검색할 때는, 검색하고자 하는 주소를 문자 단위로 나누어 트라이에서 찾아가며, 마지막 노드에 도달하면 해당 주소의 정보를 반환합니다.
이러한 과정에서 트라이는 문자열의 길이에 따라 메모리를 많이 사용하므로, 대용량 데이터에서는 사용이 어려울 수 있습니다.
시간복잡도와 공간복잡도에 대해 설명해 주세요.
시간복잡도는 알고리즘의 수행시간을 분석하는 것이며, 공간복잡도는 알고리즘이 사용하는 메모리 공간의 양을 분석하는 것입니다. 두 복잡도 모두 알고리즘의 효율성을 판단하는 중요한 기준입니다.
빅오, 빅오메가, 빅세타
빅오(Big-O)는 알고리즘의 최악의 경우를 나타내는 표기법으로, 알고리즘의 성능 상한을 나타냅니다. 빅오는 입력 크기 n에 대한 함수 f(n)의 상한을 나타내는데, 즉 알고리즘의 실행시간이 최악의 경우에 f(n) 보다 크지 않다는 것을 의미합니다.
빅오메가(Big-Omega)는 알고리즘의 최선의 경우를 나타내는 표기법으로, 알고리즘의 성능 하한을 나타냅니다. 빅오메가는 입력 크기 n에 대한 함수 g(n)의 하한을 나타내는데, 즉 알고리즘의 실행시간이 최선의 경우에 g(n)보다 작지 않다는 것을 의미합니다.
빅세타(Big-Theta)는 알고리즘의 평균적인 경우를 나타내는 표기법으로, 알고리즘의 성능 상한과 하한이 같은 경우를 나타냅니다. 빅세타는 입력 크기 n에 대한 함수 h(n)이 상한과 하한을 가지는 경우, 알고리즘의 실행시간이 h(n)에 비례한다는 것을 의미합니다.
Big-O를 사용하는 이유가 있을까요?
Big-O는 알고리즘의 성능 상한을 나타내는 가장 느슨한 표기법입니다. 따라서, 빅오 표기법을 사용하면 알고리즘의 실행시간이 얼마나 걸릴지 빠르게 예측할 수 있고, 다양한 알고리즘을 비교할 때에도 유용합니다.
O(1)은O(N^2) 보다빠른 것은 맞지만, 상황에 따라 달라질 수 있습니다. O(1)은 상수 시간 복잡도를 나타내며, 입력 크기에 상관없이 일정한 시간 내에 알고리즘이 실행됩니다. 반면에 O(N^2)는 입력 크기의 제곱에 비례하는 시간이 소요됩니다. 따라서 입력 크기가 작은 경우에는 O(N^2) 알고리즘이 빠를 수도 있습니다. 하지만 일반적으로는 O(1)이 더 빠르며, 입력 크기가 커질수록 O(1)과 O(N^2)의 차이는 커집니다.
'프로그래밍 > CS' 카테고리의 다른 글
| CS스터디 6주차 - 네트워크1(TCP~CORS) (1) | 2023.04.13 |
|---|---|
| CS스터디 5주차 - 알고리즘 (0) | 2023.04.06 |
| 지역성: 시간지역성과 공간지역성 (0) | 2023.03.29 |
| CS스터디 3주차 - 페이징 메모리 (0) | 2023.03.24 |
| CS스터디 2주차 - 인터럽트 데드락 (0) | 2023.03.17 |
댓글