1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| ┌─────────────────────────────────────────────────────────────────────┐
│ 프로세스 vs 스레드 비교 │
├──────────────────┬──────────────────────┬────────────────────────────┤
│ 항목 │ 프로세스 │ 스레드 │
├──────────────────┼──────────────────────┼────────────────────────────┤
│ 정의 │ 실행 중인 프로그램 │ 프로세스 내의 실행 흐름 │
├──────────────────┼──────────────────────┼────────────────────────────┤
│ 메모리 공간 │ 독립적 (Code,Data, │ Code,Data,Heap 공유 │
│ │ Heap,Stack 각각 보유)│ Stack만 독립 │
├──────────────────┼──────────────────────┼────────────────────────────┤
│ 생성 비용 │ 큼 (fork) │ 작음 (경량 프로세스) │
├──────────────────┼──────────────────────┼────────────────────────────┤
│ 컨텍스트 스위칭 │ 비용 큼 (메모리 맵 │ 비용 작음 (Stack만 전환) │
│ │ 전체 전환) │ │
├──────────────────┼──────────────────────┼────────────────────────────┤
│ 통신 │ IPC 필요 (파이프, │ 공유 메모리로 직접 통신 │
│ │ 소켓, 공유메모리 등) │ (동기화 필요!) │
├──────────────────┼──────────────────────┼────────────────────────────┤
│ 안정성 │ 하나 죽어도 다른 │ 하나 죽으면 전체 프로세스 │
│ │ 프로세스에 영향 없음 │ 에 영향 │
└──────────────────┴──────────────────────┴────────────────────────────┘
★ 핵심: 스레드는 Code/Data/Heap을 공유하고, Stack만 독립
★ 함정: "스레드는 Heap을 공유하지 않는다" → 틀림 (Heap 공유함)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| ┌────────────┐
생성 ────→│ Ready │←───── 타임아웃 (Time-out)
(new) │ (준비) │
└─────┬──────┘
│ Dispatch (스케줄러가 CPU 할당)
▼
┌────────────┐
│ Running │
│ (실행) │
└──┬────┬───┘
I/O 요청 │ │ 실행 완료
(Wait) │ │ (Exit)
▼ ▼
┌──────┐ ┌──────┐
│Blocked│ │Termi-│
│(대기) │ │nated │
└──┬───┘ └──────┘
│ I/O 완료
└──→ Ready로 돌아감
★ Blocked(대기) → Running 직접 전이는 없다!
반드시 Blocked → Ready → Running 순서
★ Ready → Running = Dispatch
★ Running → Ready = Preemption(선점) / Timer Interrupt
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| ┌──────────────────────────────────────────────────────────┐
│ PCB 구성 요소 │
├──────────────────┬───────────────────────────────────────┤
│ PID │ 프로세스 식별 번호 │
│ Process State │ 현재 상태 (Ready/Running/Blocked) │
│ Program Counter │ 다음 실행할 명령어 주소 ★ │
│ CPU Registers │ 레지스터 값 (컨텍스트 스위칭 시 저장) │
│ Memory Info │ 페이지 테이블, 세그먼트 테이블 │
│ I/O Status │ 할당된 I/O 장치 및 파일 목록 │
│ Scheduling Info │ 우선순위, 스케줄링 큐 포인터 │
│ Accounting Info │ CPU 사용 시간, 제한 시간 │
└──────────────────┴───────────────────────────────────────┘
★ 컨텍스트 스위칭 시 현재 프로세스의 PCB에 상태를 저장하고,
다음 프로세스의 PCB에서 상태를 복원한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ 방식 │ 설명 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 파이프(Pipe) │ 단방향 통신 (부모↔자식, FIFO) │
│ 명명 파이프 │ 양방향, 이름으로 접근 (관련 없는 프로세스 간) │
│ (Named Pipe) │ │
├──────────────────┼──────────────────────────────────────────────────┤
│ 메시지 큐 │ 커널에 메시지를 보내고 읽는 방식 │
│ (Message Queue) │ 비동기적 통신 가능 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 공유 메모리 │ 같은 메모리 영역을 공유 (가장 빠름) │
│ (Shared Memory) │ ★ 동기화 문제 직접 처리 필요 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 소켓(Socket) │ 네트워크 통신 (다른 호스트 간에도 가능) │
├──────────────────┼──────────────────────────────────────────────────┤
│ 시그널(Signal) │ 비동기 이벤트 알림 (SIGKILL, SIGTERM 등) │
├──────────────────┼──────────────────────────────────────────────────┤
│ 세마포어 │ 동기화 도구 (프로세스 간 임계영역 보호) │
└──────────────────┴──────────────────────────────────────────────────┘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| ┌──────────┬───────┬─────────────────────────────────────────────────┐
│ 알고리즘 │선점 │ 핵심 특징 & 계산 │
├──────────┼───────┼─────────────────────────────────────────────────┤
│ FCFS │비선점 │ 먼저 온 순서. 호위 효과(Convoy Effect) │
│ │ │ 평균 대기시간 불리 │
├──────────┼───────┼─────────────────────────────────────────────────┤
│ SJF │비선점 │ 실행 시간 짧은 것 우선. 최적 평균 대기시간 ★ │
│ │ │ 기아(Starvation) 가능 │
├──────────┼───────┼─────────────────────────────────────────────────┤
│ SRTF/SRT │선점 │ SJF의 선점 버전. 남은 시간이 더 짧으면 선점 │
├──────────┼───────┼─────────────────────────────────────────────────┤
│ Priority │둘 다 │ 우선순위 숫자가 작을수록 높은 경우가 일반적 │
│ │ │ 기아 → 에이징(Aging)으로 해결 ★ │
├──────────┼───────┼─────────────────────────────────────────────────┤
│ RR │선점 │ Time Quantum(시간 할당량)만큼 돌아가며 실행 │
│ │ │ TQ 크면→FCFS, 작으면→컨텍스트스위칭 오버헤드↑ │
├──────────┼───────┼─────────────────────────────────────────────────┤
│ HRN │비선점 │ (대기시간+서비스시간)/서비스시간 ★ 계산 공식 │
│ │ │ 높은 값 우선 실행. 에이징 기법 적용 │
├──────────┼───────┼─────────────────────────────────────────────────┤
│ MLFQ │선점 │ 여러 큐 + 피드백. 실무에서 가장 일반적 │
│ │ │ 상위 큐: TQ 작음(대화형), 하위: TQ 큼(배치) │
└──────────┴───────┴─────────────────────────────────────────────────┘
★ 계산 공식:
반환시간(Turnaround Time) = 완료시간 - 도착시간
대기시간(Waiting Time) = 반환시간 - 실행시간
응답시간(Response Time) = 처음 CPU 얻은 시간 - 도착시간
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 프로세스: P1(도착:0, 실행:7), P2(도착:2, 실행:4), P3(도착:4, 실행:1), P4(도착:5, 실행:4)
SJF(비선점):
시간 0~7: P1 실행 (먼저 도착했으므로)
시간 7~8: P3 실행 (실행시간 1로 가장 짧음)
시간 8~12: P2 실행 (실행시간 4)
시간 12~16: P4 실행 (실행시간 4)
대기시간:
P1: 0, P2: 8-2-4=2 → 6, P3: 8-4-1=3, P4: 12-5-4=7 → 아니,
P1: 0-0=0, P2: 7-2=5(대기시작~CPU획득 - 실행시간이 아니라 대기한 시간)
정확히:
대기시간 = 시작시간 - 도착시간
P1: 0-0=0, P3: 7-4=3, P2: 8-2=6, P4: 12-5=7
평균 대기시간 = (0+3+6+7)/4 = 4
|
1
2
3
4
5
6
7
8
9
10
11
12
| ┌─────────────────────────────────────────────────────────────────────┐
│ 임계영역 해결 조건 3가지 ★★★ │
├──────────────────┬──────────────────────────────────────────────────┤
│ 상호 배제 │ 하나의 프로세스가 임계영역에 있으면 │
│ (Mutual Excl.) │ 다른 프로세스는 진입 불가 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 진행 │ 임계영역에 아무도 없으면 진입 가능해야 함 │
│ (Progress) │ 무한 대기 방지 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 한정 대기 │ 진입 요청 후 유한 시간 내 진입 보장 │
│ (Bounded Wait) │ 기아 방지 │
└──────────────────┴──────────────────────────────────────────────────┘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ 도구 │ 설명 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 뮤텍스(Mutex) │ 이진 세마포어. Lock/Unlock │
│ │ 소유권 있음 (Lock한 스레드만 Unlock 가능) │
├──────────────────┼──────────────────────────────────────────────────┤
│ 세마포어 │ 정수 변수 + P(wait)/V(signal) 연산 │
│ (Semaphore) │ 카운팅 세마포어: 여러 자원 관리 │
│ │ P(S): S-- (0이면 대기) / V(S): S++ (대기자 깨움)│
├──────────────────┼──────────────────────────────────────────────────┤
│ 모니터(Monitor) │ 고급 동기화 도구 (Java synchronized) │
│ │ 상호 배제를 자동 보장 │
│ │ condition variable로 wait/notify │
├──────────────────┼──────────────────────────────────────────────────┤
│ 스핀락(Spinlock) │ 루프를 돌면서 대기 (Busy Waiting) │
│ │ 짧은 대기에 유리 (컨텍스트스위칭 없음) │
└──────────────────┴──────────────────────────────────────────────────┘
★ 뮤텍스 vs 세마포어:
뮤텍스 = 화장실 열쇠 1개 (소유권 있음)
세마포어 = 주차장 자리 N개 (카운터)
★ 시험 함정: "뮤텍스와 이진 세마포어는 완전히 같다" → 틀림 (소유권 차이)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 필요충분조건 4가지 (모두 동시 만족 시 발생):
1. 상호 배제 (Mutual Exclusion): 자원을 한 번에 하나만 사용
2. 점유와 대기 (Hold & Wait): 보유한 채 다른 자원 대기
3. 비선점 (No Preemption): 강제로 빼앗을 수 없음
4. 환형 대기 (Circular Wait): 원형으로 서로 대기
해결 방법:
┌──────────────────┬──────────────────────────────────────────────────┐
│ 예방(Prevention) │ 4가지 조건 중 하나를 사전에 부정 │
│ │ 자원 낭비 심함 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 회피(Avoidance) │ 안전 상태(Safe State)에서만 자원 할당 │
│ │ ★ 은행가 알고리즘(Banker's Algorithm) │
├──────────────────┼──────────────────────────────────────────────────┤
│ 탐지(Detection) │ 교착상태 발생 허용 후 탐지 │
│ │ 자원 할당 그래프(RAG) 사용 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 회복(Recovery) │ 탐지 후 프로세스 종료 또는 자원 선점으로 복구 │
└──────────────────┴──────────────────────────────────────────────────┘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| ┌──────────────────┬──────────────────────┬────────────────────────────┐
│ 항목 │ 페이징(Paging) │ 세그먼테이션 │
├──────────────────┼──────────────────────┼────────────────────────────┤
│ 분할 기준 │ 고정 크기 (페이지) │ 가변 크기 (논리적 단위) │
├──────────────────┼──────────────────────┼────────────────────────────┤
│ 단편화 │ 내부 단편화 ★ │ 외부 단편화 ★ │
├──────────────────┼──────────────────────┼────────────────────────────┤
│ 주소 변환 │ 페이지번호 + 오프셋 │ 세그먼트번호 + 오프셋 │
│ │ → 페이지 테이블 │ → 세그먼트 테이블 │
├──────────────────┼──────────────────────┼────────────────────────────┤
│ 공유/보호 │ 어려움 │ 용이 (논리적 단위) │
└──────────────────┴──────────────────────┴────────────────────────────┘
★ 시험 핵심:
페이징 → 내부 단편화 (마지막 페이지가 프레임보다 작을 때)
세그먼테이션 → 외부 단편화 (빈 공간은 있지만 연속되지 않을 때)
가상 주소 변환:
논리 주소 = (페이지 번호, 오프셋)
물리 주소 = 페이지 테이블[페이지 번호] → 프레임 번호 + 오프셋
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| 참조열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3 (프레임 3개)
[FIFO] — 먼저 들어온 것을 교체
시간: 7 0 1 2 0 3 0 4 2 3
F1: 7 7 7 2 2 2 2 4 4 4
F2: 0 0 0 0 3 3 3 2 2
F3: 1 1 1 1 0 0 0 3
부재: * * * * * * * * * → 페이지 부재: 9번
[LRU] — 가장 오래 사용하지 않은 것을 교체
시간: 7 0 1 2 0 3 0 4 2 3
F1: 7 7 7 2 2 2 2 4 4 4
F2: 0 0 0 0 0 0 0 2 2
F3: 1 1 1 3 3 3 3 3
부재: * * * * * * * → 페이지 부재: 8번
[OPT(최적)] — 가장 오랫동안 사용되지 않을 것을 교체
시간: 7 0 1 2 0 3 0 4 2 3
F1: 7 7 7 2 2 2 2 2 2 2
F2: 0 0 0 0 0 0 4 4 3
F3: 1 1 1 3 3 3 3 3 → 아니, 다시 계산
... (실제 시험에서는 직접 추적해야 함)
★ Belady's Anomaly: 프레임 수 증가 시 부재 증가 → FIFO에서만 발생
★ LRU, OPT에서는 발생하지 않음
★ OPT는 이론적 최적 (미래를 알아야 하므로 실현 불가)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ 개념 │ 설명 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 스레싱 │ 페이지 부재가 과도하게 발생, CPU 사용률 급감 │
│ (Thrashing) │ → 워킹 셋(Working Set) 모델로 해결 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 워킹 셋 │ 일정 시간 동안 참조된 페이지들의 집합 │
│ (Working Set) │ 이만큼의 프레임을 보장해야 스레싱 방지 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 지역성 │ 시간적 지역성: 최근 참조된 것이 다시 참조됨 │
│ (Locality) │ 공간적 지역성: 근처 주소가 참조될 가능성 높음 │
├──────────────────┼──────────────────────────────────────────────────┤
│ TLB │ 페이지 테이블의 캐시 │
│ │ TLB Hit → 빠른 주소 변환 │
│ │ TLB Miss → 페이지 테이블 조회 │
└──────────────────┴──────────────────────────────────────────────────┘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 요청 큐: 98, 183, 37, 122, 14, 124, 65, 67 (현재 헤드: 53)
┌──────────────────┬──────────────────────────────────────────────────┐
│ 알고리즘 │ 이동 순서 (헤드 위치 53부터) │
├──────────────────┼──────────────────────────────────────────────────┤
│ FCFS │ 53→98→183→37→122→14→124→65→67 │
│ │ 도착 순서 그대로 │
├──────────────────┼──────────────────────────────────────────────────┤
│ SSTF │ 53→65→67→37→14→98→122→124→183 │
│ (최소탐색시간 │ 현재 위치에서 가장 가까운 요청 우선 │
│ 우선) │ 기아 가능 │
├──────────────────┼──────────────────────────────────────────────────┤
│ SCAN (엘리베이터)│ 한쪽 끝까지 이동 후 방향 전환 │
│ │ 53→65→67→98→122→124→183→(끝)→37→14 │
├──────────────────┼──────────────────────────────────────────────────┤
│ C-SCAN │ 한쪽 끝까지 간 후 반대쪽 끝으로 점프 │
│ (Circular SCAN) │ 항상 한 방향으로만 서비스 │
├──────────────────┼──────────────────────────────────────────────────┤
│ LOOK │ SCAN과 유사하지만 마지막 요청까지만 이동 │
│ │ 끝까지 가지 않음 │
└──────────────────┴──────────────────────────────────────────────────┘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ 표기 │ 의미 │
├──────────────────┼──────────────────────────────────────────────────┤
│ O(1) │ 상수 시간 (배열 인덱스 접근, 해시 조회) │
│ O(log n) │ 이진 탐색, 균형 이진 트리 연산 │
│ O(n) │ 선형 탐색, 배열 순회 │
│ O(n log n) │ 효율적 정렬 (합병, 퀵, 힙) │
│ O(n²) │ 버블, 선택, 삽입 정렬 │
│ O(2^n) │ 피보나치 재귀 (메모이제이션 없이) │
│ O(n!) │ 순열 생성 │
└──────────────────┴──────────────────────────────────────────────────┘
속도 순서: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ 자료구조 │ 핵심 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 스택 (Stack) │ LIFO (Last In First Out) │
│ │ push, pop, peek/top │
│ │ 활용: 함수 호출(콜스택), 괄호 검사, 후위표기법 │
│ │ DFS 구현 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 큐 (Queue) │ FIFO (First In First Out) │
│ │ enqueue, dequeue, front, rear │
│ │ 활용: BFS, 스케줄링, 버퍼 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 덱 (Deque) │ 양쪽에서 삽입/삭제 가능 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 우선순위 큐 │ 우선순위가 높은 것 먼저 (Heap으로 구현) │
│ (Priority Queue) │ 삽입 O(log n), 삭제 O(log n) │
└──────────────────┴──────────────────────────────────────────────────┘
|
1
2
3
4
5
6
7
8
9
10
11
12
| 중위(Infix): A + B * C
후위(Postfix): A B C * +
중위 → 후위 변환 (스택 이용):
1. 피연산자 → 바로 출력
2. 연산자 → 스택에 push (단, 스택 top보다 우선순위 낮으면 pop 후 push)
3. '(' → push, ')' → '(' 만날 때까지 pop
후위 표기식 계산 (스택 이용):
예: 3 4 * 2 + → (3*4)+2 = 14
1. 피연산자 → push
2. 연산자 → pop 2개, 연산, 결과 push
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| A
/ \
B C
/ \ \
D E F
전위(Preorder): 루트→왼→오 → A B D E C F (Root-Left-Right)
중위(Inorder): 왼→루트→오 → D B E A C F (Left-Root-Right)
후위(Postorder): 왼→오→루트 → D E B F C A (Left-Right-Root)
레벨(Level): BFS 순서 → A B C D E F
★ 전위+중위 or 중위+후위가 주어지면 트리를 복원할 수 있다
★ 전위+후위만으로는 유일한 트리를 복원할 수 없다
|
1
2
3
4
5
6
7
8
9
10
| • 왼쪽 서브트리 < 루트 < 오른쪽 서브트리
• 중위 순회 시 정렬된 순서 ★
• 탐색/삽입/삭제: 평균 O(log n), 최악 O(n) (편향 트리)
삽입: 탐색 후 적절한 위치에 추가
삭제 3가지 경우:
1. 리프 노드: 그냥 삭제
2. 자식 1개: 자식으로 대체
3. 자식 2개: 중위 후속자(오른쪽 서브트리의 최솟값) 또는
중위 선행자(왼쪽 서브트리의 최댓값)로 대체
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ 트리 │ 핵심 │
├──────────────────┼──────────────────────────────────────────────────┤
│ AVL 트리 │ 모든 노드의 좌우 서브트리 높이 차이 ≤ 1 │
│ │ 회전(LL, RR, LR, RL)으로 균형 유지 │
├──────────────────┼──────────────────────────────────────────────────┤
│ Red-Black 트리 │ 노드에 Red/Black 색 부여, 규칙으로 균형 유지 │
│ │ Java TreeMap/TreeSet 내부 구현 │
├──────────────────┼──────────────────────────────────────────────────┤
│ B-Tree ★★ │ 다진 탐색 트리 (자식이 여러 개) │
│ │ 디스크 I/O 최소화, DB 인덱스에 사용 │
│ │ 차수 m인 B-Tree: 노드당 최대 m개 자식 │
├──────────────────┼──────────────────────────────────────────────────┤
│ B+ Tree ★★ │ B-Tree 변형, 데이터는 리프에만 저장 │
│ │ 리프 노드가 연결리스트로 연결 → 범위 검색 유리 │
│ │ 실제 DB(MySQL InnoDB)에서 사용 │
└──────────────────┴──────────────────────────────────────────────────┘
|
1
2
3
4
5
6
7
8
9
10
11
12
| 최대 힙: 부모 ≥ 자식 (루트가 최댓값)
최소 힙: 부모 ≤ 자식 (루트가 최솟값)
배열로 표현 (인덱스 1부터):
부모: i/2, 왼쪽 자식: 2i, 오른쪽 자식: 2i+1
삽입: 끝에 추가 → 부모와 비교하며 위로 올림 (Heapify Up) O(log n)
삭제: 루트 제거 → 마지막 노드를 루트로 → 아래로 내림 (Heapify Down) O(log n)
힙 생성: O(n) (Bottom-up 방식)
★ 힙은 완전 이진 트리 (Complete Binary Tree)
★ 힙 정렬: 힙 생성 O(n) + n번 추출 O(n log n) = O(n log n)
|
1
2
3
4
5
6
7
8
9
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ BFS │ DFS │
│ (너비 우선 탐색) │ (깊이 우선 탐색) │
├──────────────────┼──────────────────────────────────────────────────┤
│ 큐(Queue) 사용 │ 스택(Stack) 또는 재귀 사용 │
│ 레벨 순서 탐색 │ 한 경로를 끝까지 탐색 후 되돌아감 │
│ 최단 경로(가중치X)│ 사이클 탐지, 위상 정렬 │
│ O(V+E) │ O(V+E) │
└──────────────────┴──────────────────────────────────────────────────┘
|
1
2
3
4
5
6
7
8
9
10
11
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ 크루스칼(Kruskal)│ 간선 중심 — 가중치 오름차순 정렬 후 선택 │
│ │ 사이클 검사: Union-Find 사용 │
│ │ O(E log E) │
│ │ 간선이 적은 희소 그래프에 유리 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 프림(Prim) │ 정점 중심 — 현재 트리에 인접한 최소 간선 선택 │
│ │ 우선순위 큐 사용 │
│ │ O(E log V) (피보나치 힙 시 O(E + V log V)) │
│ │ 간선이 많은 밀집 그래프에 유리 │
└──────────────────┴──────────────────────────────────────────────────┘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ 다익스트라 │ 단일 출발점 최단 경로 │
│ (Dijkstra) │ 음수 가중치 불가 ★ │
│ │ 우선순위 큐: O((V+E) log V) │
├──────────────────┼──────────────────────────────────────────────────┤
│ 벨만-포드 │ 단일 출발점, 음수 가중치 허용 │
│ (Bellman-Ford) │ 음수 사이클 탐지 가능 │
│ │ O(VE) │
├──────────────────┼──────────────────────────────────────────────────┤
│ 플로이드-워셜 │ 모든 쌍 최단 경로 │
│ (Floyd-Warshall) │ DP 기반, O(V³) │
│ │ 음수 가중치 허용 (음수 사이클은 불가) │
└──────────────────┴──────────────────────────────────────────────────┘
★ 시험 함정: "다익스트라는 음수 간선이 있어도 동작한다" → 틀림
|
1
2
3
4
5
| • DAG(Directed Acyclic Graph)에서만 가능
• 선행 관계를 만족하는 순서
• 진입 차수(In-degree) 0인 노드부터 제거
• 큐 기반: O(V+E)
• 활용: 작업 순서, 컴파일 순서, 선수과목
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| ┌─────────────────────────────────────────────────────────────────────┐
│ 해시 충돌 해결 │
├──────────────────┬──────────────────────────────────────────────────┤
│ 체이닝(Chaining) │ 같은 버킷에 연결 리스트로 저장 │
│ │ 장점: 삭제 용이, 적재율 >1 가능 │
│ │ 단점: 추가 메모리(포인터) │
├──────────────────┼──────────────────────────────────────────────────┤
│ 개방 주소법 │ 빈 버킷을 찾아 저장 (테이블 내부에서 해결) │
│ (Open Addressing)│ │
│ ├ 선형 탐사 │ h(k)+1, h(k)+2, ... (1차 군집화 문제) │
│ ├ 이차 탐사 │ h(k)+1², h(k)+2², ... (2차 군집화) │
│ └ 이중 해싱 │ h₁(k), h₁(k)+h₂(k), ... (군집화 최소) │
└──────────────────┴──────────────────────────────────────────────────┘
★ 적재율(Load Factor) = 저장된 항목 수 / 버킷 수
★ 적재율이 높아지면 충돌 증가 → 성능 저하
★ Java HashMap: 적재율 0.75 초과 시 리사이즈 (2배)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| ┌──────────────┬──────────┬──────────┬──────────┬───────┬──────────┐
│ 알고리즘 │ 평균 │ 최악 │ 최선 │안정성 │ 특징 │
├──────────────┼──────────┼──────────┼──────────┼───────┼──────────┤
│ 버블 정렬 │ O(n²) │ O(n²) │ O(n) ★ │ 안정 │ 인접 교환│
│ 선택 정렬 │ O(n²) │ O(n²) │ O(n²) │불안정 │ 최솟값선택│
│ 삽입 정렬 │ O(n²) │ O(n²) │ O(n) ★ │ 안정 │ 거의정렬시│
│ │ │ │ │ │ 매우 빠름│
├──────────────┼──────────┼──────────┼──────────┼───────┼──────────┤
│ 합병 정렬 │O(n log n)│O(n log n)│O(n log n)│ 안정 │ 추가메모리│
│ 퀵 정렬 │O(n log n)│ O(n²) ★ │O(n log n)│불안정 │ 실무최적 │
│ 힙 정렬 │O(n log n)│O(n log n)│O(n log n)│불안정 │ 추가메모리X│
├──────────────┼──────────┼──────────┼──────────┼───────┼──────────┤
│ 계수 정렬 │ O(n+k) │ O(n+k) │ O(n+k) │ 안정 │정수,범위제│
│ 기수 정렬 │ O(d·n) │ O(d·n) │ O(d·n) │ 안정 │자릿수별 │
└──────────────┴──────────┴──────────┴──────────┴───────┴──────────┘
★ 퀵 정렬 최악: 이미 정렬된 배열 + 첫/마지막 원소를 피벗으로 선택 시 O(n²)
★ 안정(Stable): 같은 키 값의 상대적 순서가 유지됨
★ 비교 기반 정렬의 하한: O(n log n) — 이보다 빠를 수 없음
★ 계수/기수 정렬은 비교 기반이 아니므로 O(n log n) 제약 없음
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ 키 │ 정의 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 슈퍼키 │ 유일성을 만족하는 속성 집합 │
│ (Super Key) │ 예: {학번}, {학번, 이름}, {학번, 이름, 학과} │
├──────────────────┼──────────────────────────────────────────────────┤
│ 후보키 │ 유일성 + 최소성 │
│ (Candidate Key) │ 예: {학번}, {주민번호} │
├──────────────────┼──────────────────────────────────────────────────┤
│ 기본키 │ 후보키 중 선택된 하나, NULL 불가 │
│ (Primary Key) │ │
├──────────────────┼──────────────────────────────────────────────────┤
│ 대체키 │ 기본키로 선택되지 않은 후보키 │
│ (Alternate Key) │ │
├──────────────────┼──────────────────────────────────────────────────┤
│ 외래키 │ 다른 릴레이션의 기본키를 참조 │
│ (Foreign Key) │ NULL 허용 가능 ★ │
└──────────────────┴──────────────────────────────────────────────────┘
★ 외래키는 NULL이 가능하다 (참조 무결성과 혼동 주의)
★ 기본키는 NULL 불가 + 중복 불가 (개체 무결성)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 1NF: 모든 속성이 원자값
→ 반복 그룹, 다중 값 속성 제거
2NF: 1NF + 부분 함수 종속 제거
→ 기본키의 일부에만 종속되는 속성 분리
예: {학번, 과목} → 학과 (학번에만 종속) → 분리!
3NF: 2NF + 이행 함수 종속 제거
→ A→B→C에서 A→C를 제거 (B 테이블로 분리)
예: 학번→학과→학과장 → 학과장은 학과 테이블로 분리
BCNF: 3NF + 모든 결정자가 후보키
→ 후보키가 아닌 결정자가 있으면 분리
예: {학번, 과목}→교수, 교수→과목 (교수가 결정자이지만 후보키 아님)
→ 교수-과목 테이블 분리
★ 시험 포인트: "이 테이블은 몇 정규형인가?" 판별 문제
1) 원자값? → 1NF
2) 부분 종속 없음? → 2NF
3) 이행 종속 없음? → 3NF
4) 모든 결정자가 후보키? → BCNF
|
1
2
3
4
5
6
7
8
9
10
| X → Y: X가 Y를 함수적으로 결정
= X 값이 같으면 Y 값도 항상 같음
Armstrong 공리:
• 반사(Reflexivity): Y ⊆ X이면 X → Y
• 증가(Augmentation): X → Y이면 XZ → YZ
• 이행(Transitivity): X → Y, Y → Z이면 X → Z
• 합집합: X → Y, X → Z이면 X → YZ
• 분해: X → YZ이면 X → Y, X → Z
• 의사이행: X → Y, WY → Z이면 WX → Z
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| ┌──────────────────┬────────────┬────────────────┬──────────────────┐
│ 격리 수준 │ Dirty Read │ Non-Repeatable │ Phantom Read │
│ │ │ Read │ │
├──────────────────┼────────────┼────────────────┼──────────────────┤
│ Read Uncommitted │ 발생 ★ │ 발생 │ 발생 │
├──────────────────┼────────────┼────────────────┼──────────────────┤
│ Read Committed │ 방지 │ 발생 ★ │ 발생 │
├──────────────────┼────────────┼────────────────┼──────────────────┤
│ Repeatable Read │ 방지 │ 방지 │ 발생 ★ │
├──────────────────┼────────────┼────────────────┼──────────────────┤
│ Serializable │ 방지 │ 방지 │ 방지 │
└──────────────────┴────────────┴────────────────┴──────────────────┘
★ 위로 갈수록 성능 좋지만 정합성 낮음
★ 아래로 갈수록 정합성 좋지만 성능 낮음
★ MySQL 기본: Repeatable Read, Oracle 기본: Read Committed
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ 기법 │ 설명 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 2PL │ 2단계 로킹 프로토콜 │
│ (Two-Phase │ Growing Phase: 락 획득만 가능 │
│ Locking) │ Shrinking Phase: 락 해제만 가능 │
│ │ ★ 직렬 가능성(Serializability) 보장 │
│ │ ★ 교착상태 방지 못함! │
├──────────────────┼──────────────────────────────────────────────────┤
│ 타임스탬프 기법 │ 트랜잭션 시작 시간으로 순서 결정 │
│ │ 교착상태 없음 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 낙관적 검증 │ 먼저 실행, 커밋 시 충돌 검증 │
│ (Optimistic) │ 충돌이 드문 환경에 적합 │
├──────────────────┼──────────────────────────────────────────────────┤
│ MVCC │ 다중 버전 동시성 제어 │
│ │ 읽기는 과거 스냅샷, 쓰기만 락 │
│ │ 읽기-쓰기 충돌 최소화 │
└──────────────────┴──────────────────────────────────────────────────┘
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| ┌─────────────────────────────────────────────────────────────────────┐
│ B+ Tree 인덱스 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ [내부 노드] : 키만 저장 (검색 가이드 역할) │
│ [리프 노드] : 키 + 데이터 포인터 저장 │
│ [리프 연결] : 리프끼리 연결 리스트로 연결 → 범위 검색에 최적 │
│ │
│ [30 | 60] ← 내부 노드 │
│ / | \ │
│ [10|20] [30|40|50] [60|70|80] ← 리프 노드 (연결됨) │
│ → → │
│ │
│ 장점: │
│ • 범위 검색 O(log n + m) (m: 결과 수) │
│ • 항상 리프까지 내려가므로 검색 시간 일정 │
│ • 리프 노드만 스캔하면 전체 데이터 순회 가능 │
│ │
│ B-Tree vs B+ Tree: │
│ B-Tree: 내부 노드에도 데이터 저장 │
│ B+ Tree: 리프에만 데이터 → 내부 노드에 더 많은 키 저장 가능 │
│ → 트리 높이 ↓ → 디스크 I/O ↓ │
│ │
└─────────────────────────────────────────────────────────────────────┘
인덱스를 사용하면 안 좋은 경우:
• 데이터가 적은 테이블 (풀 스캔이 빠름)
• INSERT/UPDATE/DELETE가 빈번한 컬럼 (인덱스 유지 비용)
• 카디널리티가 낮은 컬럼 (성별 같은 것: M/F 2가지)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 순수 관계 연산:
σ (Selection) : 행 선택 (WHERE) σ age>20(R)
π (Projection) : 열 선택 (SELECT) π name,age(R)
⋈ (Join) : 두 릴레이션 결합
÷ (Division) : R÷S = S의 모든 값을 가진 R의 튜플
일반 집합 연산:
∪ (Union) : 합집합 (호환성 필요: 속성 수, 도메인 동일)
∩ (Intersection): 교집합
− (Difference) : 차집합
× (Cartesian) : 카티션 곱 (R의 행 × S의 행)
조인 종류:
• 세타 조인(θ-join): 임의 조건 R ⋈ R.a > S.b S
• 동등 조인(Equi-join): = 조건 R ⋈ R.a = S.a S
• 자연 조인(Natural Join): 같은 이름의 속성으로 자동 조인 + 중복 속성 제거
• 외부 조인: 매칭 안 되는 튜플도 포함 (NULL 채움)
- 왼쪽 외부 조인(Left Outer Join)
- 오른쪽 외부 조인(Right Outer Join)
- 완전 외부 조인(Full Outer Join)
★ Division 예시:
R(학생, 과목), S(과목) = {DB, OS}
R÷S = DB와 OS 모두 수강한 학생
|
1
2
3
4
5
6
7
8
9
10
11
| -- ROW_NUMBER, RANK, DENSE_RANK 차이 ★★★
SELECT 이름, 성적,
ROW_NUMBER() OVER (ORDER BY 성적 DESC) as rn,
RANK() OVER (ORDER BY 성적 DESC) as rk,
DENSE_RANK() OVER (ORDER BY 성적 DESC) as drk
FROM 학생;
-- 성적: 95, 90, 90, 85 일 때:
-- ROW_NUMBER: 1, 2, 3, 4 (항상 연속)
-- RANK: 1, 2, 2, 4 (동점 후 건너뜀)
-- DENSE_RANK: 1, 2, 2, 3 (동점 후 안 건너뜀) ★
|
1
2
3
4
5
6
7
8
9
10
11
12
| -- NULL 연산: NULL + 5 = NULL, NULL = NULL → Unknown ★
-- NULL 비교: IS NULL / IS NOT NULL (= 사용 불가!)
-- NVL (Oracle) / IFNULL (MySQL) / COALESCE (표준)
SELECT COALESCE(연락처, '없음') FROM 학생;
SELECT IFNULL(연락처, '없음') FROM 학생; -- MySQL
SELECT NVL(연락처, '없음') FROM 학생; -- Oracle
-- 집계 함수와 NULL:
-- COUNT(*): NULL 포함 카운트
-- COUNT(컬럼): NULL 제외 카운트 ★
-- SUM, AVG, MAX, MIN: NULL 제외 후 계산
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| ┌──────────────────┬──────────────────────────────────────────────────┐
│ 기법 │ 설명 │
├──────────────────┼──────────────────────────────────────────────────┤
│ REDO │ 커밋된 트랜잭션을 재실행 │
│ (재실행) │ 장애 후 커밋 기록이 있는 트랜잭션 │
├──────────────────┼──────────────────────────────────────────────────┤
│ UNDO │ 커밋되지 않은 트랜잭션을 취소 │
│ (취소) │ 장애 후 커밋 기록이 없는 트랜잭션 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 로그 기반 │ 트랜잭션 로그를 이용한 회복 │
│ │ 지연 갱신: 커밋 전까지 DB에 반영 안 함(REDO만) │
│ │ 즉시 갱신: 바로 반영(UNDO+REDO 모두 필요) │
├──────────────────┼──────────────────────────────────────────────────┤
│ 체크포인트 │ 특정 시점 상태 저장, 이후부터만 회복 │
│ (Checkpoint) │ 회복 시간 단축 │
├──────────────────┼──────────────────────────────────────────────────┤
│ 그림자 페이징 │ 현재 페이지 테이블 + 그림자 페이지 테이블 │
│ (Shadow Paging) │ 장애 시 그림자 테이블로 복원 │
└──────────────────┴──────────────────────────────────────────────────┘
|