전산직 컴퓨터일반 - Part 04 자료구조 요약

Posted on | In

⭐⭐⭐ 반드시 / ⭐⭐ 중요 / ⭐ 참고 ⚠️ = 기출 함정 포인트


Chapter 01. 개요

자료구조 분류 ⭐⭐⭐

구분 관계 종류
선형 구조 데이터가 1 : 1로 한 줄로 이어짐 배열, 연결 리스트, 스택, 큐, 데크
비선형 구조 데이터가 1 : N 또는 N : N 트리 (1 : N), 그래프 (N : N)

⚠️ 스택·큐는 선형, 트리·그래프는 비선형. 분류 문제 단골

알고리즘의 조건 ⭐

  • 입력 (0개 이상), 출력 (1개 이상), 명확성 (모호하지 않음), 유한성 (반드시 끝남), 효과성 (실행 가능)

복잡도 ⭐⭐⭐

  • 시간 복잡도 : 알고리즘이 수행하는 기본 연산 횟수. 입력 크기 n에 따라 변함
  • 공간 복잡도 : 알고리즘이 필요로 하는 메모리 크기
  • 빅오(Big-O) 표기법 : 최악의 경우 상한을 표기. 가장 큰 차수만 남기고 계수는 버림
    • 예 : 3n² + 5n + 2 → O(n²)

복잡도 크기 순서 ⭐⭐⭐

1
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
복잡도 대표 예
O(1) 배열 인덱스 접근, 해싱
O(log n) 이진 탐색
O(n) 순차 탐색
O(n log n) 퀵(평균)·힙·합병 정렬
O(n²) 버블·선택·삽입 정렬


Chapter 02. 배열

배열 ⭐⭐

  • 같은 자료형의 데이터를 연속된 메모리 공간에 저장
  • 인덱스로 직접 접근 → 접근 O(1)
  • 중간 삽입·삭제는 뒤의 원소를 다 밀거나 당겨야 해서 O(n)
  • 크기가 고정되어 있음

배열 주소 계산 ⭐⭐⭐

1차원

1
A[i]의 주소 = 시작 주소 + i × 원소 크기

2차원 : A[m][n] (m행 n열)

방식 공식 사용 언어
행 우선 시작 주소 + (i × n + j) × 원소 크기 C, C++, Java
열 우선 시작 주소 + (j × m + i) × 원소 크기 Fortran

예시 : int A[3][4], 시작 주소 1000, int = 4바이트일 때 A[2][1] 의 주소

  • 행 우선 : 1000 + (2 × 4 + 1) × 4 = 1036
  • 열 우선 : 1000 + (1 × 3 + 2) × 4 = 1020

⚠️ 인덱스가 0부터인지 1부터인지 문제 조건 꼭 확인

희소 행렬 ⭐

  • 대부분의 원소가 0인 행렬 → 메모리 낭비
  • 0이 아닌 원소만 (행, 열, 값) 3개 묶음으로 저장해서 공간 절약


Chapter 03. 구조체

구조체 (struct) ⭐⭐

  • 서로 다른 자료형의 데이터를 하나로 묶은 사용자 정의 자료형
1
2
3
4
5
6
7
8
9
10
11
12
struct Student {
    char name[20];
    int age;
    double score;
};

struct Student s;
struct Student *p = &s;

s.age = 20;       // 일반 변수 → 점(.)
p->age = 20;      // 포인터 → 화살표(->)
(*p).age = 20;    // p->age와 같음

⚠️ p->age = (*p).age. *p.age는 *(p.age)로 해석되어 오류

구조체 크기와 패딩 ⭐

  • CPU가 메모리를 빨리 읽도록 멤버를 정렬하면서 빈 공간(패딩)이 생길 수 있음
  • 그래서 구조체 크기 ≥ 멤버 크기의 합
1
2
struct A { char a; int b; char c; };   // 1 + (3) + 4 + 1 + (3) = 12바이트
struct B { int b; char a; char c; };   // 4 + 1 + 1 + (2) = 8바이트
  • 멤버 선언 순서에 따라 크기가 달라짐 (정확한 값은 컴파일러·환경에 따라 다름)

구조체 vs 공용체 ⭐

구분 구조체 (struct) 공용체 (union)
메모리 멤버마다 각자 공간 모든 멤버가 같은 공간 공유
크기 멤버 크기의 합 (+ 패딩) 가장 큰 멤버의 크기


Chapter 04. 포인터

포인터 ⭐⭐⭐

  • 메모리 주소를 저장하는 변수
연산자 의미
& 변수의 주소
* 포인터가 가리키는 곳의 값 (역참조) 
1
2
3
int a = 10;
int *p = &a;    // p에 a의 주소 저장
*p = 20;        // a의 값이 20으로 바뀜

배열과 포인터 ⭐⭐⭐

  • 배열 이름 = 배열 첫 원소의 주소 (a == &a[0])
  • a[i] == *(a + i)
  • 포인터 + 1 = 자료형 크기만큼 주소 이동 (int면 4바이트)
1
2
3
4
5
6
7
8
9
int a[5] = {10, 20, 30, 40, 50};
int *p = a;

printf("%d", *p);        // 10
printf("%d", *(p + 2));  // 30  → a[2]
printf("%d", *p + 2);    // 12  → a[0] + 2
p++;                     // p는 이제 a[1]을 가리킴
printf("%d", *p);        // 20
printf("%d", p[2]);      // 40  → a[3]

⚠️ *(p + 2) (주소를 옮긴 뒤 값) vs *p + 2 (값에 2를 더함). 코드 출력 문제 단골 ⚠️ p++ 이후에는 p[0]이 a[1]. 기준점이 바뀌는 것 주의

값에 의한 호출 vs 참조에 의한 호출 ⭐⭐

1
2
3
4
void swap1(int x, int y)   { int t = x;  x = y;   y = t; }    // 원본 안 바뀜
void swap2(int *x, int *y) { int t = *x; *x = *y; *y = t; }   // 원본 바뀜

swap2(&a, &b);
Call by Value Call by Reference
값을 복사해서 전달 주소를 전달
함수 안에서 바꿔도 원본 그대로 원본이 바뀜


Chapter 05. 연결 리스트

연결 리스트 ⭐⭐⭐

  • 각 노드 = 데이터 + 다음 노드를 가리키는 포인터(링크)
  • 메모리에 흩어져 있어도 포인터로 연결
종류 설명
단순 연결 리스트 다음 노드만 가리킴. 마지막 노드의 링크는 NULL
원형 연결 리스트 마지막 노드가 첫 노드를 가리킴
이중 연결 리스트 이전·다음 노드를 모두 가리킴. 양방향 탐색 가능, 포인터 공간 더 필요

배열 vs 연결 리스트 ⭐⭐⭐

구분 배열 연결 리스트
메모리 연속 불연속 (포인터로 연결)
접근 인덱스로 직접 접근 O(1) 처음부터 따라가야 함 O(n)
삽입·삭제 원소 이동 필요 O(n) 포인터만 바꾸면 됨 O(1) (위치를 알 때)
크기 고정 동적으로 변경 가능
추가 공간 없음 포인터 공간 필요

삽입·삭제 코드 ⭐⭐

노드 p 다음에 new 삽입

1
2
new->next = p->next;   // ① 새 노드가 p의 다음을 가리킴
p->next = new;         // ② p가 새 노드를 가리킴

⚠️ 순서를 바꾸면 p의 원래 다음 노드 주소를 잃어버려서 리스트가 끊김

노드 p 다음 노드 삭제

1
2
3
q = p->next;
p->next = q->next;
free(q);

이중 연결 리스트에서 p 다음에 new 삽입

1
2
3
4
new->prev = p;
new->next = p->next;
p->next->prev = new;
p->next = new;


Chapter 06. 스택

스택 (Stack) ⭐⭐⭐

  • LIFO (Last In First Out) : 나중에 들어온 게 먼저 나감
  • 한쪽 끝(Top)에서만 삽입(Push)·삭제(Pop)
  • 오버플로 : 꽉 찬 상태에서 Push / 언더플로 : 빈 상태에서 Pop

스택 응용 ⭐⭐⭐

  • 함수 호출·재귀의 복귀 주소 저장
  • 수식 계산 (후위 표기식), 중위 → 후위 변환
  • 괄호 검사
  • 깊이 우선 탐색 (DFS)
  • 되돌리기(Undo), 웹 브라우저 뒤로 가기
  • 인터럽트 처리 후 복귀

⚠️ BFS는 큐, DFS는 스택

스택 출력 순서 문제 ⭐⭐⭐

입력 순서가 1, 2, 3일 때 Push·Pop을 섞어서 나올 수 있는 순서는?

출력 가능?
1 2 3 O
1 3 2 O
2 1 3 O
2 3 1 O
3 2 1 O
3 1 2 X
  • 3이 먼저 나오려면 1, 2가 이미 스택 안에 쌓여 있어야 함 → 그다음은 반드시 2 (위에 있는 것부터)
  • 요령 : 어떤 수 k가 나온 뒤, k보다 작은 수들은 내림차순으로만 나올 수 있음
  • 예 : 입력 1, 2, 3, 4 → 4 1 2 3 불가능 (4 다음엔 3이 나와야 함)

수식 표기법 ⭐⭐⭐

표기법 형태 예
전위 (Prefix) 연산자 피연산자 피연산자 + A B
중위 (Infix) 피연산자 연산자 피연산자 A + B
후위 (Postfix) 피연산자 피연산자 연산자 A B +

중위 → 후위·전위 변환 요령

  1. 연산 우선순위대로 괄호를 전부 친다
  2. 후위 : 연산자를 자기 괄호의 오른쪽 괄호 밖으로 / 전위 : 왼쪽 괄호 밖으로
  3. 괄호를 지운다

예시 : A * (B + C) - D / E

1
2
3
괄호     : ((A * (B + C)) - (D / E))
후위     : A B C + * D E / -
전위     : - * A + B C / D E

후위 표기식 계산 (스택 이용)

피연산자는 Push, 연산자를 만나면 2개 Pop해서 계산 후 결과 Push

예시 : 5 3 2 * + 4 -

읽은 값 동작 스택
5, 3, 2 Push 5 3 2
* 3 × 2 = 6 5 6
+ 5 + 6 = 11 11
4 Push 11 4
- 11 − 4 = 7 7

⚠️ Pop 순서 주의 : 먼저 나온 게 오른쪽 피연산자 (11 − 4이지 4 − 11이 아님)


Chapter 07. 큐

큐 (Queue) ⭐⭐⭐

  • FIFO (First In First Out) : 먼저 들어온 게 먼저 나감
  • Rear(뒤)에서 삽입, Front(앞)에서 삭제
  • 응용 : CPU 작업 스케줄링, 너비 우선 탐색 (BFS), 프린터 스풀, 버퍼

원형 큐 ⭐⭐⭐

  • 선형 큐는 삭제 후 앞쪽 빈 공간을 재사용 못 함 → 배열 끝과 처음을 이어 붙인 원형 큐로 해결
1
2
3
4
삽입 : rear = (rear + 1) % N
삭제 : front = (front + 1) % N
공백 : front == rear
포화 : (rear + 1) % N == front
  • 공백과 포화를 구분하려고 한 칸을 비워둠 → 크기 N인 원형 큐는 최대 N − 1개 저장

데크 (Deque) ⭐⭐

  • 양쪽 끝에서 모두 삽입·삭제 가능 (스택 + 큐)
종류 설명
스크롤 (Scroll) 입력 제한 데크 : 입력은 한쪽만, 출력은 양쪽
셸프 (Shelf) 출력 제한 데크 : 입력은 양쪽, 출력은 한쪽만

우선순위 큐 ⭐

  • 들어온 순서가 아니라 우선순위가 높은 것부터 나감
  • 보통 힙(Heap) 으로 구현


Chapter 08. 트리

트리 용어 ⭐⭐⭐

1
2
3
4
5
        A          ← 레벨 1 (루트)
       / \
      B   C        ← 레벨 2
     / \   \
    D   E   F      ← 레벨 3 (D, E, F = 단말 노드)
용어 의미 위 트리에서
루트 (Root) 맨 위 노드 A
단말 노드 (Leaf, Terminal) 자식이 없는 노드 D, E, F
노드의 차수 (Degree) 한 노드의 자식 수 A = 2, C = 1, D = 0
트리의 차수 노드 차수 중 최댓값 2
레벨 (Level) 루트를 1로 해서 아래로 1씩 증가 –
깊이·높이 (Depth, Height) 트리의 최대 레벨 3
  • 노드 n개인 트리의 간선 수 = n − 1

이진 트리 ⭐⭐⭐

  • 모든 노드의 차수가 2 이하인 트리
종류 설명
포화 이진 트리 모든 레벨이 꽉 찬 트리
완전 이진 트리 마지막 레벨 전까지 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워진 트리 (힙이 이 형태)
편향 이진 트리 한쪽 방향으로만 자식이 이어진 트리

이진 트리 성질 ⭐⭐⭐

1
2
3
레벨 i의 최대 노드 수        = 2^(i − 1)
깊이 k인 트리의 최대 노드 수  = 2^k − 1
단말 노드 수 n₀ = 차수 2인 노드 수 n₂ + 1
  • 예 : 깊이 4 → 최대 2⁴ − 1 = 15개
  • 위 트리 확인 : 차수 2 노드 (A, B) = 2개 → 단말 노드 = 2 + 1 = 3개 (D, E, F)

⚠️ n₀ = n₂ + 1 계산 문제 매우 자주 나옴

트리 순회 ⭐⭐⭐

순회 순서 암기
전위 (Preorder) 루트 → 왼쪽 → 오른쪽 루트가 앞
중위 (Inorder) 왼쪽 → 루트 → 오른쪽 루트가 가운데
후위 (Postorder) 왼쪽 → 오른쪽 → 루트 루트가 뒤

위 트리 순회 결과

  • 전위 : A B D E C F
  • 중위 : D B E A C F
  • 후위 : D E B F C A

⚠️ 서브트리에서도 같은 규칙을 재귀적으로 적용. C는 왼쪽 자식이 없으니 중위에서 C → F

  • 수식 트리를 전위·중위·후위 순회하면 각각 전위·중위·후위 표기식이 됨

일반 트리 → 이진 트리 변환 ⭐

  • 왼쪽 자식 - 오른쪽 형제 방식 : 첫 번째 자식은 왼쪽 링크로, 형제는 오른쪽 링크로 연결


Chapter 09. 그래프

그래프 ⭐⭐⭐

  • 정점(Vertex) 과 간선(Edge) 의 집합. G = (V, E)
  • 무방향 그래프 : 간선에 방향 없음 (A–B = B–A)
  • 방향 그래프 : 간선에 방향 있음 (A→B ≠ B→A)
  • 차수 : 정점에 연결된 간선 수. 방향 그래프는 진입 차수 + 진출 차수

최대 간선 수 (완전 그래프) ⭐⭐⭐

그래프 최대 간선 수
무방향 n(n − 1) / 2
방향 n(n − 1)
  • 예 : 정점 5개 → 무방향 10개, 방향 20개

그래프 표현 ⭐⭐

구분 인접 행렬 인접 리스트
방법 n × n 2차원 배열 (연결되면 1) 정점마다 연결된 정점을 연결 리스트로
공간 O(n²) O(n + e)
유리한 경우 간선이 많은 밀집 그래프 간선이 적은 희소 그래프
  • 무방향 그래프의 인접 행렬은 대칭 행렬

그래프 탐색 ⭐⭐⭐

구분 DFS (깊이 우선) BFS (너비 우선)
방법 한 방향으로 끝까지 가고 막히면 되돌아옴 가까운 정점부터 한 층씩 방문
자료구조 스택 (재귀) 큐

예시 : 1에서 시작, 번호가 작은 정점부터 방문

1
2
3
1 ─ 2 ─ 4
│   │
3 ─ 5
  • DFS : 1 → 2 → 4 → 5 → 3
  • BFS : 1 → 2 → 3 → 4 → 5

신장 트리 ⭐⭐

  • 그래프의 모든 정점을 포함하면서 사이클이 없는 트리. 간선 수 = n − 1
  • 최소 비용 신장 트리 (MST) : 간선 가중치 합이 최소인 신장 트리
알고리즘 방법
크루스칼 (Kruskal) 전체 간선을 가중치 작은 순으로 정렬해서, 사이클이 안 생기는 간선만 선택
프림 (Prim) 한 정점에서 시작해서, 연결된 간선 중 가장 작은 것을 골라 트리를 확장

⚠️ 크루스칼 = 간선 중심 / 프림 = 정점 중심

최단 경로 ⭐⭐

알고리즘 특징
다익스트라 한 정점에서 다른 모든 정점까지. 음수 가중치 X
벨만-포드 한 정점 기준. 음수 가중치 O
플로이드-워셜 모든 정점 쌍 사이의 최단 경로

위상 정렬 ⭐

  • 방향 그래프에서 선후 관계를 지키며 정점을 나열 (예 : 선수 과목 순서). 사이클이 없어야 가능


Chapter 10. 정렬

정렬 알고리즘 ⭐⭐⭐

정렬 방법
버블 (Bubble) 인접한 두 원소를 비교해서 교환. 1회전마다 가장 큰 값이 맨 뒤로
선택 (Selection) 남은 것 중 최솟값을 찾아 맨 앞과 교환
삽입 (Insertion) 앞쪽은 정렬된 상태로 두고, 다음 원소를 알맞은 위치에 삽입
셸 (Shell) 삽입 정렬 개선. 일정 간격(gap) 떨어진 원소끼리 삽입 정렬 후 간격을 줄여감
퀵 (Quick) 피봇(기준값) 을 정해 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할 후 재귀 (분할 정복)
힙 (Heap) 최대 힙을 만들고, 루트(최댓값)를 맨 뒤로 보내며 반복
합병 (Merge, 2원 합병) 반씩 쪼갠 뒤 정렬하며 합침 (분할 정복)
기수 (Radix) 자릿수별로 버킷에 분배 (비교 안 함)

⚠️ “피봇 정렬”이라는 이름은 없음. 피봇을 쓰는 건 퀵 정렬

복잡도 비교 ⭐⭐⭐

정렬 최선 평균 최악 안정성 추가 메모리
버블 O(n)* O(n²) O(n²) 안정 X
선택 O(n²) O(n²) O(n²) 불안정 X
삽입 O(n) O(n²) O(n²) 안정 X
셸 O(n log n) 약 O(n^1.5) O(n²) 불안정 X
퀵 O(n log n) O(n log n) O(n²) 불안정 X
힙 O(n log n) O(n log n) O(n log n) 불안정 X
합병 O(n log n) O(n log n) O(n log n) 안정 O(n)
기수 O(dn) O(dn) O(dn) 안정 O(n)

* 교환이 없으면 바로 끝내는 개선 버전 기준

  • 안정 정렬 : 같은 값의 원래 순서가 유지됨 → 버블, 삽입, 합병, 기수
  • 선택 정렬은 이미 정렬돼 있어도 항상 O(n²)

⚠️ 퀵 정렬 최악 = 이미 정렬된 데이터 (피봇이 한쪽 끝일 때) ⚠️ 삽입 정렬 최선 = 이미 정렬된 데이터 → O(n) ⚠️ 힙·합병은 최악도 O(n log n), 합병은 추가 메모리 필요, 힙은 불필요

회전별 결과 문제 ⭐⭐⭐

[8, 3, 4, 9, 7] 오름차순 정렬

회전 선택 정렬 버블 정렬 삽입 정렬
1회전 [3, 8, 4, 9, 7] [3, 4, 8, 7, 9] [3, 8, 4, 9, 7]
2회전 [3, 4, 8, 9, 7] [3, 4, 7, 8, 9] [3, 4, 8, 9, 7]
3회전 [3, 4, 7, 9, 8] [3, 4, 7, 8, 9] [3, 4, 8, 9, 7]
4회전 [3, 4, 7, 8, 9] 완료 [3, 4, 7, 8, 9]
  • 선택 : 앞에서부터 작은 값이 하나씩 확정
  • 버블 : 뒤에서부터 큰 값이 하나씩 확정
  • 삽입 : 앞쪽 정렬된 구간이 하나씩 늘어남

힙 ⭐⭐

  • 완전 이진 트리 + 부모와 자식 간 크기 규칙
    • 최대 힙 : 부모 ≥ 자식 → 루트 = 최댓값
    • 최소 힙 : 부모 ≤ 자식 → 루트 = 최솟값
  • 배열로 저장 (인덱스 1부터) : 왼쪽 자식 = 2i, 오른쪽 자식 = 2i + 1, 부모 = i / 2
  • 삽입·삭제 O(log n). 우선순위 큐 구현에 사용


Chapter 11. 탐색

순차 탐색 vs 이진 탐색 ⭐⭐⭐

구분 순차 탐색 이진 탐색
방법 처음부터 하나씩 비교 가운데 값과 비교해서 범위를 반씩 줄임
전제 조건 없음 반드시 정렬되어 있어야 함
복잡도 O(n) O(log n)

이진 탐색 과정

1
2
3
mid = (low + high) / 2
찾는 값 < A[mid] → high = mid − 1
찾는 값 > A[mid] → low = mid + 1

예시 : [3, 7, 12, 18, 25, 31, 40] 에서 31 찾기 (인덱스 0부터)

비교 low high mid A[mid] 결과
1 0 6 3 18 31 > 18 → low = 4
2 4 6 5 31 찾음

→ 2번 비교

⚠️ 이진 탐색은 정렬 필수. “정렬 안 된 데이터에도 사용 가능”은 틀린 보기

이진 탐색 트리 (BST) ⭐⭐⭐

  • 모든 노드에 대해 왼쪽 서브트리 < 루트 < 오른쪽 서브트리
  • 중위 순회하면 오름차순으로 정렬된 결과가 나옴 ⚠️ 단골
  • 탐색·삽입·삭제 : 평균 O(log n), 편향 트리가 되면 최악 O(n)
  • 삭제할 노드의 자식이 2개면 왼쪽 서브트리의 최댓값 또는 오른쪽 서브트리의 최솟값으로 대체

예시 : 30, 20, 40, 10, 25, 35 순서로 삽입

1
2
3
4
5
        30
       /  \
     20    40
    /  \   /
  10   25 35
  • 중위 순회 : 10 20 25 30 35 40 (오름차순)
  • 이미 정렬된 순서(10, 20, 30…)로 삽입하면 오른쪽 편향 트리 → O(n)

AVL 트리 ⭐⭐

  • BST의 편향 문제를 해결한 균형 이진 탐색 트리
  • 균형 인수 (BF) = 왼쪽 서브트리 높이 − 오른쪽 서브트리 높이
  • 모든 노드의 BF가 −1, 0, 1 중 하나여야 함. 벗어나면 회전으로 균형 회복
불균형 유형 해결
LL (왼쪽 자식의 왼쪽에 삽입) 오른쪽 회전 1번
RR (오른쪽 자식의 오른쪽에 삽입) 왼쪽 회전 1번
LR (왼쪽 자식의 오른쪽에 삽입) 왼쪽 회전 → 오른쪽 회전
RL (오른쪽 자식의 왼쪽에 삽입) 오른쪽 회전 → 왼쪽 회전
  • 항상 균형 유지 → 탐색 O(log n) 보장

B-트리 ⭐⭐

  • 노드 하나에 여러 개의 키를 저장하는 다원 균형 탐색 트리. 디스크 기반 탐색(DB 인덱스)에 사용

m차 B-트리 조건

항목 조건
노드당 최대 자식 수 m
노드당 최대 키 수 m − 1
최소 자식 수 (루트·단말 제외) ⌈m / 2⌉
루트의 최소 자식 수 2 (단말이 아닐 때)
단말 노드 모두 같은 레벨
  • 3차 B-트리 (2-3 트리) : 노드당 키 1~2개, 자식 2~3개
  • 삽입 시 키가 넘치면(오버플로) 노드를 분할하고 가운데 키를 부모로 올림

B+ 트리 ⭐

  • 실제 데이터는 단말 노드에만 저장, 단말 노드끼리 연결 리스트로 이어짐 → 순차 접근도 빠름

해싱 (Hashing) ⭐⭐⭐

  • 해시 함수로 키 값을 계산해서 저장 위치(주소)를 바로 구함 → 탐색 O(1)

용어

용어 의미
해시 테이블 데이터를 저장하는 표 (버킷 여러 개로 구성)
버킷 / 슬롯 하나의 주소 / 버킷 안의 저장 칸
충돌 (Collision) 서로 다른 키가 같은 주소로 계산되는 현상
동의어 (Synonym) 충돌로 같은 주소를 갖게 된 키들
오버플로 버킷이 꽉 차서 더 저장할 수 없는 상태

해시 함수 종류 ⭐⭐

방법 설명
제산법 (Division) 키를 테이블 크기(주로 소수)로 나눈 나머지 → 가장 많이 사용
제곱법 (Mid-square) 키를 제곱한 뒤 중간 자리를 주소로
폴딩법 (Folding) 키를 여러 부분으로 나눠 더하거나 XOR
기수 변환법 키를 다른 진법으로 변환
숫자 분석법 키의 각 자릿수 분포를 분석해서 고른 자릿수 사용

충돌 해결 ⭐⭐⭐

방법 설명
개방 주소법 충돌 시 테이블의 다른 빈 칸을 찾아 저장
└ 선형 조사 바로 다음 칸(+1, +2, …)을 차례로 확인 → 1차 군집 발생
└ 이차 조사 +1², +2², +3² … 간격으로 확인 → 2차 군집
└ 이중 해싱 두 번째 해시 함수로 이동 간격 결정
체이닝 (Chaining) 같은 주소의 데이터를 연결 리스트로 이어 붙임

예시 : 테이블 크기 7, 해시 함수 key % 7, 선형 조사, 키 10, 17, 24 순서로 삽입

  • 10 % 7 = 3 → 3번 저장
  • 17 % 7 = 3 → 충돌 → 4번 저장
  • 24 % 7 = 3 → 충돌 → 4번도 충돌 → 5번 저장

탐색 복잡도 정리 ⭐⭐

탐색 평균 최악
순차 탐색 O(n) O(n)
이진 탐색 O(log n) O(log n)
이진 탐색 트리 O(log n) O(n) (편향)
AVL 트리 O(log n) O(log n)
해싱 O(1) O(n) (충돌 심할 때)