자료구조는 소프트웨어 개발자 면접에서 자주 나오는 주제 중 하나입니다. 일반적으로 면접에서는 자료구조의 개념, 장단점, 시간 복잡도, 특정 상황에서 어떤 자료구조를 사용하는지에 대해 질문할 수 있습니다.
자료구조란 ?
자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.
1. 배열(Array)
Q : 배열이란 무엇이며, 어떤 상황에서 사용하는 것이 좋나요?
A :
배열은 동일한 타입의 요소들이 연속된 메모리 공간에 저장되는 자료구조입니다. 배열은 인덱스를 사용하여 요소에 접근할 수 있기 때문에, 임의 접근(random access)이 O(1)의 시간 복잡도를 가집니다. 배열은 요소의 개수가 고정되어 있고, 삽입 및 삭제가 적은 경우에 사용하기 좋습니다. 예를 들어, 고정된 크기의 컬렉션을 다루거나, 빈번하게 읽기 작업이 이루어지는 경우 배열을 사용하는 것이 효율적입니다.
2. 연결 리스트(Linked List)
Q : 연결 리스트와 배열의 차이점은 무엇인가요?
A :
연결 리스트는 각 요소가 노드로 구성되어 있으며, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다. 연결 리스트는 동적으로 크기를 변경할 수 있으며, 요소의 삽입 및 삭제가 배열보다 효율적입니다(O(1) 시간 복잡도). 그러나 연결 리스트는 임의 접근이 불가능하며, 요소에 접근하기 위해서는 처음부터 순차적으로 탐색해야 하므로 접근 시간이 O(n)입니다. 배열은 고정된 크기를 가지며 임의 접근이 빠르지만, 요소의 삽입 및 삭제가 비효율적입니다(O(n) 시간 복잡도).
3. 스택(Stack)
Q : 스택의 주요 연산과 사용 예에 대해 설명해 주세요.
A :
스택은 LIFO(Last In, First Out) 구조를 가지는 자료구조입니다. 주요 연산으로는 요소를 추가하는 push 연산과 요소를 제거하는 pop 연산이 있습니다. 스택은 재귀적인 알고리즘 구현, 함수 호출 관리, 문자열 역순 출력, 괄호 유효성 검사 등에 사용됩니다. 예를 들어, 웹 브라우저의 뒤로 가기 기능은 스택을 사용하여 이전 페이지를 추적합니다.
4. 큐(Queue)
Q : 큐와 스택의 차이점은 무엇인가요?
A :
큐는 FIFO(First In, First Out) 구조를 가지는 자료구조입니다. 주요 연산으로는 요소를 추가하는 enqueue 연산과 요소를 제거하는 dequeue 연산이 있습니다. 스택은 LIFO 구조로, 마지막에 추가된 요소가 먼저 제거되는 반면, 큐는 첫 번째로 추가된 요소가 먼저 제거됩니다. 큐는 순차적인 처리, 작업 스케줄링, 데이터 스트림 관리 등에 사용됩니다. 예를 들어, 프린터의 작업 대기열은 큐를 사용하여 처리 순서를 관리합니다.
5. 트리(Tree)
Q : 이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree)의 차이점은 무엇인가요?
A :
이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조입니다. 이진 탐색 트리는 이진 트리의 일종으로, 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가집니다. 이진 탐색 트리는 탐색, 삽입, 삭제 연산이 평균적으로 O(log n)의 시간 복잡도를 가지며, 정렬된 데이터를 효율적으로 관리할 수 있습니다. 이진 트리는 구조가 단순하여 다양한 용도로 사용될 수 있지만, 정렬된 데이터 관리에는 적합하지 않습니다.
6. 해시 테이블(Hash Table)
Q : 해시 테이블의 원리와 사용 예에 대해 설명해 주세요.
A :
해시 테이블은 키-값 쌍을 저장하는 자료구조로, 해시 함수를 사용하여 키를 해시 값으로 변환하고 이를 인덱스로 사용하여 값을 저장합니다. 해시 테이블은 평균적으로 O(1)의 시간 복잡도로 빠른 검색, 삽입, 삭제 연산을 제공합니다. 해시 테이블은 키를 기반으로 빠르게 데이터를 검색해야 하는 경우에 사용됩니다. 예를 들어, 데이터베이스 인덱스, 캐시, 중복 검사 등에 사용됩니다.
7. 그래프(Graph)
Q : 그래프의 종류와 대표적인 탐색 알고리즘에 대해 설명해 주세요.
A :
그래프는 정점(vertices)과 간선(edges)으로 구성된 자료구조입니다. 그래프는 방향성 여부에 따라 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 구분됩니다. 또한, 간선에 가중치가 있는지 여부에 따라 가중치 그래프(Weighted Graph)와 비가중치 그래프(Unweighted Graph)로 나뉩니다. 대표적인 그래프 탐색 알고리즘으로는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다. DFS는 재귀적으로 정점을 방문하며, 스택을 사용하여 구현할 수 있습니다. BFS는 큐를 사용하여 최단 경로를 탐색합니다.
