cs-review-for-interview

PublishedMar 16, 2026

Author강민철

Sourcehttps://www.hanbit.co.kr/product/C4913349732

Description「이것이 취업을 위한 컴퓨터 과학이다 with CS 기술 면접」 요약

#도서

Chapter 01. 기술 면접과 실무를 위한 컴퓨터 과학

왜 CS를 공부하는 개발자가 뛰어난 개발자가 되는가

프로그래밍 언어는 컴퓨터를 조작하기 위한 도구에 불과하다. 프로그래밍 언어 사용법만 아는 것은 컴퓨터를 이해하는 것이 아니다.
CS 기본기가 탄탄한 개발자는 문제 해결 능력이 뛰어나고, 기술적 의사결정을 더 잘 내릴 수 있다.
단순히 "동작하는 코드"를 넘어서 왜 그렇게 동작하는지 이해할 수 있어야 한다.

이 책에서 다루는 CS 주제

주제	핵심 질문
컴퓨터 구조	컴퓨터는 내부적으로 어떻게 동작하는가?
운영체제	프로그램은 어떻게 실행되고 관리되는가?
자료구조	데이터는 어떻게 저장하고 관리하는 것이 효율적인가?
네트워크	컴퓨터끼리 어떻게 데이터를 주고받는가?
데이터베이스	대량의 데이터를 어떻게 관리하는가?

Chapter 02. 컴퓨터 구조

1. 컴퓨터 구조의 큰 그림

핵심 부품 4가지

메인보드 (시스템 버스)

CPU	메모리 (RAM)	보조기억장치	입출력장치
ALU, 제어장치, 레지스터	실행 중 데이터 저장	HDD, SSD	키보드, 모니터

CPU: 명령어를 해석·실행하는 장치. ALU(연산), 제어장치(제어 신호), 레지스터(임시 저장)로 구성
메모리(RAM): 현재 실행 중인 프로그램의 명령어와 데이터를 저장. 주소로 접근
보조기억장치: 전원이 꺼져도 데이터 보존 (HDD, SSD)
입출력장치: 컴퓨터 외부와 소통하는 장치

메인보드와 버스

버스: 컴퓨터 부품 간 데이터를 주고받는 통로
시스템 버스: 주소 버스 + 데이터 버스 + 제어 버스

기본 작동 과정

메모리에 프로그램(명령어+데이터)이 적재됨
CPU가 메모리에서 명령어를 가져옴(fetch)
명령어 해석(decode) → 실행(execute)
결과를 메모리에 저장(store)

2. 데이터: 0과 1로 표현하기

숫자 표현

2진수(binary): 컴퓨터가 이해하는 기본 단위. 0과 1만 사용
16진수(hexadecimal): 2진수를 간결하게 표현 (0x 접두사)
2진수 4자리 = 16진수 1자리
음수 표현: 2의 보수(two's complement) 방식 사용
- 모든 비트를 반전 → 1 더하기
- 예: 0101(+5) → 1010 + 1 = 1011(-5)

문자 인코딩

인코딩	특징
ASCII	7비트, 영문 128자. 한글 등 지원 불가
EUC-KR	완성형 한글 인코딩. 약 2,350자 표현 가능. 일부 글자 누락
유니코드	전 세계 문자를 통합 표현. 코드 포인트로 매핑
UTF-8	유니코드의 가변 길이 인코딩. 1~4바이트. 웹 표준으로 가장 널리 사용

3. CPU

명령어 구조

연산 코드 (opcode)	오퍼랜드 (피연산자/주소)

연산 코드: 수행할 동작 (데이터 전송, 산술/논리 연산, 제어 흐름, 입출력)
오퍼랜드: 연산에 사용될 데이터 또는 데이터의 주소

주소 지정 방식 (Addressing Mode)

방식	설명
즉시 주소 지정	오퍼랜드에 데이터 자체가 담김
직접 주소 지정	오퍼랜드에 데이터의 메모리 주소가 담김
간접 주소 지정	오퍼랜드에 "주소의 주소"가 담김
레지스터 주소 지정	오퍼랜드에 레지스터 번호가 담김
레지스터 간접 주소 지정	레지스터에 저장된 값이 실제 주소

주요 레지스터

프로그램 카운터(PC): 다음에 실행할 명령어의 주소
명령어 레지스터(IR): 현재 실행 중인 명령어
메모리 주소 레지스터(MAR): 접근할 메모리 주소
메모리 버퍼 레지스터(MBR): 메모리와 주고받을 데이터
범용 레지스터: 데이터와 주소 모두 저장 가능
플래그 레지스터: 연산 결과 상태 (부호, 제로, 캐리, 오버플로 등)
스택 포인터(SP): 스택의 꼭대기 주소
베이스 레지스터: 기준 주소 저장

명령어 사이클

인출(Fetch) → 해석(Decode) → 실행(Execute) → 저장(Store)
     ↑                                          │
     └──────────────────────────────────────────┘

인터럽트: 사이클 중간에 발생하는 신호로, CPU가 하던 작업을 중단하고 처리
- 하드웨어 인터럽트: 입출력장치 등 외부 장치에서 발생
- 소프트웨어 인터럽트(예외): 프로그램 실행 중 발생
  - 폴트(fault): 예외 처리 후 해당 명령어 재실행
  - 트랩(trap): 예외 처리 후 다음 명령어 실행 (디버깅의 브레이크포인트 등)
  - 중단(abort): 심각한 오류로 프로세스 강제 종료

CPU 성능 향상 설계

클럭 속도 높이기

클럭(Hz): CPU 동작 속도 단위. 클럭이 높을수록 빠르지만, 발열 등 한계 존재

멀티코어 프로세서

하나의 CPU 안에 여러 코어. 이론상 코어 수만큼 성능 향상
실제로는 소프트웨어의 병렬 처리 설계가 중요

멀티스레드 프로세서

하드웨어적 멀티스레드: 하나의 코어가 동시에 여러 명령어 처리
하이퍼스레딩: 인텔의 SMT(Simultaneous Multithreading) 기술

파이프라이닝

시간 →  T1    T2    T3    T4    T5
명령1: 인출─해석─실행─저장
명령2:      인출─해석─실행─저장
명령3:           인출─해석─실행─저장

세탁기 비유: 세탁→건조→다림→개기를 동시 진행
파이프라인 위험: 데이터 위험, 제어 위험, 구조적 위험

비순서적 실행 (Out-of-Order Execution)

명령어 순서를 변경해 파이프라인 멈춤 최소화

슈퍼스칼라

파이프라인을 여러 개 두어 동시에 여러 명령어 처리

CISC vs RISC

특성	CISC	RISC
명령어	복잡, 가변 길이	단순, 고정 길이
명령어 수	많음	적음
파이프라이닝	어려움	유리
주소 지정	다양	제한적
대표 ISA	x86, x86-64	ARM

4. 메모리

RAM의 종류

종류	특징
DRAM	시간이 지나면 데이터 사라짐. 재충전 필요. 메인 메모리에 사용
SRAM	전원이 연결되어 있으면 데이터 유지. 빠르지만 비쌈. 캐시에 사용
SDRAM	클럭에 동기화된 DRAM
DDR SDRAM	클럭 한 주기에 2번 데이터 전송. DDR4 = 16배 대역폭

메모리 주소

물리 주소: 실제 메모리의 하드웨어 주소
논리 주소: 프로세스가 사용하는 가상의 주소 (0번지부터 시작)
MMU(Memory Management Unit): 논리 주소 → 물리 주소 변환

엔디안 (Byte Order)

빅 엔디안: 높은 바이트부터 저장 (네트워크 바이트 오더)
리틀 엔디안: 낮은 바이트부터 저장 (x86 계열)

캐시 메모리

CPU와 메모리 사이의 속도 차이를 완충하는 고속 메모리
L1 캐시 > L2 캐시 > L3 캐시 (L1이 가장 빠르고 작음)
캐시 히트: 원하는 데이터가 캐시에 있는 경우 → 빠름
캐시 미스: 캐시에 없어 메모리에서 가져와야 하는 경우 → 느림
참조 지역성 원리:
- 시간 지역성: 최근 접근한 데이터를 다시 접근할 가능성이 높음
- 공간 지역성: 접근한 데이터 근처의 데이터에 접근할 가능성이 높음
쓰기 정책:
- Write-through: 캐시와 메모리에 동시 쓰기 (일관성↑, 성능↓)
- Write-back: 캐시에만 쓰고, 교체 시 메모리에 반영 (성능↑)

5. 보조기억장치와 입출력장치

RAID (Redundant Array of Independent Disks)

RAID	방식	특징
RAID 0	스트라이핑	데이터를 여러 디스크에 분산. 속도↑, 안전성✗
RAID 1	미러링	동일 데이터를 두 디스크에 복제. 안전성↑, 용량 50%
RAID 4	스트라이핑 + 패리티 디스크	패리티 디스크 병목
RAID 5	스트라이핑 + 분산 패리티	패리티를 분산 저장. 가장 보편적
RAID 6	스트라이핑 + 이중 패리티	디스크 2개까지 고장 허용

입출력 방식

프로그램 입출력: CPU가 직접 입출력 상태를 확인하고 제어
인터럽트 기반 입출력: 입출력 완료 시 인터럽트로 CPU에 알림
DMA(Direct Memory Access): CPU 개입 없이 입출력장치가 메모리에 직접 접근

Chapter 03. 운영체제

1. 운영체제의 큰 그림

운영체제의 역할

자원(resource) 관리: CPU, 메모리, 입출력장치 등 한정된 자원을 효율적으로 할당
프로세스 관리: 여러 프로그램의 동시 실행을 조율
메모리 관리: 각 프로세스에 필요한 메모리 공간 할당
파일 시스템 관리: 보조기억장치의 데이터를 체계적으로 관리

커널(Kernel)

운영체제의 핵심 기능을 담당하는 부분
하드웨어와 프로그램 사이에서 자원 관리를 수행

이중 모드(Dual Mode)

커널 모드: 하드웨어에 직접 접근 가능. 모든 명령어 실행 가능
사용자 모드: 제한된 명령어만 실행 가능
시스템 콜(System Call): 사용자 모드에서 커널 모드의 기능을 요청하는 인터페이스
- open(), read(), write(), fork(), exec() 등

2. 프로세스와 스레드

프로세스(Process)

실행 중인 프로그램. 운영체제로부터 자원(메모리, CPU 시간)을 할당받음
각 프로세스는 독립된 메모리 공간을 가짐

프로세스 메모리 영역

주소 방향	영역	저장 내용	성장 방향
높은 주소 ↑	스택 (Stack)	함수 호출 정보, 지역 변수	↓ 아래로 성장
	(빈 공간)
	힙 (Heap)	동적 할당 메모리	↑ 위로 성장
	데이터 (Data)	전역 변수, 정적 변수	-
낮은 주소 ↓	코드 (Code)	실행할 명령어 (텍스트 영역)	-

PCB (Process Control Block)

프로세스의 모든 정보를 담은 자료구조
포함 정보: PID, 프로세스 상태, PC, 레지스터 값, 메모리 정보, 열린 파일 목록 등

프로세스 상태

생성(New)
  |
  v
준비(Ready)  <--[타이머 인터럽트]--  실행(Running)
     |                                    |
  [디스패치] --------------------------->  |
                                          | [입출력 요청]
                                          v
                                    대기(Waiting)
                                          | [입출력 완료]
                                          v
                                    준비(Ready)
                                          |
                                          v
                                    종료(Terminated)

문맥 교환(Context Switch)

CPU가 실행 중인 프로세스를 교체할 때 발생
현재 프로세스의 상태(문맥)를 PCB에 저장 → 새 프로세스의 문맥을 복원
오버헤드가 발생하므로 너무 잦은 문맥 교환은 성능 저하 유발

스레드(Thread)

프로세스 내의 실행 흐름 단위
같은 프로세스의 스레드끼리 코드, 데이터, 힙 영역을 공유 (스택만 독립)
멀티프로세스 vs 멀티스레드:
- 멀티프로세스: 프로세스 간 독립적, 하나가 죽어도 다른 프로세스에 영향 없음
- 멀티스레드: 자원 공유로 효율적, 문맥 교환 비용 적음, 하나가 문제 생기면 전체 영향

프로세스 간 통신(IPC)

공유 메모리: 프로세스들이 같은 메모리 공간을 공유
메시지 전달: 커널을 통해 데이터를 주고받음 (파이프, 소켓 등)

3. 동기화와 교착 상태

동기화 문제

레이스 컨디션(Race Condition): 여러 스레드/프로세스가 공유 자원에 동시 접근 → 예측 불가능한 결과
임계 구역(Critical Section): 공유 자원에 접근하는 코드 영역
상호 배제(Mutual Exclusion): 임계 구역에 동시에 하나만 접근 허용

동기화 기법

기법	설명
뮤텍스 락	잠금(lock)/해제(unlock)로 임계 구역 보호. 한 번에 하나의 스레드만 접근
세마포어	정수형 변수로 동시 접근 허용 수 조절. `wait()`으로 감소, `signal()`로 증가
모니터	언어 수준의 동기화 도구. 조건 변수와 함께 사용 (Java의 `synchronized`)

스레드 안전(Thread Safety)

여러 스레드가 동시에 접근해도 올바르게 동작하는 코드
Java: synchronized 키워드, Vector, Hashtable, ConcurrentHashMap
Python: GIL(Global Interpreter Lock)이 존재하여 한 번에 하나의 스레드만 Python 바이트코드 실행

교착 상태(Deadlock) 발생 조건 — 4가지 모두 만족 시 발생

상호 배제: 자원을 한 번에 하나의 프로세스만 사용
점유와 대기: 자원을 점유한 채로 다른 자원을 대기
비선점: 다른 프로세스가 점유 중인 자원을 빼앗을 수 없음
환형 대기: 프로세스들이 원형으로 자원을 대기

교착 상태 해결 방법

예방: 4가지 조건 중 하나 이상을 원천적으로 제거 (환형 대기 제거가 현실적)
회피: 안전 상태를 유지하도록 자원 할당 (은행원 알고리즘)
검출 후 회복: 교착 상태 발생 후 탐지 → 프로세스 강제 종료 또는 자원 선점
무시 (타조 알고리즘): 교착 상태가 드물다면 무시하고, 발생 시 재부팅

4. CPU 스케줄링

기본 개념

CPU 스케줄링: 여러 프로세스에 CPU를 어떤 순서로 배정할지 결정
선점형(Preemptive): 운영체제가 강제로 CPU를 빼앗을 수 있음
비선점형(Non-preemptive): 프로세스가 스스로 CPU를 반납할 때까지 대기

주요 스케줄링 알고리즘

알고리즘	방식	선점 여부	특징
FIFO (FCFS)	먼저 온 순서대로	비선점	단순하지만 긴 작업이 앞에 오면 호위 효과 발생
SJF	실행 시간 짧은 것 먼저	비선점	평균 대기시간 최소화, 기아 현상 가능
라운드 로빈(RR)	타임 슬라이스(퀀텀)만큼 번갈아 실행	선점	공정함. 타임 슬라이스 크기가 핵심
최소 잔여 시간 우선(SRT)	남은 시간 짧은 것 먼저	선점	SJF의 선점형 버전
다단계 큐	우선순위별 별도 큐	-	큐마다 다른 스케줄링 정책 적용
다단계 피드백 큐	큐 간 이동 가능	-	CPU 오래 쓰면 낮은 우선순위 큐로 이동

리눅스 스케줄링 정책

정책	설명
`SCHED_FIFO`	실시간. 높은 우선순위 프로세스 먼저 실행
`SCHED_RR`	실시간. 라운드 로빈 방식
`SCHED_NORMAL`	일반 프로세스. CFS(Completely Fair Scheduler) 사용
`SCHED_BATCH`	배치 작업에 최적화된 스케줄링
`SCHED_IDLE`	CPU 사용이 매우 적은 프로세스용

5. 가상 메모리

물리 주소와 논리 주소

각 프로세스는 0번지부터 시작하는 논리 주소 사용
MMU: 논리 주소를 물리 주소로 변환
실행 중인 프로세스에만 물리 메모리 할당 → 메모리 효율 극대화

스와핑(Swapping)

메모리가 부족할 때 프로세스를 통째로 보조기억장치(스왑 영역)로 내보냄
스왑 아웃: 메모리 → 보조기억장치
스왑 인: 보조기억장치 → 메모리

연속 메모리 할당의 문제

외부 단편화: 빈 공간이 조각나서 큰 프로세스를 적재 못함
내부 단편화: 할당된 메모리 중 사용하지 않는 부분이 발생

페이징 (Paging)

프로세스를 **고정 크기의 페이지(page)**로, 메모리를 **프레임(frame)**으로 나눔
논리 주소 = 페이지 번호 + 오프셋
페이지 테이블: 페이지 번호 → 프레임 번호 매핑
유효 비트: 해당 페이지가 메모리에 적재되어 있는지 표시
보호 비트: 읽기/쓰기 권한 관리

논리 주소  =  [페이지 번호]  +  [오프셋]
                   |
              페이지 테이블 (번호 -> 프레임 매핑)
                   |
                   v
물리 주소  =  [프레임 번호]  +  [오프셋]

TLB (Translation Lookaside Buffer)

페이지 테이블의 캐시. 자주 접근하는 페이지의 매핑 정보를 빠르게 조회
TLB 히트: TLB에서 찾음 → 빠름
TLB 미스: 메모리의 페이지 테이블에서 찾아야 함 → 느림

페이지 교체 알고리즘

알고리즘	방식
FIFO	가장 먼저 적재된 페이지 교체. 간단하지만 비효율적 가능
최적 페이지 교체	앞으로 가장 오래 사용되지 않을 페이지 교체. 이론적 최적, 구현 불가
LRU	가장 오래 전에 사용된 페이지 교체. 현실적으로 가장 널리 사용

스래싱(Thrashing)

페이지 폴트가 과도하게 발생하여 CPU가 실제 작업보다 페이지 교체에 시간을 더 쓰는 상태
프레임 할당이 부족하면 발생
해결: 적절한 프레임 수 할당, 워킹 셋 알고리즘 등 사용

6. 파일 시스템

파일과 디렉터리

파일: 보조기억장치에 저장된 관련 데이터의 모음. 이름과 확장자로 식별
파일 속성: 유형, 크기, 생성/수정 시간, 소유자, 권한 등
파일 디스크립터: 운영체제가 파일에 부여하는 정수 번호 (0: stdin, 1: stdout, 2: stderr)
디렉터리: 파일과 하위 디렉터리를 포함하는 특수한 파일
경로: 절대 경로(루트부터), 상대 경로(현재 위치부터)

파일 할당 방식

연속 할당: 블록을 연속으로 할당. 외부 단편화 문제
연결 할당: 각 블록이 다음 블록의 주소를 가리킴. 순차 접근만 가능
색인 할당: 색인 블록이 모든 블록의 주소를 보관. 랜덤 접근 가능

파일 시스템 종류

윈도우: NTFS, ReFS
리눅스: EXT2, EXT3, EXT4, XFS, ZFS 등
macOS: APFS(Apple File System)

아이노드(inode) 기반 파일 시스템

inode: 파일의 메타데이터(소유자, 권한, 크기, 블록 위치 등)를 저장하는 자료구조
EXT 파일 시스템 구조: 블록 그룹 단위로 관리
- 슈퍼블록 → 그룹 디스크립터 → 데이터 비트맵 → 아이노드 비트맵 → 아이노드 테이블 → 데이터 블록

저널링 파일 시스템

변경 사항을 로그(저널)에 먼저 기록 후 실제 반영
갑작스러운 전원 차단 등에서 복구 가능
메타데이터 저널링: 메타데이터만 로그
풀 저널링: 메타데이터 + 데이터 모두 로그

마운트(Mount)

LNB 메모리의 파일 시스템을 사용하기 위해 운영체제에 연결하는 과정
리눅스에서는 모든 장치가 파일로 표현됨

가상 머신과 컨테이너

가상 머신: 하이퍼바이저 위에 완전한 게스트 운영체제 실행. 무겁지만 격리 수준 높음
컨테이너: 호스트 운영체제의 커널을 공유. 가볍고 빠르지만 격리 수준 낮음
- Docker: 컨테이너 생성/관리 플랫폼
- Kubernetes: 컨테이너 오케스트레이션 도구. 여러 컨테이너의 배포, 확장, 관리를 자동화

Chapter 04. 자료구조

1. 자료구조의 큰 그림

시간 복잡도와 빅 오 표기법

시간 복잡도: 입력 크기(n)에 따른 연산 횟수의 증가 추세
공간 복잡도: 입력 크기에 따른 메모리 사용량의 증가 추세
빅 오 표기법(Big-O): 최악의 경우의 증가율만 표현

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

표기	이름	예시
O(1)	상수	배열 인덱스 접근
O(log n)	로그	이진 탐색
O(n)	선형	단순 순회
O(n log n)	선형 로그	병합 정렬, 퀵 정렬(평균)
O(n²)	이차	이중 반복문, 버블 정렬

자료구조 분류

자료구조
├── 선형 자료구조
│   ├── 배열
│   ├── 연결 리스트
│   ├── 스택
│   └── 큐
└── 비선형 자료구조
    ├── 트리
    │   ├── 이진 트리
    │   ├── 이진 탐색 트리
    │   ├── AVL 트리
    │   ├── 레드-블랙 트리
    │   └── B 트리
    ├── 그래프
    └── 해시 테이블

2. 배열과 연결 리스트

배열(Array)

같은 타입의 데이터를 연속된 메모리 공간에 저장
인덱스로 O(1) 접근 가능 (랜덤 액세스)
크기가 고정 (정적 배열) → 크기 변경 불가
동적 배열 (ArrayList, vector): 꽉 차면 더 큰 배열을 할당하고 복사
삽입/삭제: O(n) — 요소들을 밀거나 당겨야 함

연결 리스트(Linked List)

노드들이 **포인터(참조)**로 연결된 자료구조
각 노드: 데이터 + 다음 노드 포인터
삽입/삭제: O(1) (위치를 알 때)
탐색: O(n) — 순차적으로만 접근 가능

종류	특징
단일 연결 리스트	다음 노드만 가리킴. 한 방향 순회
이중 연결 리스트	이전·다음 노드 모두 가리킴. 양방향 순회
원형 연결 리스트	마지막 노드가 첫 노드를 가리킴

배열 vs 연결 리스트

연산	배열	연결 리스트
인덱스 접근	O(1)	O(n)
맨 앞 삽입/삭제	O(n)	O(1)
중간 삽입/삭제	O(n)	O(1) (위치 알 때)
메모리	연속, 캐시 효율 좋음	불연속, 포인터 오버헤드

3. 스택과 큐

스택(Stack) — LIFO (Last In, First Out)

push: 맨 위에 삽입
pop: 맨 위에서 제거
활용 사례:
- 함수 호출 스택: 함수 호출 시 스택 프레임 push, 반환 시 pop
- 웹 브라우저 뒤로 가기
- 괄호 짝 맞추기
- DFS 구현

큐(Queue) — FIFO (First In, First Out)

enqueue: 뒤에 삽입
dequeue: 앞에서 제거
활용 사례:
- CPU 스케줄링 (준비 큐)
- BFS 구현
- 프린터 대기열
- 버퍼

4. 해시 테이블

해시 함수(Hash Function)

임의의 크기 데이터 → 고정 크기 해시 값 변환
좋은 해시 함수: 충돌 최소화, 균등 분포, 빠른 계산
대표적 해시 알고리즘: MD5, SHA-1, SHA-256, SHA-512 등

해시 테이블 구조

키(Key) → [해시 함수] → 해시 값 → 버킷(인덱스) → 값(Value)

해시 충돌(Hash Collision) 해결

1. 체이닝(Chaining)

같은 버킷에 연결 리스트로 여러 데이터를 저장
장점: 구현 간단, 삭제 용이
단점: 체인이 길어지면 탐색 O(n)

2. 오픈 어드레싱(Open Addressing)

충돌 시 다른 빈 버킷을 찾아 저장
선형 탐사: 바로 다음 버킷부터 순서대로 탐색. 클러스터링 문제
이차 탐사: 1², 2², 3²... 간격으로 탐색
이중 해싱: 두 번째 해시 함수로 탐색 간격 결정

언어별 해시 맵 구현

언어	해시 맵 구현
Java	`HashMap`, `Hashtable`
Python	`dict`
C++	`unordered_map`
Go	`map`

5. 트리(Tree)

트리 기본 용어

용어	설명
루트 노드	최상위 노드
부모/자식 노드	간선으로 연결된 상위/하위 노드
형제 노드	같은 부모를 가진 노드들
리프 노드	자식이 없는 노드
깊이(depth)	루트에서 특정 노드까지의 간선 수
높이(height)	트리에서 가장 긴 깊이
차수(degree)	노드의 자식 수
서브트리	특정 노드를 루트로 하는 부분 트리

트리 순회

순회	순서	결과
전위 순회	루트 → 왼쪽 → 오른쪽	A-B-D-E-C-F
중위 순회	왼쪽 → 루트 → 오른쪽	D-B-E-A-C-F
후위 순회	왼쪽 → 오른쪽 → 루트	D-E-B-F-C-A
레벨 순서 순회	레벨별 왼쪽→오른쪽	A-B-C-D-E-F

이진 트리 종류

종류	특징
정 이진 트리	모든 노드가 0개 또는 2개의 자식
완전 이진 트리	마지막 레벨 전까지 꽉 참, 마지막은 왼쪽부터 채움
포화 이진 트리	모든 레벨이 꽉 참 (완전의 특수 경우)
편향 이진 트리	한쪽으로만 치우친 트리 (사실상 연결 리스트)

힙(Heap)

최대 힙: 부모 ≥ 자식. 루트가 최대값
최소 힙: 부모 ≤ 자식. 루트가 최소값
완전 이진 트리 형태. 배열로 구현 가능
삽입/삭제: O(log n)
활용: 우선순위 큐, 힙 정렬

이진 탐색 트리(BST)

왼쪽 서브트리의 모든 값 < 루트 < 오른쪽 서브트리의 모든 값
탐색/삽입/삭제: 평균 O(log n), 최악 O(n) (편향 시)
삭제 시 3가지 경우:
1. 리프 노드: 그냥 삭제
2. 자식 1개: 자식으로 교체
3. 자식 2개: 왼쪽 서브트리의 최대값 또는 오른쪽 서브트리의 최소값으로 교체

균형 이진 탐색 트리

AVL 트리: 모든 노드의 좌우 서브트리 높이 차이가 1 이하. 회전으로 균형 유지
레드-블랙 트리: 노드에 빨강/검정 색상 부여. 규칙에 따라 균형 유지
- 규칙: 루트와 리프(NIL)는 검정, 빨강 노드의 자식은 검정, 루트→리프 경로의 검정 노드 수 동일
- C++ std::map, Java TreeMap이 사용

B 트리

대량의 데이터를 디스크에서 효율적으로 읽고 쓰기 위한 균형 트리
하나의 노드에 여러 키와 자식 포인터 보유
데이터베이스 인덱스에 핵심적으로 사용
B+ 트리: 실제 데이터는 리프 노드에만 저장, 리프 노드끼리 연결 리스트로 연결 → 범위 검색에 유리

6. 그래프(Graph)

그래프 기본 개념

정점(Vertex/Node): 그래프의 기본 요소
간선(Edge): 정점 간의 연결
방향 그래프: 간선에 방향이 있음 (A→B ≠ B→A)
무방향 그래프: 간선에 방향이 없음 (A-B = B-A)
가중치 그래프: 간선에 비용(가중치)이 부여됨

그래프 표현 방법

인접 행렬(Adjacency Matrix)

2차원 배열로 연결 여부 저장
공간: O(V²)
장점: 두 정점 간 연결 여부 O(1) 확인
단점: 간선이 적으면 (희소 그래프) 메모리 낭비

인접 리스트(Adjacency List)

각 정점마다 연결된 정점들의 리스트
공간: O(V + E)
장점: 메모리 효율적 (희소 그래프)
단점: 두 정점 간 연결 확인 시 리스트 탐색 필요

깊이 우선 탐색(DFS)

스택 또는 재귀로 구현
한 경로를 끝까지 탐색 후 되돌아감 (백트래킹)
시간 복잡도: O(V + E)

너비 우선 탐색(BFS)

큐로 구현
현재 정점의 인접 정점들을 먼저 모두 방문
최단 경로 탐색에 활용 (비가중치 그래프)
시간 복잡도: O(V + E)

최단 경로 알고리즘 — 다익스트라(Dijkstra)

하나의 시작 정점에서 모든 정점까지의 최단 거리 계산
양의 가중치만 처리 가능 (음수 간선 불가)
동작 방식:
1. 시작 정점의 거리 = 0, 나머지 = ∞
2. 방문하지 않은 정점 중 최단 거리 정점 선택
3. 해당 정점을 통해 인접 정점으로의 거리가 더 짧으면 갱신
4. 모든 정점을 방문할 때까지 반복
시간 복잡도: O(V²) 또는 O(E log V) (우선순위 큐 사용 시)

Chapter 05. 네트워크

1. 네트워크의 큰 그림

기본 구조

노드(node): 네트워크에 연결된 장치 (호스트, 라우터, 스위치 등)
간선(link): 노드 간 연결 (유선/무선)
호스트(host): 네트워크 가장자리의 송수신 주체 (클라이언트, 서버)

네트워크 토폴로지

토폴로지	특징
스타형	중앙 장치에 모든 노드 연결. 중앙 장비 고장 시 전체 마비
링형	원형으로 연결. 한 노드 장애 시 전체 영향
버스형	하나의 통신 회선에 모든 노드 연결
트리형	계층적 구조
메시형	모든 노드가 서로 연결. 안정성↑, 비용↑

LAN과 WAN

LAN(Local Area Network): 가까운 거리의 네트워크. 가정, 사무실, 학교 등
WAN(Wide Area Network): 먼 거리의 네트워크. ISP가 제공. 인터넷이 대표적인 WAN

패킷 교환 네트워크

데이터를 패킷(packet) 단위로 쪼개어 전송
각 패킷이 독립적으로 최적 경로를 찾아 이동

호스트 간 데이터 전달 과정 — 캡슐화와 역캡슐화

캡슐화 (송신 측)

응용 계층:    [데이터]
전송 계층:    [TCP/UDP 헤더 | 데이터]        → 세그먼트/데이터그램
네트워크 계층: [IP 헤더 | TCP 헤더 | 데이터]   → 패킷
데이터링크 계층:[이더넷 헤더 | IP | TCP | 데이터 | 트레일러] → 프레임
물리 계층:    비트 스트림으로 변환

역캡슐화 (수신 측): 각 계층에서 해당 헤더를 제거하며 데이터를 추출

프로토콜과 네트워크 참조 모델

OSI 7계층 모델

계층	이름	역할
7	응용 계층	사용자와 직접 상호작용 (HTTP, DNS, FTP 등)
6	표현 계층	데이터 형식 변환, 암호화
5	세션 계층	연결 설정/관리/해제
4	전송 계층	종단 간 신뢰성 있는 전송 (TCP, UDP)
3	네트워크 계층	라우팅, IP 주소 기반 전달
2	데이터 링크 계층	MAC 주소 기반 프레임 전달
1	물리 계층	비트 전기 신호 변환

TCP/IP 4계층 모델

TCP/IP 계층	OSI 대응
응용 계층	응용 + 표현 + 세션
전송 계층	전송
인터넷 계층	네트워크
네트워크 접근 계층	데이터 링크 + 물리

2. 물리 계층과 데이터 링크 계층

이더넷(Ethernet)

현재 LAN에서 가장 널리 사용되는 프로토콜
IEEE 802.3 표준
유선 매체 사용 (UTP/STP 케이블, 광섬유)

유선 매체

UTP 케이블: 꼬임쌍선. 가장 보편적 (Cat5e, Cat6 등)
STP 케이블: 차폐 처리된 꼬임쌍선
광섬유(Fiber): 빛으로 데이터 전송. 고속, 장거리

무선 매체 — Wi-Fi

IEEE 802.11 표준
주요 규격: 802.11n(Wi-Fi 4), 802.11ac(Wi-Fi 5), 802.11ax(Wi-Fi 6)
대역폭: 2.4GHz 대역 + 5GHz 대역

IP 주소와 MAC 주소

구분	IP 주소	MAC 주소
계층	네트워크 계층	데이터 링크 계층
길이	IPv4: 32비트, IPv6: 128비트	48비트
변경	네트워크에 따라 변경 가능	하드웨어에 고정 (원칙적으로)
범위	논리적 주소	물리적 주소

네트워크 인터페이스: NIC

NIC(Network Interface Card): 네트워크 연결을 위한 하드웨어
MAC 주소는 NIC에 부여됨
NIC가 수신한 프레임의 목적지 MAC 주소를 확인하여 자신의 것이 아니면 폐기

허브와 스위치

허브: 물리 계층 장치. 수신한 신호를 모든 포트에 브로드캐스트. 충돌 발생 가능
- 콜리전 도메인: 허브에 연결된 모든 장치가 하나의 충돌 도메인
스위치: 데이터 링크 계층 장치. MAC 주소 테이블로 목적지 포트에만 프레임 전송
- 각 포트가 별도의 충돌 도메인 → 충돌 감소
- 전이중 모드 지원: 동시 송수신 가능

VLAN (Virtual LAN)

물리적 네트워크와 무관하게 논리적으로 네트워크를 분리
같은 스위치에 연결되어 있어도 서로 다른 VLAN이면 통신 불가
보안과 브로드캐스트 도메인 분리에 유용

ARP (Address Resolution Protocol)

IP 주소 → MAC 주소 변환 프로토콜
ARP 요청 (브로드캐스트) → ARP 응답 (유니캐스트) → MAC 주소 획득
ARP 테이블에 매핑 정보 캐시

3. 네트워크 계층 — IP

IP의 핵심 특징

비연결형(connectionless): 사전 연결 설정 없이 패킷 독립 전송
비신뢰적(unreliable): 전송 보장 없음. 패킷 손실, 순서 변경 가능
최선형 전달(best-effort delivery): 최선을 다하지만 보장하지 않음

IPv4 vs IPv6

구분	IPv4	IPv6
주소 길이	32비트	128비트
표기	10진수 (192.168.1.1)	16진수 (2001:0db8:...)
주소 개수	약 43억 개	사실상 무한
헤더	가변 길이, 복잡	고정 길이, 단순

IP 패킷 구조

주요 필드: 버전, TTL(Time To Live), 프로토콜, 출발지/목적지 IP 주소
단편화(Fragmentation): MTU보다 큰 패킷을 분할 전송
플래그(Flags): DF(Don't Fragment), MF(More Fragments)

신뢰할 수 없는 통신과 비연결형 통신

IP 자체는 신뢰성을 보장하지 않음
신뢰성은 상위 계층(TCP)이 담당

IP 주소의 구조

172 . 16 . 12 . 45
[네트워크 부분] . [호스트 부분]

네트워크 부분: 어떤 네트워크에 속하는지
호스트 부분: 해당 네트워크 내 특정 호스트

클래스풀 주소 체계

클래스	첫 번째 옥텟 범위	네트워크/호스트 비율
A	0 ~ 127	8/24 비트
B	128 ~ 191	16/16 비트
C	192 ~ 223	24/8 비트

→ 주소 낭비 문제로 클래스리스 주소 체계 (CIDR) 등장

CIDR (Classless Inter-Domain Routing)

네트워크 부분의 길이를 서브넷 마스크로 자유롭게 지정
표기: 192.168.1.0/24 (앞 24비트가 네트워크 부분)
서브네팅: 큰 네트워크를 작은 서브넷으로 분할
슈퍼네팅: 여러 작은 네트워크를 하나로 합침

공인 IP 주소와 사설 IP 주소

공인 IP: 인터넷에서 고유한 주소. ISP가 할당
사설 IP: 사설 네트워크 내에서만 사용. 인터넷에 직접 접속 불가
- 10.0.0.0/8
- 172.16.0.0/12
- 192.168.0.0/16
NAT(Network Address Translation): 사설 IP ↔ 공인 IP 변환. 공유기가 대표적

IP 주소의 할당

정적 할당: 관리자가 수동으로 IP 주소를 부여
동적 할당 (DHCP): DHCP 서버가 자동으로 IP 주소를 할당·관리
- DHCP Discover → Offer → Request → Acknowledge

ICMP (Internet Control Message Protocol)

IP 통신의 오류 보고·진단을 위한 프로토콜
대표적 활용: ping(연결 확인), traceroute(경로 추적)

라우팅

라우터: 서로 다른 네트워크를 연결하고 패킷의 최적 경로를 결정
라우팅 테이블: 목적지까지의 경로 정보를 저장
정적 라우팅: 관리자가 수동으로 경로 설정. 소규모 네트워크에 적합
동적 라우팅: 라우팅 프로토콜이 자동으로 경로를 학습·갱신
- 거리 벡터 방식 (RIP): 홉 수 기반
- 링크 상태 방식 (OSPF): 전체 네트워크 토폴로지를 파악하여 최적 경로 계산

NAT (Network Address Translation)

사설 IP ↔ 공인 IP를 변환하는 기술
공유기(라우터)가 대표적으로 NAT 수행
NAPT(Network Address Port Translation): IP 주소 + 포트 번호를 함께 변환하여 여러 호스트가 하나의 공인 IP를 공유

4. 전송 계층 — TCP와 UDP

TCP vs UDP

특성	TCP	UDP
연결	연결 지향적 (3-way handshake)	비연결형
신뢰성	보장 (재전송, 순서 보장)	보장 없음
속도	상대적으로 느림	빠름
흐름/혼잡 제어	있음	없음
활용	HTTP, FTP, 이메일	DNS, 스트리밍, 게임

TCP의 연결 — 3-way Handshake

단계	클라이언트	방향	서버
①	SYN 전송	→→→	SYN 수신 (연결 요청)
②	SYN+ACK 수신	←←←	SYN+ACK 전송 (수락 + 응답)
③	ACK 전송	→→→	ACK 수신 → ESTABLISHED

TCP의 연결 해제 — 4-way Handshake

단계	클라이언트	방향	서버
①	FIN 전송	→→→	FIN 수신 (종료 요청)
②	ACK 수신	←←←	ACK 전송 (확인)
③	FIN 수신	←←←	FIN 전송 (서버 종료 준비 완료)
④	ACK 전송 → TIME-WAIT	→→→	ACK 수신 → CLOSED

TIME-WAIT: 클라이언트가 마지막 ACK 전송 후 일정 시간 대기. 지연 패킷 대비

TCP 주요 상태

상태	설명
CLOSED	연결 없음
LISTEN	서버가 연결 요청 대기 중
SYN-SENT	클라이언트가 SYN 전송 후 응답 대기
SYN-RECEIVED	서버가 SYN 수신 후 SYN+ACK 전송
ESTABLISHED	연결 수립 완료. 데이터 전송 가능
FIN-WAIT-1/2	연결 종료 진행 중 (능동적 종료 측)
CLOSE-WAIT	상대방의 FIN 수신 후 종료 대기
TIME-WAIT	마지막 ACK 전송 후 대기

TCP 흐름 제어 (Flow Control)

수신 측의 처리 속도에 맞춰 송신 속도를 조절
슬라이딩 윈도우: 수신 측이 윈도우 크기(한 번에 받을 수 있는 양)를 송신 측에 알려줌

TCP 혼잡 제어 (Congestion Control)

네트워크 혼잡 시 전송 속도를 낮춤
슬로 스타트: 윈도우 크기를 1부터 시작, 지수적으로 증가
혼잡 회피: 임계값 이후 선형적으로 증가
빠른 재전송: 중복 ACK 3개 수신 시 즉시 재전송
빠른 회복: 빠른 재전송 후 윈도우를 절반으로 줄이고 선형 증가

5. 응용 계층 — HTTP의 기초

DNS (Domain Name System)

도메인 이름 → IP 주소 변환
계층적 구조: 루트 DNS → TLD DNS (.com, .kr) → 권한 있는 DNS
DNS 캐시: 이전 조회 결과를 캐싱하여 속도 향상
대표 공용 DNS: Google(8.8.8.8), Cloudflare(1.1.1.1)

URI, URL, URN

URI: 자원을 식별하는 통합 식별자
URL: 자원의 위치로 식별 (scheme://authority/path?query#fragment)
URN: 자원의 이름으로 식별

URL 구성 요소

https://www.example.com:8042/over/there?name=ferret#nose
└─┬─┘ └──────┬──────┘└┬─┘└───┬────┘ └───┬────┘└─┬┘
scheme    authority   port   path      query   fragment

HTTP의 특징

요청-응답 기반: 클라이언트가 요청 → 서버가 응답
무상태(Stateless): 각 요청이 독립적. 이전 요청의 상태를 기억하지 않음
미디어 독립적: 어떤 유형의 데이터든 전송 가능

HTTP 메시지 구조

[요청/응답 라인]     ← 메서드 + URI + 버전 / 버전 + 상태코드 + 사유
[헤더]              ← key: value 쌍. 부가 정보
[빈 줄]
[본문(body)]        ← 실제 전송 데이터 (선택적)

HTTP 메서드

메서드	역할	멱등성	안전
GET	리소스 조회	O	O
POST	리소스 생성/처리	X	X
PUT	리소스 전체 교체	O	X
PATCH	리소스 부분 수정	X	X
DELETE	리소스 삭제	O	X
HEAD	GET과 동일하되 본문 없이 헤더만 응답	O	O

멱등성(Idempotent): 같은 요청을 여러 번 해도 결과가 동일 안전(Safe): 서버의 상태를 변경하지 않음

HTTP 상태 코드

범위	의미	대표 코드
1xx	정보	100 Continue
2xx	성공	200 OK, 201 Created, 204 No Content
3xx	리다이렉션	301 Moved Permanently, 302 Found, 304 Not Modified
4xx	클라이언트 오류	400 Bad Request, 401 Unauthorized, 403 Forbidden, 404 Not Found
5xx	서버 오류	500 Internal Server Error, 502 Bad Gateway, 503 Service Unavailable

6. 응용 계층 — HTTP와 응용

쿠키 (Cookie)

서버가 클라이언트에 저장시키는 작은 데이터
HTTP의 무상태 특성을 보완 → 로그인 상태, 사용자 설정 등 유지
Set-Cookie (서버→클라이언트), Cookie (클라이언트→서버)

캐시 (Cache)

이전에 받은 리소스의 복사본을 저장하여 재사용
조건부 요청: 서버에 리소스가 변경되었는지 확인 후 재사용 여부 결정
- If-Modified-Since / Last-Modified: 시간 기반
- If-None-Match / ETag: 고유 식별자 기반
변경 없으면 304 Not Modified 응답 (본문 없이 캐시 재사용)

콘텐츠 협상 (Content Negotiation)

같은 URI에 대해 클라이언트의 선호에 따라 다른 표현을 제공
요청 헤더: Accept, Accept-Language, Accept-Encoding

HTTPS와 SSL/TLS

HTTPS = HTTP + SSL/TLS (보안 계층 추가)
암호화 방식:
- 대칭키 암호화: 같은 키로 암호화/복호화. 빠르지만 키 교환 문제
- 비대칭키(공개키) 암호화: 공개키로 암호화, 개인키로 복호화. 느리지만 키 교환 안전

TLS 핸드셰이크

단계	클라이언트	방향	서버
①	ClientHello 전송 (지원 cipher suite 목록)	→→→	수신
②	ServerHello 수신 (선택된 cipher suite, 인증서)	←←←	ServerHello 전송
③	인증서 검증 → 키 교환 정보 전송	→→→	대칭키 생성
④	대칭키 생성 완료	←→←→	암호화 통신 시작

인증서(Certificate): CA(인증 기관)가 서버의 공개키를 보증
Cipher Suite: 키 교환 + 대칭 암호화 + 해시 알고리즘의 조합
- 예: TLS_AES_128_GCM_SHA256

7. 현업에서 알아야 할 네트워크

스케일링

스케일 업(Scale Up): 단일 서버의 성능 향상 (CPU, RAM 업그레이드)
스케일 아웃(Scale Out): 서버 대수를 늘려 부하 분산

로드 밸런싱 (Load Balancing)

여러 서버에 트래픽을 분산 배치하는 기술
L4 로드 밸런서: 전송 계층(IP+포트) 기반 분산
L7 로드 밸런서: 응용 계층(URL, 헤더, 쿠키 등) 기반 분산. 더 세밀한 제어 가능

프록시 서버

클라이언트와 서버 사이의 중계 서버
포워드 프록시: 클라이언트 측. 캐싱, 접근 제어, 익명화
리버스 프록시: 서버 측. 로드 밸런싱, 캐싱, SSL 종단, 보안

소켓 프로그래밍

소켓: 네트워크 통신의 종단점(endpoint). IP 주소 + 포트 번호로 식별
서버: socket() → bind() → listen() → accept() → 데이터 송수신
클라이언트: socket() → connect() → 데이터 송수신
블로킹 소켓: 입출력 완료까지 대기
논블로킹 소켓: 입출력 완료를 기다리지 않고 즉시 반환

Chapter 06. 데이터베이스

1. 데이터베이스의 큰 그림

데이터베이스와 DBMS

데이터베이스: 체계적으로 구조화된 데이터의 집합
DBMS(Database Management System): 데이터베이스를 관리하는 소프트웨어
- 대표: MySQL, PostgreSQL, Oracle, SQL Server, MongoDB

파일 대신 데이터베이스를 사용하는 이유

데이터의 일관성, 무결성 보장
동시 접근 제어 (여러 사용자/프로그램이 동시에 안전하게 접근)
효율적인 검색·갱신 (인덱스 활용)
보안과 권한 관리
백업과 복구 기능

테이블의 기본 구조

용어	설명
테이블(릴레이션)	행과 열로 구성된 데이터 집합
행(row/레코드/튜플)	하나의 데이터 항목
열(column/필드/속성)	데이터의 특성/항목
기본키(Primary Key)	각 행을 고유하게 식별하는 열. 중복·NULL 불가
외래키(Foreign Key)	다른 테이블의 기본키를 참조하는 열. 테이블 간 관계 표현

칼럼 타입 (MySQL 기준)

유형	타입 예시
정수	INT, BIGINT, SMALLINT, TINYINT
실수	FLOAT, DOUBLE, DECIMAL
문자열	CHAR(고정), VARCHAR(가변), TEXT
날짜/시간	DATE, TIME, DATETIME, TIMESTAMP
불리언	BOOLEAN (TINYINT(1)로 저장)

2. RDBMS의 기본

트랜잭션 (Transaction)

하나의 논리적 작업 단위. 여러 SQL 문을 묶어 전부 성공하거나 전부 실패
COMMIT: 트랜잭션 확정. 변경사항을 영구 반영
ROLLBACK: 트랜잭션 취소. 변경사항을 되돌림

ACID 속성

속성	설명
원자성(Atomicity)	트랜잭션은 전부 수행되거나 전혀 수행되지 않음 (All or Nothing)
일관성(Consistency)	트랜잭션 전후로 데이터베이스는 일관된 상태 유지
격리성(Isolation)	동시 실행되는 트랜잭션은 서로 간섭하지 않음
지속성(Durability)	COMMIT된 데이터는 영구적으로 보존

격리 수준 (Isolation Level)

격리 수준	Dirty Read	Non-repeatable Read	Phantom Read	성능
Read Uncommitted	O	O	O	가장 빠름
Read Committed	X	O	O	-
Repeatable Read	X	X	O	-
Serializable	X	X	X	가장 느림

Dirty Read: 커밋되지 않은 데이터를 읽음
Non-repeatable Read: 같은 쿼리를 두 번 실행했을 때 결과가 다름 (다른 트랜잭션의 UPDATE)
Phantom Read: 같은 조건의 쿼리에서 행이 추가/삭제됨 (다른 트랜잭션의 INSERT/DELETE)

ERD (Entity-Relationship Diagram)

엔티티(Entity): 데이터로 표현할 대상 (테이블)
속성(Attribute): 엔티티의 특성 (칼럼)
관계(Relationship): 엔티티 간의 연관
- 1:1, 1:N, N:M 관계
- N:M 관계는 중간 테이블(매핑 테이블)로 해소

무결성 제약 조건

개체 무결성: 기본키는 NULL이 될 수 없고 중복 불가
참조 무결성: 외래키는 참조하는 테이블의 기본키에 존재하는 값이거나 NULL
도메인 무결성: 칼럼의 값은 정의된 도메인(타입, 범위)에 부합

3. SQL

DDL (Data Definition Language)

CREATE TABLE: 테이블 생성
ALTER TABLE: 테이블 구조 변경
DROP TABLE: 테이블 삭제

DML (Data Manipulation Language)

INSERT — 데이터 삽입

INSERT INTO users (username, email, birthdate) VALUES ('kim', 'kim@example.com', '1990-01-15');

SELECT — 데이터 조회

SELECT * FROM users;
SELECT username, email FROM users WHERE age >= 20;

UPDATE — 데이터 수정

UPDATE users SET email = 'new@example.com' WHERE user_id = 1;

DELETE — 데이터 삭제

DELETE FROM users WHERE user_id = 1;

주요 SQL 절

절	역할
`WHERE`	조건 필터링
`ORDER BY`	정렬 (ASC/DESC)
`LIMIT`	결과 행 수 제한
`GROUP BY`	그룹별 집계
`HAVING`	GROUP BY 결과에 대한 조건 (WHERE는 그룹화 전, HAVING은 그룹화 후)
`DISTINCT`	중복 제거

집계 함수

COUNT(), SUM(), AVG(), MAX(), MIN()

JOIN — 테이블 결합

JOIN 유형	설명
INNER JOIN	양쪽 테이블에 모두 존재하는 행만 결합
LEFT OUTER JOIN	왼쪽 테이블의 모든 행 + 오른쪽에 매칭되는 행 (없으면 NULL)
RIGHT OUTER JOIN	오른쪽 테이블의 모든 행 + 왼쪽에 매칭되는 행 (없으면 NULL)
FULL OUTER JOIN	양쪽 테이블의 모든 행 결합 (MySQL은 직접 지원 안 함)
CROSS JOIN	모든 행의 조합 (카르테시안 곱)

SELECT customers.name, orders.product_id
FROM customers
INNER JOIN orders ON customers.customer_id = orders.customer_id;

서브쿼리 (Subquery)

쿼리 안에 포함된 또 다른 쿼리
WHERE 절, FROM 절, SELECT 절 등에서 사용 가능

SELECT * FROM users WHERE age > (SELECT AVG(age) FROM users);

4. 인덱스

인덱스란

데이터를 빠르게 검색하기 위한 자료구조 (책의 색인과 동일한 원리)
인덱스 없이 조회: 풀 테이블 스캔 (모든 행을 순차 탐색) → 느림
인덱스 사용 시: 트리 구조(주로 B+ 트리)를 통해 빠른 탐색 → O(log n)

인덱스의 장단점

장점	단점
조회 속도 대폭 향상	추가 저장 공간 필요
ORDER BY, GROUP BY 성능 개선	INSERT/UPDATE/DELETE 시 인덱스도 갱신 → 쓰기 성능 저하

인덱스 종류

클러스터형 인덱스: 테이블의 물리적 정렬 순서와 일치. 테이블당 1개
비클러스터형(보조) 인덱스: 별도의 인덱스 구조. 여러 개 생성 가능

5. 데이터베이스 설계

정규화 (Normalization)

데이터 중복을 최소화하고 무결성을 보장하기 위해 테이블을 분리하는 과정

정규형	조건
제1정규형(1NF)	모든 칼럼 값이 원자값(더 이상 분해 불가능한 값)
제2정규형(2NF)	1NF + 부분 함수 종속 제거 (기본키의 일부에만 종속되는 칼럼 분리)
제3정규형(3NF)	2NF + 이행 함수 종속 제거 (A→B→C에서 A→C 종속 제거)
BCNF	3NF + 모든 결정자가 후보키

반정규화 (Denormalization)

성능 향상을 위해 의도적으로 정규화 규칙을 완화
조회 성능 ↑, 데이터 중복 ↑, 무결성 관리 어려움 ↑
JOIN이 과도할 때, 읽기 성능이 중요한 경우에 고려

6. NoSQL

RDBMS vs NoSQL

RDBMS: 정해진 스키마, 테이블 기반, 관계/조인 지원, ACID 보장
NoSQL: 유연한 스키마, 다양한 데이터 모델, 수평 확장에 유리, 대용량 처리에 강점

NoSQL의 유형

유형	설명	대표
키-값(Key-Value)	키와 값의 쌍으로 저장. 가장 단순하고 빠름	Redis, Memcached
문서(Document)	JSON/BSON 형태의 문서 저장. 유연한 스키마	MongoDB
그래프(Graph)	노드와 관계로 데이터 표현. 소셜 네트워크 등에 적합	Neo4j
컬럼 패밀리	열 기반으로 데이터 저장. 대규모 분석에 강점	Cassandra, HBase

Redis

인메모리 키-값 데이터베이스. 매우 빠른 읽기/쓰기
캐시, 세션 저장소, 실시간 랭킹, 메시지 큐 등에 활용
다양한 자료구조 지원: 문자열, 리스트, 해시, 셋, 정렬 셋
주요 명령어:
- 문자열: SET, GET
- 리스트: LPUSH, RPUSH, LPOP, RPOP, LRANGE, LLEN
영속성(Persistence): RDB 스냅샷, AOF(Append Only File) 방식으로 디스크에 저장 가능
레플리케이션: 마스터-슬레이브 구조로 읽기 분산
캐시 서버로 사용 시 부적절한 데이터베이스의 부하를 줄여 성능 대폭 향상

기술 면접 질문 모음

각 챕터 말미에 수록된 실제 면접 질문과 핵심 답변입니다.

Ch02. 컴퓨터 구조

Q1. 다음 코드의 성능 문제를 찾고 개선 방법을 설명하세요.

int matrix[2000][2000];
for (int j = 0; j < 2000; j++)
    for (int i = 0; i < 2000; i++)
        matrix[i][j] += 1;

A. 열(j)을 기준으로 순회하면 메모리가 행 단위로 저장된 2차원 배열에서 캐시 미스가 2,000번씩 반복 발생합니다. i와 j 루프 순서를 바꿔 행 우선 순회로 변경하면 공간 지역성을 활용하여 캐시 히트율이 올라가고 성능이 대폭 향상됩니다.

Q2. 하이퍼스레딩(SMT) 프로세서에서 프로그램을 개발할 때 주의할 점은?

A. 하이퍼스레딩은 하나의 물리 코어가 두 개의 논리 코어처럼 동작하지만, 실제 연산 유닛은 공유합니다. 따라서 스레드 수를 물리 코어 수에 맞추는 것이 오히려 효율적일 수 있으며, CPU 집약적인 작업에서 논리 코어 수만큼 스레드를 생성하면 오버헤드가 발생할 수 있습니다.

Q3. GPU와 CPU의 차이점은 무엇이며, GPU는 어떤 작업에 유리한가요?

A. CPU는 복잡한 제어 흐름과 순차 처리에 최적화된 소수의 고성능 코어를 가집니다. GPU는 수천 개의 단순한 코어로 대규모 병렬 연산에 특화되어 있습니다. 머신러닝, 그래픽 렌더링, 영상 처리처럼 같은 연산을 대량의 데이터에 반복 적용하는 작업에 GPU가 유리합니다. (CUDA를 통해 GPU 프로그래밍 가능)

Ch03. 운영체제

Q1. 다음 코드에서 문제를 찾고 수정하세요.

int shared_data = 0;

void* increment(void* arg) {
    for (int i = 0; i < 100000; i++)
        shared_data++;  // ← 문제
    return NULL;
}
// 두 스레드가 increment()를 동시에 실행

A. shared_data++는 읽기→증가→쓰기의 3단계 연산인데, 두 스레드가 동시에 접근하면 레이스 컨디션이 발생합니다. 뮤텍스 락(pthread_mutex_lock/unlock)이나 원자적 연산(atomic)으로 임계 구역을 보호해야 합니다.

Q2. Q1에서 나타난 문제를 수정하는 코드를 보여주세요.

A. pthread_mutex_t mutex를 선언하고 increment() 내부에서 pthread_mutex_lock(&mutex)와 pthread_mutex_unlock(&mutex)으로 shared_data++를 감쌉니다.

Q3. 4GB의 프로그램을 64비트 컴퓨터에서 실행할 수 있나요?

A. 가능합니다. 64비트 운영체제는 가상 메모리를 통해 각 프로세스에 매우 넓은 가상 주소 공간(이론상 수 TB)을 제공합니다. 실제 물리 메모리가 4GB 미만이더라도 스와핑을 통해 보조기억장치를 활용하여 실행할 수 있습니다.

Q4. 스레드 안전(Thread-safe)한 서비스를 만들기 위한 조건은?

A. ① 공유 자원 접근 시 뮤텍스/세마포어로 상호 배제 보장 ② 불변 객체(Immutable) 활용으로 공유 자원 자체를 줄임 ③ 스레드 안전한 자료구조(ConcurrentHashMap, Vector) 사용 ④ 가능하면 로컬 변수 위주로 설계하여 공유 상태 최소화

Q5. 리눅스에서 일반 사용자 프로세스가 CPU를 할당받는 과정을 설명하세요.

A. ① 프로세스가 생성되면 준비 큐에 들어감 ② 리눅스의 CFS(Completely Fair Scheduler)가 vruntime(가상 실행 시간)이 가장 작은 프로세스 선택 ③ 선택된 프로세스가 CPU를 할당받아 실행 상태로 전환 ④ 타임 슬라이스 소진 또는 입출력 요청 시 다시 준비/대기 큐로 이동

Q6. 페이지 폴트를 최소화하는 방법은?

A. ① 워킹 셋(자주 사용하는 페이지 집합) 파악 후 충분한 프레임 할당 ② 프리패칭(prefetching): 곧 필요할 페이지를 미리 적재 ③ 데이터 접근 패턴을 지역성 높게 설계 (배열 순차 접근 등) ④ 불필요한 메모리 낭비를 줄여 실제 필요한 페이지에 충분한 프레임 확보

Q7. 스래싱(Thrashing)을 방지하는 방법은?

A. ① 프로세스에 충분한 프레임 할당 ② 워킹 셋 모델: 최근 일정 시간 동안 참조된 페이지만 유지 ③ 동시에 실행되는 프로세스 수(다중프로그래밍 정도)를 줄임 ④ 메모리 증설 또는 스와프 공간 확대

Q8. 파일 디스크립터(File Descriptor)란 무엇인가요?

A. 운영체제가 열린 파일이나 소켓, 파이프 등의 I/O 자원을 식별하기 위해 부여하는 정수 번호입니다. 프로세스별로 독립적으로 관리되며, 0(stdin), 1(stdout), 2(stderr)은 기본으로 할당됩니다. open() 시스템 콜로 파일을 열면 3번부터 순차적으로 할당되며, close()로 반환해야 합니다.

Ch04. 자료구조

Q1. 인접 리스트와 인접 행렬의 차이점과 각각 언제 사용하는지 설명하세요.

A. 인접 행렬은 O(V²) 공간을 사용하지만 두 정점 간 연결 확인이 O(1)로 빠릅니다. 인접 리스트는 O(V+E) 공간으로 희소 그래프에서 메모리 효율적이며, 대부분의 실제 그래프(소셜 네트워크, 도로망)는 희소하므로 인접 리스트를 더 많이 씁니다. 인접 행렬은 연결이 촘촘한 밀집 그래프에 적합합니다.

Q2. BFS와 DFS의 차이점과 각각 어떤 상황에 유리한지 설명하세요.

A. BFS는 큐를 사용하며 가까운 노드부터 탐색하므로 최단 경로 탐색(비가중치)에 적합합니다. DFS는 스택/재귀를 사용하며 한 경로를 끝까지 탐색하므로 경로 존재 여부, 미로 탈출, 사이클 탐지에 적합합니다.

Q3. 큐를 배열로 구현할 때 제공해야 하는 인터페이스를 구현하세요.

class MyQueue:
    def __init__(self):
        self.items = []
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        if self.is_empty(): return None
        return self.items.pop(0)
    def is_empty(self):
        return len(self.items) == 0

Q4. 이진 탐색 트리(BST)에서 모든 노드를 오름차순으로 순회하는 코드를 작성하세요.

A. 중위 순회(왼쪽 → 루트 → 오른쪽)를 사용합니다. BST의 중위 순회 결과는 항상 오름차순으로 정렬됩니다.

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value)
        inorder(node.right)

Q5. 해시 테이블의 장점과 단점을 설명하세요.

A. 장점: 평균 O(1)의 빠른 탐색·삽입·삭제. 단점: ① 해시 충돌 시 최악 O(n) ② 순서 보장 없음 ③ 좋은 해시 함수 설계 필요 ④ 메모리 사용이 비효율적일 수 있음 (버킷의 빈 공간). 정렬된 순회가 필요하면 BST, 순서가 필요 없고 빠른 조회가 중요하면 해시 테이블이 적합합니다.

Q6. 배열 대신 연결 리스트를 쓰는 경우와, 반대로 연결 리스트 대신 배열을 쓰는 경우는?

A. 연결 리스트 선호: 삽입/삭제가 빈번하고 크기 예측이 어려울 때 (O(1) 삽입/삭제). 배열 선호: 인덱스로 빠른 랜덤 접근이 필요할 때 (O(1) 접근), 캐시 효율이 중요할 때, 크기가 고정적일 때.

Ch05. 네트워크

Q1. HTTP 캐시가 오래된 데이터를 반환하는 문제를 어떻게 해결하나요?

A. 조건부 요청을 활용합니다. ETag / If-None-Match 헤더 쌍으로 리소스의 고유 식별자를 비교하거나, Last-Modified / If-Modified-Since 헤더 쌍으로 수정 시각을 비교합니다. 서버가 변경 없음을 확인하면 304 Not Modified를 반환하고 클라이언트는 캐시를 재사용합니다.

Q2. HTTP와 HTTPS의 차이를 설명하세요.

A. HTTPS = HTTP + TLS/SSL 암호화 계층. ① TCP 3-way handshake 후 TLS handshake 추가 진행 ② 비대칭키로 대칭키를 안전하게 교환 ③ 이후 빠른 대칭키 암호화로 데이터 전송 ④ CA가 발급한 인증서로 서버 신원 검증. HTTP는 평문 전송이라 중간자 공격(MITM)에 취약합니다.

Q3. 포워드 프록시와 리버스 프록시의 차이를 설명하세요.

A. 포워드 프록시: 클라이언트 앞에 위치. 클라이언트를 대신해 요청 → 캐싱, 접근 제어, 익명화에 활용. 리버스 프록시: 서버 앞에 위치. 서버를 대신해 응답 → 로드 밸런싱, 캐싱, SSL 종단, DDoS 방어에 활용. 클라이언트는 리버스 프록시의 존재를 모릅니다.

Q4. 스케일 업과 스케일 아웃의 차이를 설명하고 각각 어떤 상황에 적합한지 설명하세요.

A. 스케일 업: 기존 서버의 하드웨어 성능 향상(CPU·RAM 업그레이드). 단순하지만 비용 급증, 한계 존재. 스케일 아웃: 서버 대수 증가. 비용 효율적이고 이론상 무한 확장 가능하지만 로드 밸런서와 분산 설계 필요. 상태 없는(stateless) 서비스는 스케일 아웃에 유리합니다.

Q5. 웹 서버(Web Server)와 웹 애플리케이션 서버(WAS)의 차이와 함께 사용하는 이유는?

A. 웹 서버(Nginx, Apache): 정적 파일(HTML, CSS, 이미지) 전송에 최적화. WAS(Tomcat, Node.js, Django): 동적 비즈니스 로직 처리. 함께 사용하는 이유: ① 웹 서버가 정적 리소스를 직접 처리해 WAS 부하 감소 ② 리버스 프록시로 WAS를 외부에 직접 노출하지 않아 보안 강화 ③ 로드 밸런싱으로 여러 WAS 인스턴스에 요청 분산

Ch06. 데이터베이스

Q1. 트랜잭션 격리 수준 중 Read Committed와 Repeatable Read의 차이는?

A. Read Committed: 커밋된 데이터만 읽지만, 같은 트랜잭션 내에서 같은 쿼리를 두 번 실행하면 다른 결과가 나올 수 있음(Non-repeatable Read 허용). Repeatable Read: 트랜잭션 시작 시점의 스냅샷을 유지하므로 같은 쿼리는 항상 같은 결과 보장. MySQL InnoDB의 기본값이며 MVCC로 구현합니다.

Q2. Employees와 Departments 테이블을 INNER JOIN하는 SQL을 작성하세요.

SELECT e.FirstName, e.LastName, d.DepartmentName
FROM Employees e
INNER JOIN Departments d ON e.DepartmentID = d.DepartmentID;

Q3. 위 결과에서 Finance 부서 직원만 조회하는 SQL은?

SELECT e.FirstName, e.LastName, e.Salary
FROM Employees e
INNER JOIN Departments d ON e.DepartmentID = d.DepartmentID
WHERE d.DepartmentName = 'Finance';

Q4. SQL에서 NULL을 처리하는 방법을 설명하세요.

A. NULL은 값이 없음을 의미하며 = NULL로 비교 불가. ① IS NULL / IS NOT NULL로 비교 ② COALESCE(col, 기본값)으로 NULL 대체 ③ IFNULL(col, 기본값) (MySQL) ④ 집계 함수(COUNT, SUM 등)는 NULL을 자동으로 무시

Q5. NoSQL 데이터베이스란 무엇이고 RDBMS와의 차이는?

A. NoSQL은 Not Only SQL의 약자로 고정된 스키마 없이 다양한 형태의 데이터를 저장합니다. RDBMS: 정형 데이터, 강한 일관성(ACID), 수직 확장에 유리. NoSQL: 비정형·반정형 데이터, 수평 확장 용이, 유연한 스키마, 대용량·고속 처리에 강점. 소셜 미디어의 게시글(문서 DB), 세션 캐싱(키-값), 관계 데이터(그래프 DB) 등에 활용합니다.

Q6. 관계형 DB와 NoSQL 중 어느 것을 선택할지, 어떤 상황에서 판단하나요?

A. RDBMS 선택: 데이터 간 관계가 복잡하고 무결성이 중요한 경우 (금융, 주문/결제). NoSQL 선택: 대용량 데이터를 빠르게 처리해야 하고 스키마가 자주 변하는 경우 (로그, 피드, 세션). 실무에서는 단일 선택보다 목적에 맞게 혼용(폴리글랏 퍼시스턴스)하는 것이 일반적입니다.