Array & Linked list & Dynamic array
Array는 어떤 자료구조 인가요?
Array는 여러 데이터를 연속된 메모리에 저장할 때 사용하는 자료구조이다.
Dynamic Array를 Linked list와 비교하여 장단점을 설명해 주세요.
Dynamic Array는 인덱스로 빠르게 검색 할 수 있는 장점이 있으나 삽입과 삭제를 할때에는 한개의 요소씩 shift가 일어나기 때문에 linked list보다 느리다는 단점이 있습니다. Linked list는 검색할 때 포인터를 하나씩 찾아야하기 때문에 Dynamic Array보다 느리며, 포인터 노드를 끊고 추가하면 되기 때문에 삽입과 삭제가 빠르다는 장점이 있습니다.
Dynamic Array는 어떤 자료구조 인가요?
Dynamic Array는 데이터가 배열 길이만큼 차지하게 되면 기존의 길이에서 2배로 길이를 동적으로 늘리는 array입니다.
Linked List에 대해서 설명해 주세요.
linked list는 요소와 요소간을 pointer node로 연결해서 리스트를 구현한 자료구조 입니다.
어느 상황에 Linked list를 쓰는게 Array보다 더 나을까요?
노드의 검색보다 삽입과 삭제가 빈번하게 일어날 때 Linked list를 사용하는 것이 좋습니다.
어느 상황에 Array를 쓰는게 Linked list보다 더 나을까요?
노드의 삽입과 삭제보다 검색이 빈번하게 일어날 때 Array를 사용하는 것이 좋습니다.
Array와 Linked List의 memory allocation은 언제 일어나며, 메모리의 어느 영역을 할당 받나요?
Array는 컴파일 단계에서 메모리 할당이 일어납니다. 이를 정적 메모리 할당이라고 합니다. 이것은 스택 메모리 영역에 할당됩니다. Linked list는 런타임 단계에서 노드가 추가될 때 메모리 할당이 일어납니다. 이를 동적 메모리 할당이라고 부릅니다. 이것은 힙 메모리 영역에 할당됩니다.
⭐ Array vs Linked list를 비교해서 설명해주세요
Array는 인덱스로 검색을 할 수 있어 검색이 빠른 장점이 있습니다. 그러나 삽입, 삭제에서는 linked list보다 느린 단점이 있습니다. linked list는 검색은 O(N)으로 배열보다 느리지만 삽입과 삭제를 배열보다 빠르게 할 수 있습니다.
Array-Base 와 List-Base의 경우 어떤 차이가 있나요?
Queue & Stack
Queue는 무슨 자료구조 인가요?
Queue는 먼저 삽입한 데이터가 먼저 삭제가 되는 자료구조 입니다. 예시로는 프로세스 관리나 프린터의 인쇄 대기열과 같은 우선순위가 같은 작업 등이 있습니다.
Stack은 어떤 자료구조 인가요?
stack은 나중에 삽입한 데이터가 먼저 나오는 구조를 가진 자료구조 입니다. 예시로는 실행취소나 웹 브라우저 방문 기록 등이 있습니다.
⭐ Queue vs priority queue를 비교하여 설명해 주세요
큐는 배열로 주로 구현을 하고, 먼저 들어온 데이터가 먼저 처리되지만, 우선순위 큐는 힙 이라는 완전 이진트리를 이용하여 구현되며, 우선순위가 높은 데이터가 먼저 처리됩니다.BST
⭐⭐BST는 어떤 자료구조 인가요?
이진 탐색 트리는 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가 있는 노드만 포함하고, 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드만 포함하는 트리입니다.
BST의 worst case 시간복잡도는 O(n)입니다. 어떠한 경우에 worst case가 발생하나요?
한쪽으로만 쏠린 트리인 편향 트리일때 worst case가 발생합니다.
BST worst case를 해결하는 방법은 무엇인가요
한쪽으로 쏠린 편향 트리를 AVL트리를 이용하여 균형을 맞추는 방법이 있습니다. AVL트리는 스스로 균형을 잡는 이진 탐색 트리입니다.
이진 탐색 트리에서 저장된 정보가 128일 때 탐색횟수는 몇 번 째일까요?
log2의 시간복잡도를 가져 7번입니다.Hash table
⭐⭐ Hash table는 어떤 자료구조 인가요?
해시 테이블은 해시 함수를 사용하여 변환한 값을 index로 삼아 키(kay)와 데이터(value)를 저장하는 자료구조를 말합니다.
좋은 hash function의 조건은 뭘까요?
서로 다른 두 개의 키가 같은 인덱스로 계산되어 충돌이 일어날 수 있는데, 충돌이 일어나지 않는 hash function이 좋은 hash function입니다.
⭐⭐⭐⭐ Hash table에서 collision이 발생하면 어떻게 되나요? 해결방법엔 뭐가 있을까요?
콜리전이 일어나면 두개의 키가 동일한 slot에 해시 됩니다. 이것을 해결하기 위해 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장하는 개방주소법과 한 슬롯당 들어갈 수 있는 value의 수에 제한을 두지 않는 분리연결법을 사용할 수 있습니다.
Hash table에서 worst case에 시간복잡도는 O(n)이라고 했는데 어떤 상황인가요?
collision이 많아질 수록 검색시 시간 복잡도가 O(1)에서 O(n)에 가까워집니다. 콜리전이란 키가 동일한 slot에 해시되는 상황을 뜻합니다.