[CS] CS 면접 대비 : 자료구조 1

기술면접 예상 질문 및 답변

LinkedList와 ArrayList의 차이점에 대해 설명하세요.

LinkedList는 내부적으로 양방향 연결리스트로 구성되어 있습니다. 따라서 원소를 양방향 순회가 가능합니다. 또한 데이터 삽입/삭제 시 가리키는 주소값만 변경해주면 되기 때문에 시간 복잡도가 O(1)로 매우 효율적입니다. 그러나 순차적 접근이기 때문에 조회 속도가 느리다는 단점이 있습니다.

반면에 ArrayList는 기본적으로 배열을 사용하고 있습니다. 배열 기반이므로 인덱스를 가지고 있어서 무작위 접근이 가능하기 때문에 조회가 빠르다는 장점이 있습니다. 그러나 데이터 삽입/삭제 시 나머지 데이터의 위치를 한 칸씩 이동해야 하기 때문에 비효율적이라는 단점이 있습니다.

 

ArrayList와 Array의 차이점에 대해 설명하세요.

배열은 처음 메모리를 할당할 때 크기를 지정해주어야 하며, 지정된 크기를 변경할 수 없습니다. 반면에 ArrayList는 일반 배열과는 달리 크기를 미리 지정하지 않고 동적으로 값을 삽입/삭제할 수 있습니다.

 

해시 테이블의 개념 및 특징과 시간 복잡도를 설명하세요.

해시는 데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 것을 말하며, 해시 테이블은 해시를 통해 매핑된 정보를 가지고 있는 테이블입니다. 해시 과정에서 해시 함수를 구현하여 임의의 길이를 고정된 길이로 바꿔줍니다.

해시 테이블은 key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색 모두 평균적으로 O(1)의 시간복잡도를 가지고 있습니다. 순서, 관계가 있는 배열에는 적합하지 않으며, 해시 테이블을 위한 공간을 미리 만들어두어야 하므로 공간 효율성이 떨어진다는 특징이 있습니다. 또한 해시 함수 의존도가 높아서 적절한 해시 함수를 만드는 것이 중요하며, 해시 함수가 복잡하면 해시 과정이 오래 걸릴 수 있고, 해시 충돌이 발생하게 될 수도 있습니다.

 

해시 충돌을 해결하기 위한 방법에는 무엇이 있나요?

해시 충돌 문제 해결 방법으로는 체이닝, Open Addressing, 선형 탐사, 제곱 탐사 등이 있습니다.

체이닝은 연결리스트를 이용하여 노드를 계속 추가해나가는 방식으로, 제한 없이 계속 연결이 가능하나, 메모리 문제가 발생할 수 있습니다. Open Addressing은 해시 함수로 얻은 키 값에 이미 값이 존재하면 다음 주소에 데이터를 저장하도록 허용하는 것입니다. 선형 탐사는 키 값에 이미 데이터가 존재하면 정해진 고정 폭으로 이동하여 해시 값의 중복을 피하는 방식이고, 제곱 탐사는 정해진 고정 폭의 제곱수로 이동하여 해시 값의 중복을 피하는 방식입니다.

 

Stack과 Queue의 차이점은 무엇인가요?

스택은 마지막에 넣은 것이 먼저 나오는 LIFO 구조입니다. 따라서 호출 시 가장 위에 있는 원소가 반환됩니다. 반면에 큐는 먼저 들어간 것이 먼저 나오는 FIFO 구조입니다.

 

트리 자료구조의 개념을 설명하고, 특징을 3가지 이상 설명하세요.

트리는 값을 가지는 노드와 노드들을 연결하는 간선으로 이루어진 자료구조로, 사이클이 없는 그래프라고 할 수 있습니다.

특징으로는 앞서 말씀드린 것처럼 사이클이 존재할 수 없으며, 노드가 N개일 때 간선은 N-1개 존재한다는 것입니다. 또한 루트에서 어떤 한 노드로 가는 방법은 한 가지만 존재하고, 모든 노드는 자료형으로 표현이 가능합니다.

 

트리 순회 방식에 대해 설명하세요.

트리 순회 방식에는 크게 전위 순회, 중위 순회, 후위 순회 3가지가 있습니다. 첫번째로 전위 순회는 ‘루트→왼쪽 자식→오른쪽 자식’ 순으로 방문하는 것입니다. 두번째로 중위 순회는 ‘왼쪽 자식→루트→오른쪽 자식’ 순으로 방문하는 것입니다. 마지막으로 후위 순회는 ‘왼쪽 자식→오른쪽 자식→루트’ 순으로 방문하는 방식입니다.

 

B-tree와 B+ tree의 각각의 특징은 무엇인가요?

B-tree와 B+ tree는 모두 이진 트리를 확장한 형태입니다. B-tree는 이진 탐색 트리(BST)를 확장한 트리로, 각 노드는 여러 개의 key를 가질 수 있고, 여러 개의 자식 노드를 가질 수 있습니다. 왼쪽 자식 노드의 키는 자신보다 작고, 오른쪽 자식 노드의 키는 자신보다 큰 값을 가집니다. 모든 leaf node는 동일한 depth를 가지고 있으며, b 트리는 스스로 균형을 맞추기 때문에 최악의 경우에도 O(logN)의 검색 성능을 보입니다.

B+ tree는 B-tree를 개량한 구조로, B-tree처럼 모든 leaf node는 동일한 depth를 가집니다. 그러나 B-tree와는 달리 leaf node에 data가 저장되고, non-leaf-node에는 key만 저장됩니다. leaf node 사이는 link로 연결하여 B-tree에 비해 쉬운 순회가 가능합니다. 또한 data가 leaf-node에만 존재하므로 용량이 작고, key 탐색 시 b-tree에 비해 적은 수의 disk-block만 읽어도 된다는 특징이 있습니다.

 

이진 탐색 트리의 데이터 저장 규칙에 대해 설명하세요.

이진 탐색 트리의 노드에 저장된 키는 유일해야 합니다. 그리고 부모의 키가 왼쪽 자식 노드의 키보다 크고, 오른쪽 자식 노드의 키보다 작아야 합니다. 또한 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리가 되어야 한다는 규칙이 있습니다.

 

이진 탐색 트리의 시간복잡도에 대해 자세히 설명하세요.

이진 탐색 트리의 높이를 h라고 하면 이진 탐색 트리의 탐색 연산은 O(h)의 시간복잡도를 가집니다. 이를 노드의 개수 n으로 바꿔보면, 높이가 1 증가할 때마다 노드가 최대 2배로 늘어나기 때문에 O(logn)이 된다고 할 수 있습니다.

 

최대힙과 최소힙에 대해 설명하세요.

힙은 완전 이진 트리의 일종으로, 여러 값들 중 최댓값과 최솟값을 빠르게 찾아내도록 만들어진 자료구조입니다.

최대힙은 최댓값을 구하기 위한 힙 구조로, 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리입니다.

최소힙은 최대힙과 반대로 최소값을 구하기 위한 힙 구조로, 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리입니다.

 

최소 신장 트리에 대해 설명하세요.

신장 트리는 그래프의 모든 정점이 사이클 없이 연결된 형태를 말하며, 최소 신장 트리는 신장 트리 중 간선 가중치의 합이 최소인 것을 말합니다.

 

최소 신장 트리를 만드는 알고리즘 두 가지의 차이점은 무엇인가요?

최소 신장 트리를 만드는 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있습니다.

크루스칼 알고리즘은 간선을 기준으로 하는 것으로, 간선을 가중치 오름차순 정렬하고, 간선의 가중치가 가장 작은 것부터 검토하여, 그래프에 사이클이 생기지 않는 경우 해당 간선을 추가하며 최소 신장 트리를 만들어주는 알고리즘입니다. O(ElogE)의 시간복잡도를 가집니다.

프림 알고리즘은 정점을 기준으로 하는 것으로, 하나의 정점을 기준으로 해당 정점에 연결된 간선 중 가중치가 가장 작은 것부터 그래프에 사이클이 발생하지 않도록 연결하는 방식입니다. O(ElogV)의 시간복잡도를 가집니다.

 

그래프의 정의와 구현 방법에 대해 설명하세요.

그래프는 정점과 간선의 집합을 말하며, 각 정점에 연결된 간선의 개수를 degree라고 합니다. 그래프를 구현하는 방법에는 인접 행렬을 이용하는 방식과 인접 리스트를 이용하는 방식이 있습니다.

인접 행렬은 정방 행렬을 사용하여 구현하는데, 간선의 개수가 많은 경우 적절한 방법입니다. 간선의 개수와는 무관하게 O(V^2)의 공간 복잡도를 가집니다.

인접 리스트는 연결 리스트를 이용하는 방법으로, 간선의 개수가 적은 경우 적절한 방법입니다. 인접 리스트를 쭉 따라가보며 연결된 정점을 찾아야 하므로 연결 여부를 확인하는데 오래 걸립니다. O(E+V)의 공간 복잡도를 가집니다.

 

그래프 탐색 방법에는 무엇이 있나요?

그래프 탐색 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.

깊이 우선 탐색은 임의의 한 정점에서 연결되어 있는 한 정점으로만 나아가, 연결된 정점의 끝까지 탐색하는 것입니다. 연결 가능한 정점이 있을 때까지 계속 연결하다가 더 이상 연결된 정점이 없으면 바로 전 단계의 정점으로 돌아가서 연결 가능한 정점이 있는지 확인합니다. stack/재귀를 이용하여 구현 가능합니다.

너비 우선 탐색은 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아가는 방식으로, queue를 이용하여 구현 가능합니다. 탐색 시작점을 queue에 넣고, queue에 저장된 값을 하나씩 빼면서 빼낸 정점에 연결된 정점을 queue에 넣는 과정을 반복합니다. 너비 우선 탐색을 통해 구한 경로는 ‘최단 경로’가 됩니다.