기술면접 | 데이터구조

index, node, 탐색, 삽입, 삭제먼저, Array는 연속된 메모리 공간을 사용하고, Linked List는 연속되지 않은 메모리 공간을 사용합니다.그래서 Array의 경우, index를 통해 각 요소에 접근할 수 있고, 탐색에 필요한 시간복잡도는 O(1)입니다

LIFO, FIFOStack은 자료의 입력과 출력을 한 곳으로 제한한 자료구조입니다. 그래서 LIFO(Last In First Out) 구조로, 마지막에 삽입된 데이터가 먼저 삭제되는 자료구조입니다.반면 Queue는 자료의 입력과 출력을 양쪽 끝으로 제한한 자료구조입니

비선형, Node, Edge, Root Node, Terminal Node, Internal Node, level트리는 비선형 자료구조로, 계층적 관계를 표현하는 자료구조입니다. 대표적으로 이진트리나 이진탐색트리 등이 그 예시입니다. 트리는 Node와 이를 잇는 Edg

2개의 Sub Tree, 재귀적, level, heightBinary Tree는 Root Node를 기준으로 2개의 Sub Tree로 나뉘어집니다. 그리고 재귀적으로 그 나누어진 Tree도 모두 Binary Tree이어야 합니다. 즉, 모든 노드가 최대 2개의 자식을

key, 탐색, 편향 트리, worst caseBinary Search Tree는 효율적인 탐색을 위해 고안된 binary tree의 일종입니다. Binary Search Tree는 binary tree에 몇 가지 규칙을 추가하여 특정 데이터를 쉽게 찾을 수 있게 만듭

완전이진트리,최소힙,최대힙,최소값,최댓값Heap은 Tree의 구조로 이루어진 자료구조로, 완전이진트리 자료구조입니다. 대표적으로 최소힙과 최대힙이 존재하며, 최소힙은 각 Node에 해당하는 값이 자식 Node의 값보다 작거나 같은 Binary Tree입니다. 이때, r

균형 트리, 편향 트리, balance factor평균적으로 Binary Search Tree에서 탐색에 있어 시간복잡도는 O(log n)입니다. 하지만 편향 트리(skewed tree)가 만들어지면, 최악의 경우 탐색에 있어 O(n)의 시간복잡도를 가집니다. 이 문제

회전,탐색,삽입,삭제AVL Tree는 스스로 균형을 잡는 binary search tree로, 왼쪽 sub tree의 높이와 오른쪽 sub tree의 높이의 차이를 표현하는 Balance Factor가 2 이상일 때 회전을 통해 균형을 맞춥니다. binary searc

탐색,삽입,삭제,Black-height,NIL

sub tree 개수,요소의 개수,요소 내부 오름차순,균형, Tree heightMultiway Search Tree는 한 Node 내에 최대 m-1개의 요소와 m개의 자식을 갖는 Tree 구조입니다. Binary Search Tree는 이 m 값이 2인 Tree라고

balance, inner node, leaf node, multiway search tree, key, data, blockB-Tree는 각 Node에 여러개의 Key와 Child를 가질 수 있는 multiway search tree입니다. 이때 모든 Leaf Nod

hash, index, collision, hashcode, hash function, key, Open Address , Separate Chaining hash table은 data를 hash function을 통해 hash code로 변환하고 고유의 key를 생성

정점(Vertex), 간선(edge), 방향성, 무방향성, 가중치, degree, cycle, 네트워크그래프는 vertex와 이를 연결하는 간선(edge)로 이루어져있는 자료구조입니다. 연결관계에 있어서 방향성이 있는 그래프와 방향성이 없는 그래프로 나눌 수 있습니다.

queue, stack, 정점, 간선BFS는 너비 우선 탐색으로, 그래프 상에서 시작되는 정점을 기준으로, 연결되어 있는 모든 정점을 탐색하는 알고리즘입니다. 마치 Tree의 Level Order 순회처럼 작동하며, 실제 구현에서는 queue를 사용하여 다음 탐색할 정

최소 신장 트리에 대해 설명하세요 Keyword 신장 트리, cycle, edge weight, Kruskal, Prim Script 먼저 신장 트리(spanning tree)는 원 그래프 기준으로 모든 정점이 cycle 없이 연결된 형태를 말합니다. 이 신장 트리는

양의 가중치, 최단거리 테이블, 우선순위 큐BFS가 가중치가 없는 상황에서 그래프에서의 최단거리 탐색에 쓰인다면, 다익스트라 알고리즘은 각 간선이 서로 다른 양의 가중치로 이루어진 그래프에서 특정 지점에서 특정 지점까지의 최단거리 탐색에 쓰입니다.먼저, 시작 정점의 거

방향성, 비순환, 선후관계, InDegree위상정렬은 방향성 비순환 그래프에서 선후관계를 고려한 정렬 알고리즘입니다. 예를 들어 A 정점에서 B 정점으로 향하는 간선이 존재할 때, A가 B보다 앞쪽에 위치하도록 정렬하도록 설계된 알고리즘입니다. 위상정렬의 핵심은 특정