[CS 지식] 3. 자료구조

📚 자료구조 면접 필수 개념 정리

---

1. Array(배열)

정의

• 연속된 메모리에 같은 타입의 원소를 순서대로 저장. 인덱스로 O(1) 임의 접근(Random Access) 가능.

비유/보충

• 책장이 연속된 칸으로 이루어져 있어, n번째 칸에 바로 손이 간다(접근 빠름).
• 중간에 책을 끼우거나 빼면 뒤의 책들을 밀고/당겨야 한다(삽입/삭제 느림).
• CPU 캐시 적중률( locality )이 좋아 순차 순회가 매우 빠름.

시간복잡도

• 접근: O(1) / 검색(정렬X): O(n) / 끝 삽입·삭제: O(1) / 중간 삽입·삭제: O(n)

언제 쓰나

• 순서 유지 + 임의 접근이 중요하고, 중간 삽입/삭제가 드문 데이터.

답변 예시

“배열은 연속된 메모리에 순서대로 저장해 인덱스로 O(1) 접근이 가능합니다. 대신 중간 삽입·삭제 시 뒤 원소들을 이동해야 해 O(n) 비용이 들죠. 그래서 순서가 중요하지만 갱신이 적은 데이터에 적합합니다.

Q. Array를 적용시키면 좋을 데이터의 예를 구체적으로 들어주세요. 구체적 예시와 함께 Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지 함께 설명해주세요.

답변 예시

“Array를 적용시키면 좋은 예로 주식 차트가 있습니다.주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날짜별로 주식 가격이 차례대로 저장되어야 하는 데이터입니다.즉, 순서가 굉장히 중요한 데이터이므로 Array 같이 순서를 보장해주는 자료구조를 사용하는 것이 좋습니다.Array를 사용하지 않고 순서가 없는 자료 구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어 들이고 비교해야 하는 번거로움이 발생합니다.”

---

2. Stack / Queue / Tree / Heap

정의

• Stack: LIFO (예: 함수 호출 스택, 실행 취소)
• Queue: FIFO (예: OS 스케줄러 대기열, 메시지 큐)
• Tree: 계층/비선형 구조 (예: 디렉터리, DOM)
• Heap(이진 힙): 완전이진트리 기반 우선순위 빠른 추출(최대/최소)
  • 삽입/삭제 O(log n), 최댓값/최솟값 조회 O(1)

답변 예시

“스택은 LIFO, 큐는 FIFO로 선형 구조이고, 트리는 비선형 계층 구조입니다. 힙은 완전이진트리로 최댓값/최솟값을 빠르게 꺼내는 데 특화되어 삽입·삭제가 O(log n)입니다.”

---

3. Stack / Queue 사용 예

• Stack: 지역변수와 매개변수 데이터 값이 저장되는 공간이며, 메소드 호출시 메모리에 할당되고 종료되면 메모리가 해제되며, LIFO(Last In First Out)구조를 가집니다.
• ex) 함수 호출/복귀, 웹 브라우저 뒤로 가기
• Queue: 자원의 할당과 회수를 하는 스케쥴러 역할에 사용됩니다. 메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가 그 순서를 결정할 때 가장 단순한 형태의 스케쥴링 정책이 FCFS(First Come First Serve)입니다.
• ex) 작업 스케줄링

답변 예시

“스택은 함수 호출 스택과 같은 LIFO 상황에, 큐는 OS 스케줄러나 메시지 큐처럼 선입선출 처리에 쓰입니다.”

---

4. Stack 간단 구현 (Java)

public class Stack {
    private static final int MAX = 10;
    private int top = -1;
    private final int[] data = new int[MAX];

    public void push(int x) throws Exception {
        if (top == MAX - 1) throw new Exception("스택이 가득 찼습니다.");
        data[++top] = x;
    }
    public int pop() throws Exception {
        if (top == -1) throw new Exception("스택이 비었습니다.");
        return data[top--];
    }
    public int peek() throws Exception {
        if (top == -1) throw new Exception("스택이 비었습니다.");
        return data[top];
    }
    public boolean isEmpty() { return top == -1; }
    public int size() { return top + 1; }
}

---

5. Priority Queue(우선순위 큐)

정의/구현

• 우선순위가 높은 원소를 먼저 꺼냄.
• 배열/연결리스트/힙으로 구현 가능하나, 이진 힙이 일반적(삽입/삭제 O(log n)).

답변 예시

“우선순위 큐는 순서와 무관하게 우선순위가 높은 데이터를 먼저 꺼내는 구조로, 보통 이진 힙으로 구현해 삽입·삭제 O(log n)을 보장합니다.”

---

6. Array vs ArrayList

차이

• Array: 고정 크기, 원시타입 저장, 빠른 접근/낮은 오버헤드
• ArrayList: 가변 크기 동적 배열, 내부적으로 용량 배수 확장(Amortized O(1) append)

답변 예시

“배열은 크기가 고정이라 빠르고 가볍지만, ArrayList는 자동으로 크기를 늘려 다루기가 편합니다. 추가는 평균 O(1)이지만 확장 시 재할당 비용이 발생할 수 있습니다.”

---

7. Array vs LinkedList

Array

• 인덱스 접근 O(1), 캐시 친화적
• 중간 삽입/삭제 O(n)

LinkedList

• 노드 단위 연결. 중간 삽입/삭제 O(1)(포인터만 교체)
• 임의 접근 불가, 탐색 O(n), 캐시 비우호

답변 예시

“배열은 임의 접근이 O(1)로 빠르지만 중간 삽입·삭제가 느립니다. 링크드 리스트는 반대로 삽입·삭제가 O(1)이지만 원하는 위치를 찾는 탐색이 O(n)이라 느립니다.”

---

8. 해시 테이블(Hash Table) — 개념/시간복잡도

정의

• (Key → 해시함수 → 인덱스)로 버킷 배열에 저장. 평균 조회/삽입/삭제 O(1).

충돌 처리

• Chaining(연결 리스트/트리로 체이닝)
• Open Addressing(선형/제곱 탐사, 이중 해싱)

실무 포인트

• 부하율(load factor) 관리와 리사이즈가 성능의 핵심.
• 자바: HashMap은 충돌 심해지면 버킷을 트리화(RBT) 하여 성능 보호.

답변 예시

“해시 테이블은 키를 해시함수로 인덱스에 매핑해 평균 O(1)로 접근합니다. 충돌은 체이닝이나 오픈어드레싱으로 해결하고, 부하율에 따라 리사이즈하여 성능을 유지합니다.”

---

9. HashMap vs Hashtable (Java)

차이

• 동기화: Hashtable은 기본 동기화( thread-safe ), HashMap은 아님
• null: Hashtable은 null 키/값 불가, HashMap은 허용
• 현대 대안: 멀티스레드 환경에선 ConcurrentHashMap 권장(세분화 락/병렬성)

답변 예시

“Hashtable은 동기화와 null 불허의 레거시 컬렉션이고, HashMap은 동기화되지 않으며 null을 허용합니다. 동시성 환경에서는 HashMap 대신 ConcurrentHashMap을 씁니다.”

---

10. Binary Tree vs BST

Binary Tree

• 자식이 최대 2개인 트리(형태 제약 없음)

BST (Binary Search Tree)

• 왼 < 부모 < 오 규칙 유지 → 탐색 평균 O(log n)
• 편향되면 O(n)까지 악화 → 균형 트리(AVL/RBT) 필요

답변 예시

“이진 트리는 단순한 구조 개념이고, BST는 왼쪽이 작고 오른쪽이 큰 정렬 규칙을 갖는 트리입니다. 균형이 무너지면 O(n)까지 느려져서 Red-Black Tree 같은 균형 트리를 씁니다.”

---

11. Red-Black Tree(RBT)

핵심 아이디어

• 노드를 빨강/검정으로 색칠하며 회전과 재색으로 높이를 거의 균형 상태로 유지.
• 연산(탐색/삽입/삭제) O(log n) 보장.

대표 속성(요지)

1. 노드는 적/흑 중 하나
2. 루트는 흑
3. 적 노드의 자식은 모두 흑(적-적 연속 금지)
4. 모든 리프(NIL)까지의 흑 높이 동일

답변 예시

“RBT는 색 규칙과 회전으로 트리 높이를 균형에 가깝게 유지해 연산을 O(log n)으로 보장합니다. 자바 HashMap이 충돌 버킷을 트리화할 때도 RBT를 사용합니다.”

---

12. Heap

최대힙/최소힙

• 루트가 최댓값/최솟값, 배열로 구현(인덱스 규칙: i의 자식 2i+1, 2i+2)
• push/pop O(log n), top O(1)

사용처

• 우선순위 큐, 상위 K개 문제, 다익스트라, 스케줄링

답변 예시

“힙은 완전이진트리를 배열로 표현해 최댓값/최솟값을 O(1)로 보고, 삽입·삭제를 O(log n)에 수행합니다. 우선순위 큐와 최단경로 알고리즘에 널리 쓰입니다.”

---

13. 추가로 알면 좋은 면접 포인트

• 동적 배열의 Amortized O(1): 용량 배로 늘릴 때만 재할당 비용 발생
• Trie(프리픽스 트리): 문자열 접두사 검색에 특화(O(문자열 길이))
• Deque: 양끝 삽입·삭제 O(1) (슬라이딩 윈도우, 모노토닉 큐 패턴)
• Stable vs Unstable 정렬: 동일 키의 상대 순서 보존 여부

---