면접대비 질문 정리: 자료구조

1. 배열(Array)과 연결 리스트(Linked List)의 차이점은 무엇인가?

✅ 답변

배열, 위키백과

배열은 고정된 크기의 연속적인 메모리 공간에 데이터를 저장하는 자료구조로, 인덱스를 통해 빠르게 접근할 수 있습니다. 하지만 크기를 미리 정해야 하며, 크기 변경이 불가능합니다.

 

연결 리스트, 위키백과

연결 리스트는 각 요소가 데이터와 포인터로 구성되어 있어 크기 변경이 자유롭고, 삽입 및 삭제가 효율적입니다. 그러나 요소 접근 속도가 느리고, 추가 메모리 공간이 필요합니다.

 

2. 스택(Stack)과 큐(Queue)의 차이점은 무엇인가?

✅ 답변

스택, 위키백과

스택은 후입선출(LIFO) 방식으로, 가장 마지막에 삽입된 요소가 먼저 제거됩니다.

큐, 위키백과

큐는 선입선출(FIFO) 방식으로, 가장 먼저 삽입된 요소가 먼저 제거됩니다.

3. 이진 탐색 트리(Binary Search Tree)란 무엇인가?

✅ 답변

이진 탐색 트리, 위키백과

이진 탐색 트리는 각 노드가 최대 두 개의 자식을 가지는 트리 구조로, 왼쪽 자식은 부모보다 작은 값을, 오른쪽 자식은 부모보다 큰 값을 가집니다. 이 특징 덕분에 탐색, 삽입, 삭제 등의 연산을 평균적으로 `O(log n)`의 시간 복잡도를 가집니다.

 

4. 힙(Heap) 자료구조란 무엇인가?

✅ 답변

힙, 위키백과 / https://www.hello-algo.com/en/chapter_heap/heap/

힙은 완전 이진 트리로, 부모 노드의 값이 자식 노드의 값보다 크거나 작은 성질을 가집니다. 

최대 힙은 부모가 자식보다 크고, 최소 힙은 부모가 자식보다 작습니다. 주로 우선순위 큐를 구현할 때 사용됩니다.

 

참고: https://www.hello-algo.com/en/chapter_heap/heap/

 

 

5. 해시 테이블(Hash Table)에서 충돌(Collision)을 처리하는 방법은 무엇인가?

해시 테이블, 위키백과

✅ 답변
충돌을 처리하는 방법은 여러 가지가 있으며, 대표적인 방법은 체이닝(Chaining)과 개방 주소법(Open Addressing)입니다.
체이닝은 각 해시 버킷이 링크드 리스트를 가짐으로써 충돌을 처리합니다.
개방 주소법은 충돌 발생 시 다른 빈 공간을 찾아 데이터를 저장하는 방법으로, 선형 탐색, 이차 탐색, 이중 해싱 등이 있습니다.

 

6. 트리(Tree) 자료구조의 특징은 무엇인가?

✅ 답변
트리는 계층적 구조를 갖는 자료구조로, 하나의 루트 노드에서 시작하여 여러 자식 노드로 확장됩니다.

트리는 순차적이지 않으며, 자식 노드는 여러 개일 수 있습니다. 트리 구조에서 각 노드는 데이터와 자식 노드를 참조하는 포인터를 가집니다.

 

7. 그래프(Graph) 자료구조란 무엇인가?

✅ 답변

그래프,위키백과

그래프는 노드(정점)와 그 노드를 연결하는 간선(엣지)로 이루어진 자료구조입니다.

그래프는 유향 그래프와 무향 그래프, 가중치 그래프와 비가중치 그래프로 나눌 수 있습니다. 그래프는 트리와 달리 사이클을 가질 수 있습니다.

 

 

8. 너비 우선 탐색(BFS, Breadth First Search)과 깊이 우선 탐색(DFS, Depth First Search)의 차이점은 무엇인가?

✅ 답변

BFS, 위키백과

너비 우선 탐색(BFS)는 큐를 사용하여 레벨 순서대로 노드를 탐색합니다. 가장 가까운 노드부터 차례대로 방문하므로 최단 경로를 찾는 데 유리합니다.

DFS, 위키백과

깊이 우선 탐색(DFS)는 스택을 사용하거나 재귀적으로 구현하며, 한 방향으로 끝까지 탐색한 후 다시 돌아가며 다른 방향을 탐색합니다.

 

 

9. 이진 힙(Binary Heap)에서 삽입(insert)과 삭제(delete) 연산의 시간 복잡도는 어떻게 되는가?

✅ 답변
삽입 연산의 시간 복잡도는 `O(log n)`입니다. 힙에서 새 노드를 삽입할 때는 마지막에 노드를 추가하고, 힙 속성을 유지하기 위해 상향 조정(heapify-up)을 합니다.
삭제 연산의 시간 복잡도도 `O(log n)`입니다. 루트 노드를 삭제한 후, 마지막 노드를 루트로 올리고 하향 조정(heapify-down)을 수행합니다.

 

 

10. 레드-블랙 트리(Red-Black Tree)란 무엇인가?

✅ 답변

레드-블랙 트리, 위키백과

레드-블랙 트리는 이진 탐색 트리의 일종으로, 각 노드는 레드 또는 블랙 색을 가지고, 다음의 조건을 만족합니다.
1. 루트는 블랙이다.
2. 모든 리프 노드는 블랙이다.
3. 레드 노드는 연속해서 나타날 수 없다.
4. 각 노드에서 리프 노드까지의 블랙 노드의 수는 같다.
레드-블랙 트리는 균형을 유지하여 최악의 경우에도 탐색 시간이 `O(log n)`입니다.

 

 

11. 이진 탐색(Binary Search) 알고리즘의 시간 복잡도는 무엇인가?

✅ 답변
이진 탐색 알고리즘은 정렬된 배열에서 값을 찾을 때 사용하는 알고리즘으로, 매번 검색 범위를 절반으로 줄입니다. 시간 복잡도는 `O(log n)`입니다.

 

 

12. 큐(Queue)의 연산 중 enqueue와 dequeue의 시간 복잡도는 어떻게 되는가?

✅ 답변
enqueue: 큐에 새로운 요소를 삽입하는 연산으로, 시간 복잡도는 `O(1)`입니다.
dequeue: 큐에서 요소를 제거하는 연산으로, 시간 복잡도는 `O(1)`입니다. 큐는 선입선출(FIFO) 방식으로 작동하므로 연산이 간단합니다.

 

 

13. 트리에서 균형잡힌 트리(Balanced Tree)란 무엇인가?

✅ 답변
균형잡힌 트리는 각 노드의 자식 트리들의 높이 차이가 일정 범위 내에 있는 트리입니다. 예를 들어, AVL 트리는 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1인 트리입니다. 균형잡힌 트리는 탐색, 삽입, 삭제 시 `O(log n)`의 시간 복잡도를 보장합니다.

 

 

14. 힙(Heap) 자료구조에서 부모 노드와 자식 노드의 관계는 무엇인가?

✅ 답변
힙은 이진 트리로, 부모 노드가 자식 노드보다 크거나(최대 힙) 작아야(최소 힙) 합니다. 즉, 최대 힙에서는 부모가 자식보다 크고, 최소 힙에서는 부모가 자식보다 작습니다. 이 특성을 통해 힙은 우선순위 큐를 구현할 때 유용합니다.

 

 

15. 이진 탐색 트리에서 삽입과 삭제 연산의 시간 복잡도는 어떻게 되는가?

✅ 답변
이진 탐색 트리에서 삽입과 삭제는 트리의 균형 상태에 따라 다르지만, 평균적으로 시간 복잡도는 `O(log n)`입니다. 하지만 최악의 경우(트리가 편향될 때)는 `O(n)`이 될 수 있습니다.

 

 

16. 트리에서 트리 순회(Tree Traversal)의 종류에는 어떤 것이 있나요?

✅ 답변
트리 순회 방법에는 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order)가 있습니다.
전위 순회: 루트 -> 왼쪽 자식 -> 오른쪽 자식
중위 순회: 왼쪽 자식 -> 루트 -> 오른쪽 자식
후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 루트

 

 

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

✅ 답변
우선순위 큐는 큐의 일종으로, 각 요소가 우선순위를 가지고 있으며, 우선순위가 높은 요소가 먼저 처리됩니다. 일반적으로 힙을 기반으로 구현됩니다. 우선순위 큐는 우선순위가 높은 데이터가 먼저 나오는 특징이 있어, 작업 스케줄링이나 Dijkstra 알고리즘 등에 사용됩니다.

 

 

18. 힙(Heap)에서 heapify란 무엇인가요?

✅ 답변
heapify는 힙 구조에서 특정 노드를 힙 속성을 만족하도록 조정하는 연산입니다.
상향 조정(heapify-up): 삽입 시 새 노드가 부모보다 크거나 작게 조정됩니다.
하향 조정(heapify-down): 삭제 시 루트 노드를 삭제하고, 자식 노드와 비교하여 힙 속성을 만족하도록 재배치됩니다.

 

 

19. 동적 배열(Dynamic Array)과 정적 배열(Static Array)의 차이점은 무엇인가요?

✅ 답변
정적 배열은 크기가 고정되어 있어 배열 크기를 미리 정의해야 하며, 크기를 변경할 수 없습니다.
동적 배열은 크기가 가변적이며, 크기가 부족하면 배열을 자동으로 확장할 수 있습니다. JavaScript의 Array, Python의 list 등이 동적 배열의 예입니다.

 

 

20. 연결 리스트에서 이중 연결 리스트(Doubly Linked List)와 단일 연결 리스트(Singly Linked List)의 차이점은 무엇인가요?

✅ 답변
단일 연결 리스트는 각 노드가 데이터와 하나의 포인터(다음 노드를 가리키는)를 가지고 있습니다.
이중 연결 리스트는 각 노드가 데이터와 두 개의 포인터(이전 노드와 다음 노드를 가리키는)를 가지고 있어 양방향 탐색이 가능합니다. 이중 연결 리스트는 삽입과 삭제에서 더 유연하지만, 추가적인 메모리 공간이 필요합니다.

 

 

21. 트라이(Trie) 자료구조는 무엇인가요?

✅ 답변
트라이는 문자열 검색에 최적화된 트리 구조입니다. 각 노드는 문자열의 한 문자에 대응하며, 경로를 따라가며 문자열을 찾습니다. 문자열의 접두사를 효율적으로 처리할 수 있어, 자동완성 기능이나 사전 구현에 자주 사용됩니다.

 

 

22. 해시 테이블(Hash Table)에서 해시 함수(Hash Function)의 역할은 무엇인가요?

✅ 답변
해시 함수는 주어진 키를 고유한 해시 값으로 변환하여 데이터를 저장할 인덱스를 결정하는 함수입니다. 해시 함수는 효율적인 검색을 위해 잘 분배된 해시 값을 생성해야 하며, 충돌을 최소화하는 것이 중요합니다.

 

 

23. AVL 트리(AVL Tree)란 무엇인가요?

✅ 답변

AVL 트리, 위키백과

AVL 트리는 이진 탐색 트리의 일종으로, 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하로 유지되도록 균형을 맞추는 트리입니다. 균형을 맞추기 위해 회전(Rotation) 연산을 사용하며, 이를 통해 삽입과 삭제 시에도 `O(log n)` 시간 복잡도를 보장합니다.

 

 

24. 이진 검색 트리에서 순회(Traversal)는 어떤 경우에 유용하게 사용되나요?

✅ 답변
이진 검색 트리에서 순회는 데이터를 정렬된 순서로 출력하거나, 특정 조건에 맞는 데이터를 찾을 때 유용합니다.

예를 들어, 중위 순회를 사용하면 이진 검색 트리의 데이터를 오름차순으로 정렬된 상태로 출력할 수 있습니다.

 

 

25. 그래프에서 간선(Edge)의 종류에는 무엇이 있나요?

✅ 답변
그래프에서 간선은 다음과 같이 나눌 수 있습니다.
유향 간선(Directed Edge): 방향성이 있는 간선으로, 한 노드에서 다른 노드로의 연결을 나타냅니다.
무향 간선(Undirected Edge): 방향성이 없는 간선으로, 두 노드 간의 상호 연결을 나타냅니다.
가중치 간선(Weighted Edge): 간선에 가중치가 부여된 간선으로, 주로 최단 경로 알고리즘에서 사용됩니다.

 

 

26. 깊이 우선 탐색(DFS)에서 백트래킹(Backtracking)은 무엇인가요?

✅ 답변
백트래킹은 깊이 우선 탐색을 수행하면서 유망하지 않은 경로를 빨리 차단하고 이전 상태로 돌아가 다른 경로를 탐색하는 기법입니다. 이를 통해 해결할 수 없는 부분은 일찍 포기하고 더 나은 해결책을 찾아갑니다. 예를 들어, 미로 찾기나 퍼즐 문제 해결에 사용됩니다.

 

 

27. 배열(Array)에서 요소를 삽입하거나 삭제할 때의 시간 복잡도는 어떻게 되나요?

✅ 답변
배열에서 요소를 삽입하거나 삭제할 때의 시간 복잡도는 연속적인 메모리 공간이므로, 삽입이나 삭제된 요소 이후의 모든 요소를 이동시켜야 합니다. 따라서 삽입과 삭제 연산의 시간 복잡도는 `O(n)`입니다. 단, 배열의 끝에 삽입하는 경우는 `O(1)`입니다.

 

 

28. 큐(Queue)에서 리어(Rear)와 프론트(Front)의 차이점은 무엇인가요?

✅ 답변
프론트(Front): 큐에서 가장 먼저 나올 요소가 위치한 곳입니다. 큐에서 데이터를 제거할 때 프론트에서부터 삭제됩니다.
리어(Rear): 큐에서 가장 마지막에 삽입된 요소가 위치한 곳입니다. 큐에 데이터를 삽입할 때 리어에 추가됩니다.

 

 

29. 그래프에서 너비 우선 탐색(BFS)을 수행할 때 사용하는 자료구조는 무엇인가요?

✅ 답변
너비 우선 탐색(BFS)은 큐(Queue) 자료구조를 사용하여 구현합니다. 큐를 이용해 현재 노드를 방문한 후, 인접한 노드들을 큐에 넣고, 큐가 빌 때까지 반복하여 노드를 탐색합니다.

 

 

30. AVL 트리에서 회전(Rotation)이란 무엇인가요?

✅ 답변
회전은 AVL 트리에서 불균형을 해결하기 위해 사용하는 연산입니다. 좌회전(Left Rotation)과 우회전(Right Rotation)을 사용하여 불균형을 수정합니다. 회전을 통해 트리의 높이를 조절하고 균형을 맞출 수 있습니다.