자료구조 핵심 정리

🎯 학습 목표

이 강을 마치면 다음을 할 수 있습니다.

• 7가지 핵심 자료구조의 원리와 시간복잡도를 면접 답변 수준으로 설명할 수 있습니다.
• 각 자료구조를 언제 선택해야 하는지 판단 기준을 말할 수 있습니다.
• 면접에서 자주 나오는 자료구조 질문에 구조적으로 답변할 수 있습니다.
• "모르는 자료구조 질문"을 받았을 때 아는 것과 연결해 답변하는 법을 알 수 있습니다.

📋 자료구조 면접의 특성 이해

이 섹션에서는 자료구조 질문이 면접에서 왜 나오고, 어떤 관점에서 답변해야 하는지 살펴보겠습니다.

면접관이 "배열과 연결 리스트의 차이가 무엇인가요?"라고 묻는 이유는 단순히 정의를 외웠는지 확인하기 위해서가 아닙니다. 그들이 알고 싶은 것은 당신이 문제 상황에서 적절한 도구를 선택할 수 있는가입니다. 따라서 자료구조 답변의 핵심은 항상 "언제, 왜 이것을 선택하는가"와 "트레이드오프는 무엇인가"를 포함해야 합니다.

자료구조 질문에 답할 때 사용하는 일관된 구조입니다. ① 한 줄 정의 → ② 핵심 특성(어떻게 동작하는가) → ③ 시간복잡도(삽입·삭제·탐색) → ④ 언제 사용하는가 → ⑤ 트레이드오프(장단점). 이 5단계를 외워두면 어떤 자료구조가 나와도 답변 프레임이 생깁니다.

📊 7가지 핵심 자료구조 완전 정리

이 섹션에서는 기술 면접에서 가장 자주 등장하는 7가지 자료구조를 면접 답변 형식으로 정리하겠습니다.

① 배열(Array)

배열은 동일한 타입의 데이터를 메모리상에 연속적으로 저장하는 자료구조입니다. 핵심 특성은 인덱스를 통한 O(1) 임의 접근입니다. 시작 주소와 인덱스를 알면 한 번의 연산으로 원하는 위치에 접근할 수 있기 때문입니다. 반면 중간 삽입·삭제는 뒤의 원소를 모두 이동시켜야 해서 O(n)이 걸립니다. 데이터를 인덱스로 자주 접근해야 할 때, 크기가 고정되어 있을 때 최적입니다.

② 연결 리스트(Linked List)

각 데이터가 노드(데이터 + 다음 노드 참조) 단위로 존재하며, 메모리가 연속적이지 않아도 됩니다. 삽입·삭제가 O(1)이지만(위치를 알 때), 탐색은 처음부터 순차 접근해야 하므로 O(n)입니다. 삽입·삭제가 빈번하고 크기가 동적으로 변하는 상황에 적합합니다.

연산	배열	연결 리스트
접근(인덱스)	O(1) ✅	O(n) ❌
탐색	O(n)	O(n)
앞/중간 삽입	O(n) ❌	O(1) ✅
앞/중간 삭제	O(n) ❌	O(1) ✅
메모리	연속 (캐시 효율↑)	분산 (포인터 추가)

③ 스택(Stack)

스택은 LIFO(Last In First Out) — 마지막에 넣은 것을 먼저 꺼내는 자료구조입니다. push(삽입)·pop(꺼내기)·peek(최상위 조회) 모두 O(1)입니다. 함수 호출 스택, 브라우저 뒤로 가기, 실행 취소(Ctrl+Z), 괄호 유효성 검사에 활용됩니다. 면접 단골 질문: "재귀 함수의 깊이가 너무 깊어지면 왜 오류가 발생하는가?" → 함수 호출 스택이 한정된 크기를 초과하는 StackOverflow가 발생합니다.

④ 큐(Queue)

큐는 FIFO(First In First Out) — 먼저 넣은 것을 먼저 꺼내는 자료구조입니다. enqueue(뒤에 추가)·dequeue(앞에서 꺼내기) 모두 O(1)입니다. BFS(너비 우선 탐색), 프린터 작업 대기열, 메시지 큐(Kafka, RabbitMQ)가 대표적 활용입니다. 우선순위 큐(Priority Queue)는 큐에 우선순위를 부여해 높은 우선순위 항목을 먼저 꺼냅니다. 힙(Heap)으로 구현하며 삽입·삭제 O(log n), 최솟값 조회 O(1)입니다.

⑤ 트리(Tree)

트리는 노드들이 부모-자식 계층 관계로 연결된 비선형 자료구조입니다. 사이클이 없는 연결 그래프이기도 합니다. 면접에서 가장 자주 나오는 트리는 이진 탐색 트리(BST)입니다. BST는 왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 유지해 균형 잡힌 경우 탐색·삽입·삭제 모두 O(log n)이 가능합니다. 단, 정렬된 순서로 삽입하면 편향 트리가 되어 O(n)으로 성능이 저하됩니다. 이를 해결하기 위해 Red-Black Tree, AVL Tree 같은 자가 균형 BST가 존재합니다.

트리 순회 3가지는 면접에서 매우 자주 나옵니다. 전위 순회(Pre-order)는 루트 → 왼쪽 → 오른쪽 순서입니다. 중위 순회(In-order)는 왼쪽 → 루트 → 오른쪽 순서이며, BST에서 중위 순회를 하면 오름차순 정렬 결과가 나옵니다. 후위 순회(Post-order)는 왼쪽 → 오른쪽 → 루트 순서입니다.

⑥ 그래프(Graph)

그래프는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조입니다. 트리와 달리 사이클이 있을 수 있고, 방향·무방향 그래프로 나뉩니다. 소셜 네트워크, 지도, 의존성 그래프가 대표적입니다. 코드로 표현하는 두 가지 방식의 차이를 알아야 합니다.

• 인접 행렬(Adjacency Matrix): V×V 2차원 배열. 간선 존재 확인 O(1)이지만 공간 O(V²)로 낭비.
• 인접 리스트(Adjacency List): 각 정점마다 연결된 정점 목록. 공간 O(V+E)로 효율적. 대부분의 경우 인접 리스트가 적합합니다.

그래프 탐색: DFS(깊이 우선 탐색)은 스택 또는 재귀로 구현, 경로 탐색·위상 정렬에 활용합니다. BFS(너비 우선 탐색)은 큐로 구현, 최단 경로 탐색에 활용합니다.

⑦ 해시 테이블(Hash Table)

해시 테이블은 키(Key)를 해시 함수로 변환해 배열 인덱스로 사용하는 자료구조입니다. 평균 O(1)에 삽입·탐색·삭제가 가능합니다. 충돌(Collision)은 서로 다른 키가 같은 해시값을 가질 때 발생합니다. 해결 방법은 체이닝(같은 인덱스에 연결 리스트)과 오픈 어드레싱(빈 슬롯 찾기) 두 가지입니다. 충돌이 많아지면 최악 O(n)이 됩니다. Java의 HashMap, Python의 dict가 해시 테이블 기반입니다.

🎯 자료구조 선택 판단 기준

이 섹션에서는 실무와 면접 모두에서 적용할 수 있는 자료구조 선택 기준을 살펴보겠습니다.

면접에서 "어떤 자료구조를 사용하겠는가?"라는 질문을 받으면, 다음 순서로 생각하면 됩니다.

1. 주요 연산이 무엇인가? 탐색이 많은가, 삽입/삭제가 많은가, 순서가 중요한가?
2. 데이터 크기와 메모리 제약이 있는가?
3. 임의 접근이 필요한가, 순차 접근으로 충분한가?

상황	추천 자료구조	이유
인덱스 기반 빠른 접근	배열	O(1) 임의 접근
빈번한 삽입·삭제	연결 리스트	O(1) 삽입·삭제
되돌리기, 후입선출	스택	LIFO 구조
순서 보장 처리, BFS	큐	FIFO 구조
키로 빠른 탐색	해시 테이블	평균 O(1) 탐색
정렬된 데이터 탐색	BST / 힙	O(log n) 탐색
최솟값·최댓값 반복 접근	힙(우선순위 큐)	O(1) 최솟값 조회
연결 관계 표현	그래프	정점·간선 자유로운 표현

💡 면접 빈출 자료구조 질문과 전략적 답변

이 섹션에서는 면접에서 실제로 자주 나오는 자료구조 질문과 답변 전략을 살펴보겠습니다.

Q1. 해시맵의 시간복잡도는 항상 O(1)인가요?

전략: "예"라고만 하면 탈락입니다. 정답은 "평균 O(1)이지만 최악 O(n)"입니다. 모든 키가 같은 버킷에 충돌하면 체이닝된 연결 리스트를 전부 탐색해야 합니다. Java 8부터는 충돌이 8개 이상이면 연결 리스트 대신 트리(Red-Black Tree)로 변환해 최악 O(log n)을 보장합니다.

Q2. 배열과 연결 리스트 중 어떤 것이 더 좋은가요?

전략: 이런 질문에 "배열이 더 좋다" 또는 "연결 리스트가 더 좋다"고 단답하면 안 됩니다. 좋은 답변: "상황에 따라 다릅니다. 인덱스 접근이 빈번하면 배열이 낫고, 삽입·삭제가 잦으면 연결 리스트가 낫습니다. 또한 배열은 연속 메모리를 사용해 CPU 캐시 효율이 높아 실제로는 배열이 더 자주 쓰입니다."

Q3. 스택으로 큐를, 큐로 스택을 구현하는 방법은?

전략: 스택 두 개로 큐를 구현할 때, 삽입은 스택1에 push하고 꺼낼 때 스택1이 빈 경우 스택1의 모든 원소를 스택2로 이동한 뒤 pop합니다. 이렇게 하면 FIFO 순서가 됩니다. 이 질문은 알고리즘 문제로도 자주 나오기 때문에 머릿속으로 시뮬레이션해보고 설명하는 연습이 필요합니다.

Q4. BST의 단점과 해결 방법은?

전략: "정렬된 데이터를 순서대로 삽입하면 편향 트리가 되어 탐색이 O(n)으로 나빠집니다. 이를 해결하기 위해 삽입·삭제 시 자동으로 균형을 맞추는 AVL 트리나 Red-Black 트리를 사용합니다. Java의 TreeMap이 Red-Black Tree로 구현되어 항상 O(log n)을 보장합니다."

📝 핵심 요약

3강에서 배운 내용을 정리해 보겠습니다.

자료구조	핵심 특성	면접 키워드
배열	O(1) 접근, 연속 메모리	임의 접근, 크기 고정
연결 리스트	O(1) 삽입/삭제, O(n) 접근	동적 크기, 포인터 오버헤드
스택	LIFO, O(1) push/pop	함수 스택, 역순 처리
큐	FIFO, O(1) enqueue/dequeue	BFS, 메시지 큐
BST	O(log n) 탐색, 편향 주의	중위 순회 = 오름차순
그래프	정점+간선, DFS/BFS	인접 행렬 vs 인접 리스트
해시 테이블	평균 O(1), 충돌 주의	체이닝, 오픈 어드레싱

다음 강인 4강 — 알고리즘 문제 접근법에서는 낯선 알고리즘 문제를 받았을 때 막히지 않고 체계적으로 분해·해결하는 4단계 접근법을 완전히 익힙니다. 알고리즘 문제는 아는 것보다 모르는 문제를 만났을 때 어떻게 사고하는가가 더 중요합니다!