자료구조 CS 지식백과
자료구조 관련 핵심 개념을 개발자 기술 면접에서 설명할 수 있도록 문서 12편으로 정리했습니다. 각 문서는 개념, 동작 원리, 시간 복잡도와 실무 선택 기준을 함께 다룹니다.
배열 (Array)
같은 타입의 데이터를 연속 메모리에 저장하는 기본 선형 자료구조인 배열을 다룬다. O(1) 인덱스 접근의 원리, 연산별 시간 복잡도, 동적 배열의 확장과 분할 상환 분석, 캐시 지역성까지 정리했다.
Array vs ArrayList vs LinkedList
배열, ArrayList, LinkedList의 내부 저장 방식과 연산별 시간 복잡도를 비교한다. 캐시 지역성 때문에 실무에서 ArrayList가 유리한 이유와 상황별 선택 기준을 정리했다.
AVL 트리와 레드 블랙 트리 (AVL Tree & Red-Black Tree)
자가 균형 이진 탐색 트리인 AVL 트리와 레드 블랙 트리를 비교한다. 균형 인수와 회전, 탐색과 삽입 비용, TreeMap이 레드 블랙 트리를 쓰는 이유를 정리했다.
B 트리와 B+ 트리 (B-Tree & B+ Tree)
한 노드에 여러 키를 담아 높이를 낮춘 B 트리와 리프에 데이터를 모아 연결한 B+ 트리를 다룬다. 디스크 I/O 최소화 원리와 데이터베이스 인덱스가 B+ 트리를 쓰는 이유를 정리했다.
이진 탐색 트리 (Binary Search Tree)
왼쪽은 작은 값, 오른쪽은 큰 값이라는 규칙으로 평균 O(log n) 탐색을 만드는 이진 탐색 트리를 다룬다. 삽입과 삭제 과정, 편향 시 퇴화 문제와 자가 균형 트리, 해시 테이블과의 선택 기준을 정리했다.
그래프 (Graph)
정점과 간선으로 관계를 표현하는 그래프의 기본 용어와 방향, 가중치 분류를 다룬다. 인접 행렬과 리스트의 차이, DFS와 BFS, 위상 정렬과 최단 경로 활용까지 정리했다.
해시 (Hash)
해시 함수로 키를 인덱스로 변환해 평균 O(1) 조회를 만드는 해시 테이블의 원리를 다룬다. 체이닝과 개방 주소법의 충돌 해결, 적재율과 리해싱, hashCode와 equals 규칙까지 정리했다.
힙 (Heap)
부모가 자식보다 작거나 크도록 유지되는 완전 이진 트리인 힙을 다룬다. 배열 표현, 상향과 하향 조정, O(n) heapify의 원리, 우선순위 큐와 상위 K개 추출 등 활용까지 정리했다.
연결 리스트 (Linked List)
노드를 포인터로 이어 데이터를 저장하는 연결 리스트를 다룬다. 단일, 이중, 원형 구조의 차이와 연산별 비용, 배열과의 실제 성능 비교, 사이클 검출 같은 대표 문제 유형까지 정리했다.
스택과 큐 (Stack & Queue)
후입선출 스택과 선입선출 큐의 개념, O(1) 핵심 연산과 원형 큐 구현을 다룬다. 호출 스택, DFS와 BFS 등 활용처와 스택 두 개로 큐를 만드는 고전 문제까지 정리했다.
트리 (Tree)
노드를 부모 자식 관계로 연결한 계층적 자료구조인 트리를 다룬다. 기본 용어, 이진 트리의 종류, 네 가지 순회 방식, 높이와 균형이 성능을 좌우하는 이유까지 정리했다.
트라이 (Trie)
문자를 경로로 삼아 문자열 집합을 저장하는 접두사 트리인 트라이를 다룬다. O(m) 탐색 원리, 해시 테이블과의 비교, 자동 완성 활용과 메모리 트레이드오프까지 정리했다.
자료구조를 특히 많이 묻는 직군
같은 개념이라도 직군에 따라 파고드는 각도가 다릅니다. 직군별 가이드에서 어떤 질문으로 이어지는지 확인해 보세요.