트리

트리(Tree)란 무엇인가요

트리는 노드들이 부모-자식 관계를 가지며 계층적으로 연결된 비선형 자료구조입니다.

이진 트리(Binary Tree)란 무엇인가요

각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리입니다. 일반적으로 왼쪽 자식과 오른쪽 자식으로 구분합니다.

이진 탐색 트리(BST)란 무엇인가요

이진 탐색 트리는 일반적으로 각 노드를 기준으로 왼쪽 서브트리에는 더 작은 값, 오른쪽 서브트리에는 더 큰 값을 저장하는 이진 트리입니다.

BST에서 탐색, 삽입, 삭제의 시간 복잡도는 어떻게 되나요

트리가 균형 잡혀 있다면 탐색, 삽입, 삭제가 평균적으로 O(log N)입니다. 하지만 한쪽으로 치우친 트리에서는 연결 리스트와 비슷한 구조가 되어 최악의 경우 O(N)이 될 수 있습니다.

균형 이진 탐색 트리란 무엇인가요

트리가 한쪽으로 지나치게 치우치지 않도록 높이를 일정 수준으로 유지하는 이진 탐색 트리입니다. 이를 통해 탐색, 삽입, 삭제를 O(log N) 수준으로 유지할 수 있습니다.

AVL Tree란 무엇인가요

AVL Tree는 각 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지하는 균형 이진 탐색 트리입니다. 삽입이나 삭제 후 필요하면 회전 연산을 통해 균형을 맞춥니다.

Red-Black Tree란 무엇인가요

Red-Black Tree는 각 노드에 Red 또는 Black 속성을 부여하고 정해진 규칙을 통해 트리의 균형을 유지하는 이진 탐색 트리입니다. 완벽한 균형보다는 적절한 균형을 유지해 주요 연산을 O(log N)에 수행합니다.

트리의 전위, 중위, 후위 순회를 설명해주세요

현재 노드를 언제 방문하느냐에 따라 구분합니다. 전위는 Root→Left→Right, 중위는 Left→Root→Right, 후위는 Left→Right→Root 순서로 방문합니다.

Root의 위치로 기억하면 편하다(Left는 무조건 Right보다 먼저).

전위 : Root - Left - Right
중위 : Left - Root - Right
후위 : Left - Right - Root

BST를 중위 순회하면 어떤 결과가 나오나요

BST는 왼쪽에 작은 값, 오른쪽에 큰 값이 있기 때문에 중위 순회하면 데이터를 오름차순으로 방문할 수 있습니다.

힙 / 우선순위 큐

힙(Heap)이란 무엇인가요

힙은 최댓값 또는 최솟값을 빠르게 찾기 위해 사용하는 완전 이진 트리 기반의 자료구조입니다. 최대 힙과 최소 힙으로 나눌 수 있습니다.

힙은 일반적인 이진 탐색 트리와 어떤 차이가 있나요

BST는 왼쪽 < 부모 < 오른쪽이라는 정렬 관계를 이용해 특정 값을 탐색하는 구조이고, 힙은 부모와 자식 사이의 대소 관계만 보장하여 최댓값이나 최솟값을 빠르게 찾는 구조입니다.

힙에서 삽입과 삭제가 O(log N)인 이유는 무엇인가요

삽입이나 루트 삭제 후 힙의 규칙을 복구하기 위해 부모 또는 자식과 값을 교환하며 트리의 높이만큼 이동합니다. 완전 이진 트리의 높이가 O(log N)이므로 삽입과 삭제도 O(log N)입니다.

우선순위 큐(Priority Queue)란 무엇인가요

우선순위 큐는 들어온 순서가 아니라 각 데이터에 설정된 우선순위에 따라 먼저 처리되는 자료구조입니다. 일반적으로 힙을 이용해 효율적으로 구현합니다.

일반 Queue와 Priority Queue의 차이는 무엇인가요

일반 Queue는 먼저 들어온 데이터가 먼저 나오는 FIFO 방식이고, Priority Queue는 들어온 순서와 관계없이 우선순위가 높은 데이터를 먼저 처리합니다.

Priority Queue를 Heap으로 구현하는 이유는 무엇인가요

힙을 사용하면 가장 우선순위가 높은 데이터는 O(1)에 확인하고, 삽입과 제거는 O(log N)에 처리할 수 있기 때문에 Priority Queue를 효율적으로 구현할 수 있습니다.

그래프

그래프(Graph)란 무엇인가요

그래프는 정점(Vertex)과 정점들을 연결하는 간선(Edge)으로 구성된 비선형 자료구조입니다.

그래프와 트리의 차이는 무엇인가요

트리는 계층 구조를 가지며 일반적인 트리에서는 두 노드 사이의 경로가 하나이고 사이클이 없습니다. 그래프는 이러한 제약이 없어 사이클이나 여러 경로를 가질 수 있습니다.

인접 행렬과 인접 리스트의 차이는 무엇인가요

인접 행렬은 2차원 배열을 이용해 정점 간 연결 여부를 저장하고, 인접 리스트는 각 정점마다 연결된 정점들의 목록을 저장하는 방식입니다.

인접 행렬과 인접 리스트의 각각의 장단점은 무엇인가요

인접 행렬은 두 정점의 연결 여부를 O(1)에 확인할 수 있지만 O(V²)의 메모리가 필요합니다. 인접 리스트는 실제 존재하는 간선 위주로 저장해 메모리가 효율적이지만 특정 두 정점의 연결 여부를 확인하려면 연결 목록을 탐색해야 합니다.

BFS / DFS

BFS란 무엇인가요

BFS(Breadth-First Search)는 시작 정점에서 가까운 정점부터 너비 방향으로 탐색하는 그래프 탐색 알고리즘입니다. 일반적으로 Queue를 사용하여 구현합니다.

DFS란 무엇인가요

DFS(Depth-First Search)는 한 방향으로 최대한 깊게 탐색한 후 더 이상 진행할 수 없으면 돌아와 다른 경로를 탐색하는 알고리즘입니다. Stack이나 재귀를 이용해 구현할 수 있습니다.

BFS와 DFS의 차이는 무엇인가요

BFS는 가까운 노드부터 탐색하는 너비 우선 방식이고, DFS는 한 경로를 끝까지 탐색한 뒤 돌아오는 깊이 우선 방식입니다. BFS는 Queue, DFS는 Stack이나 재귀를 주로 사용합니다.