배열은 메모리에 연속적으로 저장되어 인덱스 접근이 빠르고 `O(1)`입니다. 반면 연결 리스트는 삽입과 삭제는 유리하지만 임의 접근은 `O(n)`이고, 포인터 저장 공간이 추가로 필요합니다.
Array는 크기가 고정된 기본 자료구조이고, ArrayList는 내부적으로 동적 배열을 써서 크기 확장이 가능합니다. LinkedList는 노드 기반 구조라 중간 삽입과 삭제는 유리하지만 검색과 인덱스 접근은 느립니다.
List는 순서를 보장하고 중복을 허용합니다. Set은 중복을 허용하지 않고, 구현체에 따라 순서를 보장하지 않거나 정렬된 순서를 유지합니다.
해시 함수는 키를 배열 인덱스 형태의 해시값으로 변환하는 함수입니다. 해시 테이블은 이 해시값을 이용해 평균적으로 `O(1)`에 삽입, 삭제, 조회를 수행하는 자료구조입니다.
스택은 후입선출(LIFO) 구조라 함수 호출, DFS 등에 사용합니다. 큐는 선입선출(FIFO) 구조라 BFS, 작업 대기열, 메시지 처리에 적합합니다.
힙은 완전 이진 트리 기반으로 최댓값 또는 최솟값을 빠르게 꺼낼 수 있는 자료구조입니다. Priority Queue는 내부적으로 힙을 이용해 우선순위가 높은 원소를 먼저 처리하는 추상 자료형입니다.
트리는 계층 구조를 표현하는 일반 개념입니다. Binary Tree는 자식이 최대 2개이고, BST는 왼쪽 < 루트 < 오른쪽 규칙을 만족하는 이진 트리입니다. AVL Tree는 BST에 균형 조건을 추가해 탐색 성능을 안정적으로 `O(log n)`으로 유지합니다.
BST는 균형이 맞으면 탐색, 삽입, 삭제가 `O(log n)`입니다. 하지만 한쪽으로 치우치면 연결 리스트처럼 되어 최악의 경우 `O(n)`이 됩니다.
대표적으로 체이닝과 개방 주소법이 있습니다. 체이닝은 같은 버킷에 연결 리스트나 트리를 두고, 개방 주소법은 빈 슬롯을 탐색해서 저장합니다.
Trie는 문자열을 문자 단위로 저장하는 트리입니다. 접두사 검색, 자동완성, 사전 검색처럼 문자열 탐색이 많은 경우에 효율적입니다.
B-Tree는 내부 노드와 리프 노드 모두 데이터가 들어갈 수 있고, B+Tree는 실제 데이터가 리프 노드에만 있고 내부 노드는 키와 포인터만 가집니다. DB 인덱스에서는 범위 검색에 유리한 B+Tree가 더 많이 쓰입니다.
DFS는 깊게 탐색하고, BFS는 가까운 노드부터 넓게 탐색합니다. DFS는 경로 탐색과 백트래킹에 자주 쓰고, BFS는 최단 거리나 레벨 탐색에 적합합니다.
버블, 선택, 삽입 정렬은 기본적으로 `O(n^2)`이고, 퀵 정렬은 평균 `O(n log n)`, 병합 정렬은 항상 `O(n log n)`, 힙 정렬도 `O(n log n)`입니다. 거의 정렬된 데이터에서는 삽입 정렬이 유리할 수 있고, 안정성이 필요하면 병합 정렬이 더 적합합니다.
DP는 중복되는 부분 문제를 저장하면서 최적해를 구하는 방식입니다. 재귀와 메모이제이션, 혹은 반복문 기반의 테이블 방식으로 구현합니다.
다익스트라는 음수 가중치가 없는 그래프에서 최단 경로를 구하는 알고리즘입니다. 현재까지 가장 가까운 노드를 하나씩 확정해 나가는 방식입니다.
HashMap은 키-값 쌍을 저장하고, HashSet은 내부적으로 HashMap을 사용해 키만 관리합니다. 둘 다 해시 함수를 이용해 버킷을 찾고, 충돌이 나면 체이닝이나 트리 구조로 처리합니다.
트리는 사이클이 없는 연결 그래프의 특수한 형태입니다. 그래프는 사이클이 있을 수 있고, 연결되지 않을 수도 있으며, 방향성과 가중치도 가질 수 있습니다.
Union-Find는 서로소 집합 자료구조로, 원소들이 같은 집합인지 빠르게 확인하고 집합을 합칠 수 있습니다. 사이클 판별, 연결 요소 판별, 크루스칼 알고리즘에 자주 사용합니다.
세그먼트 트리는 구간 합, 구간 최솟값 같은 구간 질의를 빠르게 처리하는 트리 구조입니다. 펜윅 트리는 구현이 더 간단하고 주로 누적합 기반의 업데이트와 구간 합 계산에 사용합니다.