1. 자료구조란 무엇이며, 선형 자료구조와 비선형 자료구조의 차이점을 설명해주세요. 각각의 대표적인 예시도 함께 들어주세요.
- 자료구조 : 데이터를 효율적으로 저장하고 관리하기 위한 구조
- 선형 자료구조 : 데이터가 순차적으로 나열되어 1:1 관계를 가짐 (배열·스택·큐가 대표적)
- 비선형 자료구조 : 데이터 간 1:N 또는 N:M 관계로 계층적이거나 망 형태를 가짐 (트리·그래프가 대표적)
- 선형은 순서 기반 처리에, 비선형은 계층적 관계나 복잡한 연결 관계 표현에 적합
2. 배열(Array)과 ArrayList, LinkedList의 차이점을 설명하고, 각각의 시간 복잡도(접근, 삽입, 삭제)를 비교해주세요. 어떤 상황에서 어떤 자료구조를 선택해야 하나요?
- Array : 고정 크기의 연속 메모리 구조로 인덱스 접근이 O(1)이지만 크기 변경이 불가
- ArrayList : 내부적으로 배열을 사용하는 동적 배열로, 인덱스 접근은 O(1)이지만 중간 삽입·삭제는 shift가 발생해 O(n)
- LinkedList : 노드와 포인터로 연결된 구조로 중간 삽입·삭제가 O(1)이지만, 인덱스 접근은 순회가 필요해 O(n)
조회가 잦으면 ArrayList, 삽입·삭제가 잦은 양 끝 연산이면 LinkedList를 선택.
다만 실제로는 캐시 효율 때문에 ArrayList가 전반적으로 더 빠른 경우가 많음.
Q1. ArrayList는 크기가 꽉 찼을 때 어떻게 동작하나요?
→ 내부적으로 현재 크기의 1.5배짜리 새 배열을 생성하고, 기존 데이터를 전부 복사해. 이 시점에 O(n) 비용이 발생하지만, amortized(분할 상환)하면 평균 O(1)로 봄.
Q2. Java에서 LinkedList가 ArrayList보다 느린 경우가 많은 이유가 뭔가요?
→ LinkedList는 메모리가 불연속적으로 분산되어 있어서 CPU 캐시 효율이 낮음.
ArrayList는 연속 메모리라 캐시 히트율이 높아서 실제로는 더 빠른 경우가 많음.
Q3. ArrayList와 Vector의 차이는 무엇인가요?
→ Vector는 동기화(synchronized) 가 적용된 ArrayList.
멀티스레드 환경에서 안전하지만, 그만큼 성능이 느림.
요즘은 Vector보다 CopyOnWriteArrayList 나 Collections.synchronizedList() 를 더 많이 씀.
Q4. 배열과 ArrayList 중 primitive 타입을 다룰 때 어느 게 효율적인가요?
→ 배열이 효율적.
ArrayList는 제네릭 타입이라 int 같은 primitive를 쓰면 Integer로 오토박싱이 발생해서 메모리와 성능 오버헤드가 생김.
3. 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List)의 차이점과 각각의 장단점을 설명해주세요.
단일 연결 리스트 : next 포인터만 가져 단방향 순회만 가능하고, 메모리가 가장 효율적
이중 연결 리스트 : prev, next 포인터를 모두 가져 양방향 순회가 가능(Java의 LinkedList가 이 방식으로 구현)
원형 연결 리스트 : 마지막 노드가 첫 노드를 가리켜 순환 구조를 형성하며, 라운드 로빈 스케줄링 같은 순환 처리에 활용
선택 기준은 역방향 탐색 필요 여부와 메모리 효율의 트레이드오프로 결정합니다.
Q1. Java의 LinkedList는 어떤 연결 리스트로 구현되어 있나요?
→ 이중 연결 리스트로 구현되어 있어. 그래서 getFirst(), getLast(), addFirst(), addLast() 같은 양방향 연산을 O(1)로 지원해.
Q2. 원형 연결 리스트는 실제로 어디에 쓰이나요?
→ 대표적으로 라운드 로빈 스케줄링 (CPU가 프로세스를 순서대로 돌아가며 실행), 미디어 플레이어 반복 재생, 원형 버퍼(Circular Buffer) 등에 활용돼.
4. 스택(Stack)이 무엇이며 LIFO 구조를 어떻게 활용하나요? 실제 사용 사례(예: 재귀 호출, 괄호 검사, 뒤로 가기)를 들어 설명해주세요.
- 스택은 LIFO(후입선출) 구조로 가장 마지막에 삽입된 데이터가 먼저 나오는 자료구조.
- push, pop, peek 모두 O(1)임
- 대표적인 활용 사례로는 함수 호출 시 사용되는 콜 스택, 괄호 유효성 검사, 브라우저 뒤로 가기, 실행 취소(Undo) 기능이 있음
- Java에서는 Stack 클래스보다 동기화 오버헤드가 없는 ArrayDeque 사용을 권장합니다.
Q1. Stack 클래스 대신 ArrayDeque를 권장하는 이유가 뭔가요?
→ Stack은 Vector를 상속받아 모든 연산에 synchronized가 걸려 있어. 싱글 스레드 환경에서도 불필요한 동기화 비용이 발생해서 느려. ArrayDeque는 동기화가 없고 배열 기반이라 훨씬 빠르고 캐시 효율도 좋아.
5. 큐(Queue)와 스택의 차이점을 설명하고, 일반 큐의 단점을 보완한 원형 큐(Circular Queue)와 연결 리스트 기반 큐의 동작 방식을 설명해주세요.
- 스택은 LIFO, 큐는 FIFO 구조로 삽입은 rear에서, 삭제는 front에서 일어남
- 배열 기반 일반 큐는 dequeue 후 앞 공간을 재사용하지 못하는 공간 낭비 문제가 있음.
- 원형 큐는 (index+1) % size 연산으로 배열을 순환시켜 이 문제를 해결하지만 크기는 여전히 고정.
- 연결 리스트 기반 큐는 동적으로 크기가 늘어나 크기 제한이 없지만 포인터 오버헤드가 존재.
6. Deque(덱)이란 무엇이며, 스택과 큐로 어떻게 활용될 수 있는지 설명해주세요.
- 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조로, 모든 연산이 O(1).
- 한쪽 끝만 사용하면 스택, 한쪽에서 삽입하고 반대쪽에서 삭제하면 큐로 동작.
- 덱 고유의 활용으로는 슬라이딩 윈도우, 회문 검사 등이 있음.
Q1. ArrayDeque와 LinkedList 기반 덱의 차이는 뭔가요?
→ ArrayDeque는 배열 기반이라 캐시 효율이 좋고 메모리 오버헤드가 적어서 대부분의 경우 더 빠름. LinkedList는 포인터 기반이라 메모리 오버헤드가 있지만 크기 제한이 없고 중간 삽입/삭제가 자유로워. 단순 스택/큐 용도라면 ArrayDeque가 더 효율적이야.
7. 우선순위 큐(Priority Queue)는 무엇이며, 일반 큐와 어떻게 다른가요? 어떤 자료구조로 구현하는 것이 가장 효율적이며 그 이유는 무엇인가요?
- 우선순위 큐는 FIFO가 아닌 우선순위가 높은 데이터가 먼저 나오는 자료구조.
- 배열로 구현하면 삽입 또는 삭제 시 O(n)이 발생하지만, 힙으로 구현하면 삽입과 삭제 모두 O(log n), 최솟값 조회는 O(1)로 가장 효율적.
- 실제로 다익스트라 알고리즘의 최단 경로 탐색, CPU 프로세스 스케줄링 등에 활용.
Java에서는 PriorityQueue 클래스가 내부적으로 최소 힙으로 구현되어 있음
8. 해시 테이블(Hash Table)의 동작 원리와 해시 함수(Hash Function)에 대해 설명해주세요. 평균/최악의 시간 복잡도는 어떻게 되나요?
- 해시 테이블은 해시 함수로 Key를 배열 인덱스로 변환해서 Value를 저장하는 자료구조
- 평균 O(1)로 탐색/삽입/삭제가 가능
- 좋은 해시 함수는 빠른 계산, 균등한 분포, 결정론적 특성을 가져야 함
- Java HashMap은 로드 팩터 0.75를 초과하면 배열을 2배로 확장하고 rehashing을 수행
- 최악의 경우 모든 Key가 같은 인덱스로 해싱되면 O(n)이 발생, 이게 해시 충돌 문제
로드 팩터 (Load Factor)
로드 팩터 = 저장된 데이터 수 / 배열 크기
ex) 데이터 7개, 배열 크기 10 → 로드 팩터 = 0.7로드 팩터가 높아질수록 충돌 확률이 증가해서 성능이 저하. Java HashMap은 기본 로드 팩터가 0.75이고, 이를 초과하면 배열을 2배로 확장(rehashing).
rehashing:
1. 2배 크기의 새 배열 생성
2. 기존 데이터를 새 배열에 전부 재삽입
3. 해시값이 바뀌기 때문에 전부 다시 계산
→ O(n) 비용 발생! (ArrayList 확장과 비슷한 개념)
Q. 로드 팩터를 너무 낮게 설정하면 어떤 문제가 있나요?
→ 충돌은 줄어들어서 탐색 성능은 좋아지지만, 메모리 낭비가 심해지고 rehashing이 자주 발생해서 오히려 성능이 저하될 수 있어. 0.75가 시간/공간 트레이드오프의 균형점.
9. 해시 충돌(Collision)이란 무엇이며, 이를 해결하는 방법(Chaining, Open Addressing)을 비교 설명해주세요.
- 해시 충돌은 서로 다른 Key가 같은 인덱스로 해싱되는 현상.
- Chaining은 충돌 시 연결 리스트로 데이터를 연결하는 방식으로 구현이 단순하지만 포인터 오버헤드와 캐시 효율 저하가 있음.
- Java HashMap이 이 방식을 사용하며, Java 8부터 버킷 크기가 8 이상이면 Red-Black Tree로 변환해 O(log n)으로 성능을 보완.
- Open Addressing은 빈 슬롯을 탐사해서 저장하는 방식으로 메모리 효율과 캐시 효율이 좋지만, 로드 팩터가 1 미만이어야 하고 삭제 시 Tombstone 처리가 필요.
그렇다면 Hash 버킷에서 데이터가 줄어들때 어떻게 되나?
: 트리→리스트 변환 기준은 6개 이하. 8(트리)과 6(리스트) 사이에 버퍼를 둬서 데이터가 경계값 근처에서 왔다갔다할 때 변환이 반복되는 thrashing을 방지해.
10. 트리(Tree) 자료구조의 기본 용어(루트, 부모, 자식, 리프, 깊이, 레벨, 차수)를 설명하고, 트리와 그래프의 차이점은 무엇인가요?
- 트리는 계층적 구조를 표현하는 비선형 자료구조.
- 트리와 그래프의 핵심 차이는 트리는 사이클이 없고, 루트가 존재하며, 노드 간 경로가 유일하고, 간선 수가 노드 수 - 1이라는 점.
- 트리는 그래프의 특수한 형태로, 사이클이 없고 모든 노드가 연결된 그래프가 트리.
Q3. 실생활에서 트리 구조의 예시를 들어주세요.
→ 파일 시스템 (폴더 안에 폴더), 조직도 (대표 → 부서장 → 팀원), HTML DOM 트리 (html → head/body → 각 태그), 댓글의 대댓글 구조 등
11. 이진 트리(Binary Tree)의 종류(완전 이진 트리, 포화 이진 트리, 정 이진 트리)를 설명하고, 트리 순회 방식 4가지(전위, 중위, 후위, 레벨 순회)를 설명해주세요.
- 포화 이진 트리(Perfect Binary Tree) : 모든 노드가 자식 2개이고 리프가 같은 레벨
- 완전 이진 트리(Complete Binary Tree) : 마지막 레벨만 왼쪽부터 채워진 구조
- 정 이진 트리(Full Binary Tree) : 자식이 0개 또는 2개만 존재하는 구조
- 순회 방식은 전위(루트→왼→오), 중위(왼→루트→오), 후위(왼→오→루트), 레벨 순회(너비 우선) 4가지
- 전위/중위/후위 -> 스택(재귀)
- 레벨 순회 -> 큐를 사용
12. 이진 탐색 트리(BST)의 특징과 핵심 연산의 시간 복잡도를 설명해주세요. BST의 단점과 그 단점이 발생하는 상황은 무엇인가요?
- BST는 왼쪽 서브트리의 모든 노드가 부모보다 작고, 오른쪽 서브트리의 모든 노드가 부모보다 큰 이진 트리.
- 탐색할 때마다 범위가 절반씩 줄어들어 평균 O(log n)이지만, 정렬된 데이터를 순서대로 삽입하면 편향 트리가 되어 최악 O(n)이 됨.
- 이 편향 문제를 해결하기 위해 삽입/삭제 시 자동으로 균형을 맞추는 AVL Tree와 Red-Black Tree가 등장함.
13. BST 노드 삭제의 3가지 케이스(자식 노드가 없는 경우, 1개인 경우, 2개인 경우)에 대해 설명해주세요.
- BST 노드 삭제는 자식 수에 따라 3가지 케이스로 나뉨
- 자식이 없으면 그냥 제거
- 자식이 1개면 자식을 삭제된 자리에 연결
- 자식이 2개면 오른쪽 서브트리의 최솟값(후계자) 또는 왼쪽 서브트리의 최댓값(전임자)으로 대체
14. 균형 이진 탐색 트리(AVL Tree, Red-Black Tree)가 왜 필요한가요? Red-Black Tree의 주요 규칙을 설명해주세요.
- BST는 편향 트리가 되면 O(n)으로 성능이 저하되는 문제가 있어서 균형 이진 탐색 트리가 필요
- AVL Tree는 Balance Factor를 -1~1로 엄격하게 유지해서 탐색이 빠르지만, 삽입/삭제 시 회전이 빈번해 쓰기 작업이 많으면 비효율적
- Red-Black Tree는 색상 규칙으로 느슨하게 균형을 유지해서 삽입/삭제 시 회전이 적고 실무에서 더 많이 쓰입니다.
Java의 TreeMap, TreeSet이 Red-Black Tree로 구현되어 있고, Java 8부터 HashMap의 버킷도 크기가 8 이상이면 Red-Black Tree로 변환
15. 힙(Heap)이란 무엇이며, 최대 힙(Max Heap)과 최소 힙(Min Heap)의 차이점은 무엇인가요? 힙의 삽입과 삭제 과정을 설명해주세요.
힙 : 완전 이진 트리 기반으로 부모-자식 간 대소 관계를 유지하는 자료구조
- 최대 힙은 부모가 항상 자식보다 크거나 같고, 최소 힙은 항상 작거나 같음
- 삽입 시 마지막 위치에 추가 후 Heapify Up
- 삭제 시 루트를 제거하고 마지막 노드를 루트로 올린 뒤 Heapify Down을 수행
- 둘 다 O(log n)입니다.
루트가 항상 최댓값/최솟값이라 O(1) 조회가 가능해서 우선순위 큐 구현에 사용되고, 힙 정렬에도 활용.
Q1. 힙이 완전 이진 트리여야 하는 이유가 있나요?
→ 완전 이진 트리여야 배열로 빈 공간 없이 표현할 수 있음. 또한 완전 이진 트리 조건을 항상 유지하기 때문에 높이가 항상 O(log n)으로 보장되기 때문에 삽입/삭제의 시간복잡도가 O(log n)이 보장됨.
Q2. 힙과 BST의 차이점은 뭔가요?
→ BST는 왼쪽 < 부모 < 오른쪽 규칙으로 완전한 정렬 구조를 유지하고 탐색에 특화돼 있음. 힙은 부모 >= 자식(또는 <=) 만 보장하고 형제 간 순서는 없음. 힙은 최댓값/최솟값을 빠르게 꺼내는 데 특화돼 있음.
Q3. 힙 생성이 O(n log n)이 아니라 O(n)인 이유는?
→ 하나씩 삽입하면 O(n log n)이지만, 아래에서 위로 Heapify 하는 방식을 쓰면 O(n)이야. 리프 노드는 Heapify가 필요 없고, 위로 올라갈수록 노드 수가 줄어들기 때문에 수학적으로 O(n)으로 수렴.
Q4. 퀵 정렬 대비 힙 정렬의 장단점은?
→ 힙 정렬은 최악에도 O(n log n) 을 보장하고 추가 메모리가 O(1). 퀵 정렬은 평균 O(n log n)이지만 최악 O(n²)이고 추가 메모리가 O(log n) 필요해. 하지만 퀵 정렬이 캐시 효율이 좋아서 실제로는 더 빠른 경우가 많음.
16. B-Tree와 B+Tree의 차이점은 무엇이며, 데이터베이스의 인덱스로 B+Tree가 주로 사용되는 이유를 설명해주세요.
- B-Tree : 하나의 노드에 여러 키와 데이터를 저장하는 균형 트리
- B+Tree : 내부 노드에 키만 저장하고 실제 데이터는 리프 노드에만 저장하며 리프끼리 연결 리스트로 연결된 구조
DB 인덱스로 B+Tree를 쓰는 이유
- 리프 노드 연결 리스트로 범위 검색이 빠름
- 내부 노드에 키만 저장해서 같은 공간에 더 많은 키를 저장할 수 있어 트리 높이가 낮아짐
- 트리 높이가 낮아서 디스크 I/O 횟수가 최소화됨
Q. B-Tree가 이진 탐색 트리(BST)보다 DB에 적합한 이유는?
→ BST는 노드당 키가 1개라 트리 높이가 높아져서 디스크 I/O가 많이 발생. B-Tree는 하나의 노드에 여러 키를 저장해서 트리 높이가 낮고, 하나의 디스크 블록에 노드 전체를 올릴 수 있어서 I/O 횟수가 훨씬 적음
17. 트라이(Trie) 자료구조란 무엇이며, 주로 어떤 상황에서 활용되나요? (예: 자동완성, 사전 검색) 그래프 / Java Collections / 응용
- 트라이는 문자열 탐색에 특화된 트리 자료구조
- 각 노드가 문자 하나를 나타내고 루트에서 노드까지의 경로가 문자열을 표현
- 삽입과 탐색 모두 문자열 길이 L에만 비례하는 O(L)로, 저장된 문자열 수와 무관하게 빠른 탐색이 가능
- 자동완성, 검색어 추천, 사전 검색처럼 접두사(prefix) 기반 탐색이 필요한 경우에 주로 활용
- 단, 노드마다 자식 포인터를 저장해야 해서 메모리 사용량이 크다는 단점
트라이에서 발생하는 오버헤드 - 노드마다 자식 포인터 배열을 유지해야 해서 메모리 사용량이 크다는 단점
18. 그래프(Graph) 자료구조의 표현 방법(인접 행렬 vs 인접 리스트)을 설명하고, 각각의 장단점과 어떤 상황에 적합한지 설명해주세요.
그래프 표현 방법은 인접 행렬과 인접 리스트 두 가지
- 인접 행렬 : V×V 배열로 간선 존재 확인이 O(1)이지만 공간이 항상 O(V²)라 노드가 많고 간선이 적은 희소 그래프에서 메모리 낭비가 심함
- 인접 리스트 : 연결된 노드만 저장해서 O(V+E) 공간을 사용하고 탐색이 효율적이라 대부분의 경우에 적합
- 따라서 밀집 그래프이거나 간선 존재 확인이 잦으면 인접 행렬, 그 외 대부분의 경우엔 인접 리스트를 사용함
19. DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)의 차이점은 무엇이며, 각각 어떤 자료구조(스택/큐)를 활용하나요? 어떤 상황에서 어떤 알고리즘을 사용해야 하나요?
DFS는 깊이 우선으로 스택(재귀)을 사용, BFS는 너비 우선으로 큐를 사용
둘 다 시간복잡도는 O(V+E)입니다.
- DFS는 모든 경로 탐색, 백트래킹, 사이클 감지에 적합
- BFS는 가중치 없는 그래프에서 최단 경로 탐색에 적합
- BFS가 최단 경로를 보장하는 이유는 레벨 단위로 탐색하기 때문에 목적지를 처음 발견하는 순간이 곧 최단 경로이기 때문
Q. DFS와 BFS의 시간복잡도가 둘 다 O(V+E)인 이유는? → 두 알고리즘 모두 모든 노드(V)를 한 번씩 방문하고, 각 노드에서 모든 간선(E)을 한 번씩 확인하기 때문이야. 인접 리스트 기준이고, 인접 행렬이면 O(V²)야.
20. Java의 Collection Framework에서 List, Set, Map 인터페이스의 차이점과 각각의 대표적인 구현체(ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap)의 특징을 비교 설명해주세요.
Java Collection Framework는 List, Set, Map 인터페이스로 나뉨
- List는 순서가 있고 중복을 허용
- ArrayList는 배열 기반으로 조회가 O(1)
- LinkedList는 이중 연결 리스트로 앞뒤 삽입/삭제가 O(1)
- Set은 중복을 허용하지 않음
- HashSet은 O(1) 탐색
- TreeSet은 Red-Black Tree 기반으로 정렬을 보장하지만 O(log n)
- Map은 Key-Value 쌍으로 저장
- HashMap은 O(1) 탐색, TreeMap은 Key 기준 정렬을 보장.
- 순서 유지가 필요하면 Linked 계열을 사용
Q. HashSet이 내부적으로 HashMap으로 구현된다는 게 무슨 뜻인가요?
→ HashSet은 내부에 HashMap을 가지고 있고, 저장할 값을 HashMap의 Key로 사용. Value는 의미 없는 더미 객체(PRESENT)를 넣음. Key의 중복을 허용하지 않는 HashMap의 특성을 그대로 활용.
21. HashMap과 HashTable, ConcurrentHashMap의 차이점은 무엇이며, 각각 어떤 상황에서 사용해야 하나요? Java 8 이후 HashMap의 내부 구조 변화(Treeify)에 대해서도 설명해주세요.
세 가지 비교
| 구분 | HashMap | HashTable | ConcurrentHashMap |
| 동기화 | ❌ | 메서드 전체 | 버킷 단위 |
| null 허용 | Key/Value 모두 ✅ | ❌ | ❌ |
| 성능 | 가장 빠름 | 가장 느림 | 중간 (실용적) |
| 스레드 안전 | ❌ | ✅ | ✅ |
| 사용 시점 | 단일 스레드 | 사용 비권장 | 멀티 스레드 |
| 등장 버전 | JDK 1.2 | JDK 1.0 | JDK 1.5 |
HashMap : 동기화가 없어 단일 스레드에서 가장 빠르고 null Key/Value를 허용
HashTable : 모든 메서드에 synchronized가 적용되어 스레드 안전하지만, 테이블 전체에 락을 걸어 성능이 낮아 현재는 사용을 권장하지 않음
ConcurrentHashMap : 버킷 단위로 락을 걸어 멀티스레드 환경에서도 높은 성능을 보장
Java 8부터는 Segment 방식에서 버킷 단위 락과 CAS 연산으로 변경되어 더욱 효율적
Java 8에서 HashMap은 버킷의 연결 리스트 길이가 8 이상이면 Red-Black Tree로 변환(Treeify)하여 최악의 경우 O(n)에서 O(log n)으로 성능을 개선
hashtable은 컬렉션 프레임워크 이전에 있던 것임
Q1. ConcurrentHashMap에서 null을 허용하지 않는 이유가 있나요?
→ 멀티스레드 환경에서 map.get(key)가 null을 반환했을 때 Key가 없는 건지, Value가 null인 건지 구분이 불가능해. 단일 스레드면 containsKey()로 확인할 수 있지만 멀티스레드에서는 확인하는 사이에 다른 스레드가 값을 바꿀 수 있어서 null 자체를 허용하지 않도록 설계했어.
Q2. ConcurrentHashMap의 버킷 단위 락이 HashTable보다 빠른 이유는?
→ HashTable은 테이블 전체에 락을 걸어서 한 번에 스레드 하나만 접근 가능. ConcurrentHashMap은 버킷 단위로 락을 걸어서 서로 다른 버킷에 접근하는 스레드들은 동시에 작업할 수 있어. 병렬 처리가 가능하니까 훨씬 빠름
