컴퓨터공학

이진 탐색 트리

Binary Search Tree

각 노드에서 찾는 값과 비교해 작으면 왼쪽, 크면 오른쪽 서브트리로 내려가는 방식으로 탐색·삽입·삭제하는 트리. 트리 높이가 일 때 연산은 이며, 균형이 잡히면 이라 평균 이지만, 한쪽으로 치우치면 연결리스트처럼 까지 나빠짐(그래서 AVL·레드블랙트리 같은 균형 트리가 필요).

ex) 파일 탐색기가 파일명을 정렬된 순서로 빠르게 찾아주는 원리.

레드블랙트리

Red-Black Tree

각 노드에 빨강/검정 색을 부여하고 "빨간 노드의 자식은 항상 검정", "루트에서 리프까지 검정 노드 수는 어느 경로든 동일" 같은 5가지 불변식을 삽입·삭제 때마다 회전(rotation)과 재색칠로 유지시켜, 트리가 완벽히 균형 잡히진 않아도 높이가 항상 을 넘지 않도록 보장하는 자가균형 이진탐색트리. AVL트리보다 회전 횟수가 적어 삽입·삭제가 잦은 실무 자료구조(C++ STL map, 리눅스 커널 스케줄러)의 표준으로 쓰임.

ex) C++ STL의 map·set이 내부적으로 레드블랙트리로 구현돼 항상 $O(\log n)$ 성능을 보장하는 것.

해시 테이블

Hash Table

키를 해시 함수로 배열 인덱스로 변환해 저장하는 자료구조. 원소 수 과 버킷 수 의 비율인 적재율(load factor) 가 성능을 좌우하며, 체이닝 방식에서는 평균 탐색 시간이 . 서로 다른 키가 같은 인덱스로 매핑되는 충돌은 체이닝(연결리스트로 연결) 또는 개방주소법(다음 빈 자리 탐색)으로 해결함.

힙과 우선순위큐

Heap & Priority Queue

부모 노드가 항상 자식 노드보다 작다(또는 크다)는 조건만 유지하는 완전이진트리로, 정렬된 배열처럼 전체를 정렬할 필요 없이 최솟값(또는 최댓값)만 항상 에 확인하고 에 꺼낼 수 있는 자료구조. 배열 하나로 트리 전체를 표현할 수 있어(인덱스 의 자식이 ) 포인터 없이 구현이 간단함.

ex) 다익스트라 알고리즘이 아직 방문 안 한 정점 중 최단거리 후보를 매번 빠르게 꺼내는 데 우선순위큐를 쓰는 것.

빅오 표기법

Big-O Notation

어떤 상수 와 가 존재해서 이후로는 이 항상 이하가 될 때 이라고 정의함. 즉 입력이 충분히 커졌을 때의 증가율 상한을 나타내는 것이지, 특정 입력에서의 실제 실행시간을 말하는 게 아님.

다익스트라 알고리즘

Dijkstra's Algorithm

출발점의 거리를 0으로, 나머지는 무한대로 초기화한 뒤, 아직 확정 안 된 정점 중 거리가 가장 짧은 정점을 우선순위 큐에서 꺼내 인접 간선을 완화(relaxation)하는 과정을 반복하는 그리디 알고리즘. 이진 힙을 쓰면 시간복잡도는 . 음수 가중치가 있으면 그리디 선택이 깨져서 성립하지 않음(그럴 땐 벨만-포드 사용).

동적 계획법

Dynamic Programming

문제가 겹치는 부분 문제(overlapping subproblems)로 쪼개지고, 부분 문제의 최적해를 조합하면 전체 최적해가 되는 최적 부분구조(optimal substructure)를 가질 때 적용 가능. 예를 들어 피보나치는 처럼 점화식으로 표현되는데, 재귀로 그냥 풀면 이지만 계산한 값을 저장(메모이제이션)하면 으로 줄어듦.

분할 정복

Divide and Conquer

문제를 개의 크기 부분 문제로 나누고, 각각을 재귀적으로 푼 뒤 시간을 들여 합치는 전략. 전체 시간복잡도는 마스터 정리(Master Theorem)로 위 점화식을 풀어 구함 — 예를 들어 병합정렬은 이라 이 나옴.

NP-완전

NP-Completeness

어떤 해가 주어졌을 때 그것이 맞는지 다항 시간에 검증은 가능하지만(NP), 다항 시간에 직접 풀 수 있는 알고리즘은 아직 아무도 못 찾은 문제들의 집합. NP-완전 문제 중 하나라도 다항 시간에 풀리면 NP의 모든 문제가 다항 시간에 풀린다는 게 증명되어 있어서(NP-완전 문제끼리는 서로 다항 시간 환원 가능), 이게 P=NP 문제의 핵심.

정렬 알고리즘 비교

Sorting Algorithms (Quick/Merge/Heap Sort)

기준값(피벗)보다 작은 값과 큰 값으로 나누는 것을 반복하는 퀵정렬(평균 이지만 최악의 경우 ), 배열을 절반씩 나눠 각각 정렬한 뒤 합치는 병합정렬(항상 이지만 추가 메모리 필요), 힙 구조를 이용해 제자리에서 정렬하는 힙정렬처럼, 비교 기반 정렬은 정보이론적으로 보다 빨라질 수 없다는 하한이 증명되어 있음.

ex) 데이터 특성에 따라 실무에서 퀵정렬(평균 속도)과 병합정렬(안정성 보장) 중 다른 것을 선택하는 이유.

그리디 알고리즘

Greedy Algorithm

매 단계에서 지금 당장 가장 좋아 보이는 선택을 하고, 그 선택을 절대 번복하지 않는 전략. 최소신장트리(크루스칼·프림)처럼 문제가 매트로이드 구조를 가지면 그리디 선택이 항상 전역 최적해로 이어진다는 게 증명되지만, 배낭 문제처럼 그렇지 않은 문제에 그리디를 쓰면 최적해를 놓칠 수 있음.

백트래킹

Backtracking

해를 한 조각씩 채워나가는 상태 공간 트리를 깊이우선으로 탐색하다가, 현재까지의 선택이 조건을 절대 만족할 수 없다고 판단되면(가지치기, pruning) 그 지점에서 더 진행하지 않고 이전 선택으로 되돌아가는 탐색법. 가지치기 조건을 얼마나 빨리 걸어주느냐가 실질적인 성능을 좌우함.

근사 알고리즘

Approximation Algorithm

NP-난해 문제를 다항 시간 안에 정확히는 못 풀어도, 알고리즘이 낸 해(ALG)와 실제 최적해(OPT)의 비율인 근사비 를 일정 범위 안으로 보장하는 알고리즘. 예를 들어 인 정점 커버 근사 알고리즘은 항상 최적해의 2배 이내 크기의 해를 보장함.

최대유량 최소컷 정리

Max-Flow Min-Cut Theorem

네트워크에서 소스(source)부터 싱크(sink)까지 흘려보낼 수 있는 최대 유량은, 그래프를 소스 쪽과 싱크 쪽 두 그룹으로 나누는 모든 방법 중 그 경계를 지나는 간선 용량의 합이 최소인 최소컷의 값과 정확히 같다는 정리. 포드-풀커슨 알고리즘은 남은 용량이 있는 경로(증가경로)를 계속 찾아 유량을 흘려보내는 과정을 반복해 이 최댓값에 도달함.

ex) 통신망에서 두 지점 사이 전송 가능한 최대 데이터량이 어느 구간(병목)에서 제한되는지 찾아내는 것.

문자열 매칭(KMP 알고리즘)

String Matching (KMP Algorithm)

텍스트에서 패턴을 찾을 때 순진하게 한 글자씩 밀며 비교하면 최악 이 걸리는데, KMP 알고리즘은 패턴 자기 자신의 접두사·접미사가 겹치는 정보를 미리 계산해두고, 비교가 실패해도 이미 일치했던 부분을 다시 비교하지 않고 실패 함수가 알려주는 위치로 곧장 건너뛰어 전체를 에 해결함.

ex) 문서 편집기의 "찾기" 기능이 수만 자 문서에서도 순식간에 검색어를 찾아내는 원리.

파이프라이닝

Pipelining

명령어 처리를 인출(IF)·해독(ID)·실행(EX)·메모리접근(MEM)·저장(WB) 등 여러 단계로 나누고, 각 단계를 서로 다른 명령어가 동시에 점유하도록 겹쳐 실행하는 기법. 이상적으로는 처리량이 파이프라인 단계 수만큼 늘지만, 이전 명령의 결과가 필요한 데이터 해저드, 분기 예측이 틀리는 제어 해저드가 파이프라인을 멈추게(stall) 만듦.

ex) 현대 CPU가 1초에 수십억 개 명령어를 처리할 수 있는 핵심 이유.

캐시 메모리

Cache Memory

CPU 옆에 붙은 작고 빠른 저장장치로, 최근에 쓴 데이터는 다시 쓰일 가능성이 높다는 시간 지역성과 근처 주소가 함께 쓰인다는 공간 지역성을 이용해 적중률을 높임. 평균 메모리 접근시간(AMAT)은 적중시간에 실패율×실패 페널티를 더해서 계산하며, 이 값을 줄이는 게 캐시 설계의 핵심 목표.

비순차 실행과 분기예측

Out-of-Order Execution & Branch Prediction

파이프라인이 명령어를 프로그램 순서대로만 처리하면 앞 명령의 결과를 기다리며 자주 멈추는데(stall), 비순차 실행은 뒤에 오는 독립적인 명령을 먼저 실행 유닛에 넣어 자원을 놀리지 않고, 나중에 결과만 원래 순서로 재정렬(commit)해 겉으로는 순서대로 실행된 것처럼 보이게 함. 조건 분기는 결과가 나오기 전엔 다음 명령을 알 수 없는데, 과거 분기 이력을 학습해 방향을 미리 추측(분기예측)하고 틀리면 그동안 실행한 걸 버리고 되돌리는 방식으로 파이프라인 손실을 최소화함.

ex) 최신 CPU가 분기 예측에 성공하면 매우 빠르지만, 예측이 자주 틀리는 코드(불규칙한 if문)에서는 성능이 뚝 떨어지는 이유.

명령어 집합 구조(RISC/CISC)

Instruction Set Architecture (RISC vs CISC)

복잡한 연산 하나를 명령어 하나로 처리하도록 다양하고 강력한 명령어를 많이 두는 CISC(x86 등)와, 각 명령어를 단순하게 만들어 한 클럭에 실행되도록 하고 대신 파이프라이닝·비순차실행 같은 하드웨어 최적화를 쉽게 만드는 RISC(ARM, RISC-V 등)로 나뉨. 스마트폰이 배터리로 오래 버텨야 해서 전력 효율이 좋은 RISC 기반 ARM 칩을 쓰는 것처럼, 명령어 집합 선택이 성능·전력·설계 복잡도에 큰 영향을 줌.

ex) 스마트폰(ARM, RISC)과 데스크톱 PC(x86, CISC)가 서로 다른 명령어 집합 구조를 쓰는 이유.

가상 메모리

Virtual Memory

프로세스마다 독립된 가상 주소 공간을 주고, 페이지 테이블을 통해 가상 주소를 실제 물리 주소로 변환하는 기법. 페이지 테이블 조회는 매번 하면 느리니 최근 변환 결과를 캐싱하는 TLB(Translation Lookaside Buffer)를 두며, 필요한 페이지가 물리 메모리에 없으면 페이지 폴트가 발생해 디스크에서 읽어옴.

교착상태

Deadlock

상호배제·점유대기·비선점·순환대기 네 조건(Coffman 조건)이 동시에 성립할 때 발생하는, 프로세스들이 서로 상대가 쥔 자원을 기다리며 영원히 멈춘 상태. 자원 할당 그래프에서 사이클이 생기면 교착상태이며, 은행원 알고리즘(Banker's Algorithm)처럼 자원을 미리 안전하게만 할당하는 회피 전략이나, 네 조건 중 하나를 원천적으로 깨는 예방 전략으로 대응함.

프로세스 스케줄링

Process Scheduling

CPU를 어느 프로세스에 언제 줄지 정하는 정책. FCFS(도착 순서), SJF(최단 작업 우선, 평균 대기시간을 이론적으로 최소화하지만 짧은 작업이 계속 오면 긴 작업이 굶는 기아 문제 발생), 라운드로빈(시간 할당량마다 순환) 등이 있고, 성능은 완료시간에서 도착시간을 뺀 반환시간(turnaround time)으로 평가함.

세마포어와 뮤텍스

Semaphore & Mutex

공유자원에 여러 실행 흐름이 동시에 접근하지 못하게 막는 동기화 도구. 세마포어는 정수 카운터를 두고 P(wait)에서 감소, V(signal)에서 증가시키며 값이 음수가 되면 그 스레드를 블록시키는 방식으로, 카운터를 1로 제한하면 상호배제용 뮤텍스가 됨(뮤텍스는 소유권 개념이 있어 잠근 스레드만 풀 수 있다는 차이).

파일시스템과 저널링

File Systems & Journaling

디스크 위 파일을 블록 단위로 관리하며 어느 블록이 어느 파일에 속하는지 매핑 정보(inode 등)를 유지하는 파일시스템은, 파일을 쓰는 도중 정전이 나면 메타데이터가 일부만 갱신돼 파일시스템 전체가 손상될 위험이 있는데, 실제 데이터를 바꾸기 전에 "무엇을 할 것인지"를 먼저 저널(로그)에 기록해두고, 중간에 장애가 나도 재부팅 시 이 저널을 replay해 일관된 상태로 복구할 수 있게 하는 기법이 저널링.

ex) 노트북 배터리가 갑자기 꺼져도 파일시스템 전체가 깨지지 않고 부팅 시 자동 복구되는 이유.

CAP 정리

CAP Theorem

네트워크 분단(Partition)이 실제로 발생하는 분산 시스템에서는, 모든 노드가 항상 같은 최신 값을 보는 일관성(Consistency)과 모든 요청이 항상 응답받는 가용성(Availability)을 동시에 완벽히 보장할 수 없고 둘 중 하나를 희생해야 한다는 정리. 카산드라는 가용성(AP)을, 전통적 관계형 DB 클러스터는 일관성(CP)을 우선하는 식으로 시스템마다 다른 선택을 함.

합의 알고리즘

Consensus Algorithm (Paxos/Raft)

노드가 죽거나 메시지가 늦게 와도 여러 노드가 결국 하나의 값에 동의하도록 만드는 알고리즘. 제안(prepare/promise)과 수락(accept/accepted) 두 단계로 나뉘며, 전체 노드의 과반수(quorum)가 동의해야 값이 확정되므로 소수 노드가 죽어도 시스템은 계속 동작할 수 있음.

샤딩

Sharding

데이터를 키 값에 따라 여러 서버(샤드)에 나눠 저장하는 기법. 단순 해시 분배는 서버 대수가 바뀌면 거의 모든 데이터를 재배치해야 하는 문제가 있어서, 해시 공간을 원형으로 두고 서버 추가·제거 시 인접 구간만 재배치하면 되는 컨시스턴트 해싱(consistent hashing)을 널리 사용함.

벡터 시계

Vector Clocks

분산 시스템에는 모든 노드가 공유하는 절대적인 시간이 없어서, 어떤 이벤트가 다른 이벤트보다 먼저 일어났는지(인과 순서)를 판단하기 어려운데, 각 노드가 자신과 다른 노드들의 이벤트 카운터를 벡터로 함께 기록하고 메시지를 주고받을 때마다 갱신하면, 두 이벤트의 벡터를 비교해 인과관계가 있는지 아니면 서로 무관하게 동시에 일어난 것인지(concurrent) 판별할 수 있음.

ex) 여러 서버에 분산 저장된 문서의 편집 충돌을 감지해 자동 병합할지 사용자에게 물어볼지 판단하는 것.

메시지 전달 보장

Message Delivery Guarantees (At-Least-Once/Exactly-Once)

분산 시스템에서 메시지가 네트워크 장애로 유실될 수 있어 재전송을 하게 되는데, 이때 메시지가 중복 처리될 수 있는 최소 1회 보장(at-least-once), 아예 유실될 수 있는 최대 1회 보장(at-most-once), 재전송을 해도 중복 없이 딱 한 번만 처리된 것과 같은 효과를 내는 정확히 1회 보장(exactly-once) 중 시스템 요구사항에 맞는 수준을 선택해야 함. 정확히 1회는 멱등성 처리나 중복 제거 로직을 함께 설계해야 실질적으로 달성됨.

ex) 결제 시스템이 네트워크 재시도로 같은 결제가 두 번 청구되지 않도록 멱등키를 사용하는 것.

마이크로컨트롤러와 인터럽트

Microcontroller & Interrupts

CPU, 메모리, 입출력 포트를 하나의 칩에 통합한 소형 컴퓨터. 인터럽트가 발생하면 CPU는 현재 실행 상태를 스택에 저장하고, 인터럽트 벡터 테이블에서 해당 인터럽트에 연결된 인터럽트 서비스 루틴(ISR)의 주소로 즉시 점프해 처리한 뒤 원래 실행으로 복귀함.

ex) 전자레인지나 세탁기의 버튼을 눌렀을 때 즉시 반응하는 제어 칩.

실시간 운영체제

Real-Time Operating System (RTOS)

작업이 정해진 마감시간(deadline) 안에 반드시 끝나야 하는 시스템을 위해, 우선순위가 고정된 작업을 마감이 가까운 순서대로 실행하는 EDF(Earliest Deadline First)나, 주기가 짧은 작업에 높은 우선순위를 주는 RM(Rate Monotonic) 같은 예측 가능한 스케줄링 알고리즘을 사용하는 운영체제.

펌웨어와 부트로더

Firmware & Bootloader

전원이 켜지는 순간 CPU는 아무 프로그램도 메모리에 없는 상태인데, 칩에 영구히 새겨진 아주 작은 초기 코드(부트로더)가 먼저 실행되어 저장장치에서 운영체제나 애플리케이션 펌웨어를 메모리로 읽어들여 실행을 넘겨주는 과정. 펌웨어 업데이트가 중간에 실패해도 부팅 불능(brick) 상태에 빠지지 않도록 이중화된 부트 영역을 두는 설계가 임베디드 기기의 핵심 안전장치.

ex) IoT 기기의 OTA(무선) 펌웨어 업데이트가 실패해도 기기가 완전히 먹통이 되지 않게 설계하는 것.

튜링 머신

Turing Machine

무한한 테이프, 테이프를 읽고 쓰는 헤드, 유한한 상태 집합과 전이 규칙으로 이루어진 계산 모델. "어떤 함수가 계산 가능하다"는 것은 그 함수를 계산하는 튜링 머신이 존재한다는 뜻으로 정의됨(처치-튜링 논제). 튜링 머신이 특정 입력에서 멈출지 여부를 일반적으로 판정하는 알고리즘은 존재하지 않는다는 정지 문제(Halting Problem)의 결정 불가능성이 이론전산학의 핵심 결과.

유한 오토마타

Finite Automata

상태 집합 , 입력 알파벳 , 전이함수 , 시작상태 , 수락상태 집합 로 정의되는 계산 모델. 결정적 오토마타(DFA)는 각 상태에서 입력마다 전이가 하나로 정해지고, 비결정적 오토마타(NFA)는 여러 전이가 가능하지만 두 모델이 인식하는 언어의 집합(정규 언어)은 정확히 같다는 게 증명되어 있음.

문맥 자유 문법

Context-Free Grammar

변수 집합, 종단기호 집합, 생성 규칙, 시작 변수로 이루어진 4-튜플로, 좌변이 항상 변수 하나뿐인 생성 규칙을 반복 적용해 문자열을 유도(derivation)하는 문법 체계. 프로그래밍 언어의 문법이 대부분 이 형태로 정의되며, 이걸로 만든 파스 트리가 컴파일러 구문분석 단계의 결과물.

계산복잡도 클래스

Computational Complexity Classes

다항 시간에 풀 수 있는 문제들의 클래스 P, 답을 다항 시간에 검증만 가능한 NP 위에, 다항 크기의 메모리만 쓰면 시간은 얼마든 걸려도 되는 PSPACE, 지수 시간까지 허용하는 EXPTIME처럼 "얼마나 많은 자원을 허용하느냐"에 따라 문제들을 계층적으로 분류하는 이론. P⊆NP⊆PSPACE⊆EXPTIME라는 포함관계는 증명돼 있지만, 이 포함이 진짜 엄격한지(등호가 아닌지)는 P vs NP를 포함해 상당수가 아직 미해결 문제.

ex) 체스처럼 게임 트리 전체를 봐야 하는 문제가 NP보다 훨씬 어려운 PSPACE급으로 분류되는 이유.

정규표현식과 펌핑 렘마

Regular Expressions & Pumping Lemma

정규표현식으로 표현 가능한 언어(정규언어)는 유한 오토마타로 인식 가능한 언어와 정확히 일치하는데, "괄호가 짝이 맞는 문자열"처럼 셀 수 없이 많은 중첩 구조를 가진 언어는 유한한 상태 수만으로는 표현할 수 없다는 걸 증명하는 도구가 펌핑 렘마. 충분히 긴 문자열은 반복 가능한 부분을 반드시 포함한다는 성질을 이용해, 특정 언어가 정규언어가 아님을 논리적으로 증명함.

ex) 프로그래밍 언어의 괄호 짝 맞추기 검사가 정규표현식만으로는 불가능해서 별도 파서가 필요한 이유.

람다 대수

Lambda Calculus

변수, 함수 정의(), 함수 적용() 세 가지 문법만으로 모든 계산을 표현하는 형식 체계. 함수를 인자에 적용해 본문의 변수를 인자로 치환하는 과정을 베타 축약(β-reduction)이라고 하며, 이 과정을 반복하는 것 자체가 곧 프로그램 실행에 해당함.

타입 시스템

Type System

타입 환경 아래에서 식 가 타입 를 갖는다는 것을 형식적인 추론 규칙으로 판정하는 체계. 커리-하워드 대응에 따르면 "타입은 명제, 프로그램은 증명"에 대응되어서, 타입 체커가 통과한다는 것은 곧 그 명제의 증명이 존재한다는 것과 논리적으로 같은 의미를 가짐.

가비지 컬렉션

Garbage Collection

프로그램이 동적으로 할당한 메모리 중 더 이상 어디서도 참조되지 않는(도달 불가능한) 객체를 자동으로 찾아 회수하는 메모리 관리 기법. 루트(전역변수, 스택)에서 출발해 참조를 따라가며 도달 가능한 객체만 살아남게(mark) 표시하고 나머지를 회수하는 mark-and-sweep 방식이 대표적이며, 참조 카운트가 0이 되는 즉시 회수하는 방식은 순환 참조를 못 잡는다는 한계가 있음.

ex) Java·Python 개발자가 C처럼 매번 직접 메모리를 해제(free)하지 않아도 되는 이유.

어휘분석과 구문분석

Lexical & Syntax Analysis

정규표현식으로 정의된 토큰 패턴을 DFA로 변환해 소스코드를 토큰 스트림으로 쪼개는 어휘분석과, 문맥자유문법을 이용해 토큰들을 문법 규칙에 맞는 파스 트리로 조립하는 구문분석 단계. 구문분석은 위에서 아래로 규칙을 예측해가는 LL 파싱과, 아래에서 위로 규칙을 축약해가는 LR 파싱 두 큰 방식으로 나뉨.

중간코드 생성

Intermediate Code Generation

소스 언어와 목적 기계어 사이에 두는 플랫폼 독립적인 표현. 한 줄에 연산자 하나만 두는 3-주소 코드(예: `t1 = a + b; t2 = t1 * c;`)가 대표적 형태이며, 이 단계를 거치면 최적화와 여러 목적 기계로의 코드 생성을 프론트엔드/백엔드로 깔끔히 분리할 수 있음.

레지스터 할당

Register Allocation

변수마다 동시에 살아있는(생존 구간이 겹치는) 관계를 그래프로 그린 레지스터 간섭 그래프(interference graph)를 만들고, 인접한 두 변수는 다른 레지스터를 쓰도록 그래프 색칠 문제로 변환해 푸는 최적화 단계. 그래프 색칠 자체가 NP-난해라서 실제로는 휴리스틱(간단화·병합·스필)을 사용함.

SSA 형태

Static Single Assignment (SSA) Form

중간코드에서 모든 변수가 프로그램 전체에서 딱 한 번만 값을 대입받도록(재대입 시 새 이름을 붙임, 예: ) 변환한 형태. 어떤 값이 어디서 정의됐는지가 변수 이름만 봐도 명확해져서, 상수 전파나 죽은 코드 제거 같은 컴파일러 최적화 알고리즘을 훨씬 간단하고 강력하게 만들 수 있음 — 분기가 합류하는 지점에서는 어느 경로로 왔는지에 따라 값을 고르는 phi 함수를 둠.

ex) LLVM 같은 현대 컴파일러 인프라가 최적화의 중간 표현으로 SSA를 표준으로 채택한 이유.

코드 최적화 기법

Code Optimization Techniques (Loop Unrolling/Inlining)

반복문 안의 반복 조건 검사·분기 비용을 줄이려 반복 본문을 여러 번 펼쳐 쓰는 루프 언롤링, 함수 호출 오버헤드(스택 프레임 생성 등)를 없애려 호출 지점에 함수 본문을 통째로 복사해 넣는 인라이닝처럼, 프로그램의 겉보기 동작은 그대로 두면서 실행 속도를 높이도록 코드 구조를 바꾸는 컴파일러 최적화 기법들.

ex) 컴파일러 최적화 옵션(-O2, -O3)을 올리면 같은 소스코드에서도 실행 파일 속도가 빨라지는 이유.

TCP 3-way 핸드셰이크

TCP 3-Way Handshake

클라이언트가 SYN(순서번호 초기화)을 보내고, 서버가 SYN-ACK(자신의 순서번호+클라이언트 확인)로 응답하고, 클라이언트가 다시 ACK로 확인하는 3단계 절차. 양쪽이 서로의 초기 순서번호(SEQ)를 교환·확인해야 이후 패킷의 순서를 맞추고 유실을 감지할 수 있기 때문에 최소 3번의 교환이 필요함.

OSI 7계층

OSI 7-Layer Model

물리(전기신호)-데이터링크(MAC 주소, 프레임)-네트워크(IP 주소, 라우팅)-전송(TCP/UDP, 포트)-세션(연결 관리)-표현(인코딩·암호화)-응용(HTTP 등) 7개 계층으로 통신을 나눈 개념 모델. 각 계층은 바로 아래 계층이 제공하는 서비스만 이용하고 자신의 서비스만 위 계층에 제공해, 계층 간 독립적인 교체·발전이 가능하게 함.

CSMA/CD

CSMA/CD

전송 전 회선이 비어있는지 감지(Carrier Sense)하고, 여러 기기가 동시에 감지 후 전송해 충돌이 나면(Collision Detection) 즉시 전송을 멈추고 무작위 시간만큼 기다렸다 재전송하는 방식. 재전송 대기시간은 충돌이 반복될수록 대기 범위를 2배씩 넓히는 지수 백오프(exponential backoff)로 정해, 충돌이 잦은 상황에서 재충돌 확률을 낮춤.

라우팅 프로토콜

Routing Protocol (BGP/OSPF)

이웃한 라우터끼리 자신이 아는 최단거리 정보만 주고받아 벨만-포드 방식으로 경로를 계산하는 거리벡터 방식(옛 RIP)과, 전체 네트워크 지도를 모든 라우터가 공유한 뒤 각자 다익스트라로 최단경로를 계산하는 링크상태 방식(OSPF)이 있음. 인터넷 전체를 잇는 BGP는 최단거리보다 정책(어느 통신사를 거칠지)을 우선하는 경로벡터 방식.

DNS

Domain Name System

도메인 이름을 IP로 바꿀 때, 루트 서버 → 최상위도메인(.com 등) 서버 → 권한 있는(authoritative) 서버 순으로 계층을 타고 내려가며 질의하는 분산 계층형 시스템. 사용자 단말은 보통 이 과정을 대신 처리해주는 재귀적 리졸버(recursive resolver)에게 한 번만 물어보고 결과를 캐싱해 다음 조회를 빠르게 함.

TCP 혼잡제어

TCP Congestion Control

네트워크가 얼마나 혼잡한지 알 수 없는 상태에서, 처음엔 전송 속도(혼잡 윈도우)를 매 왕복마다 2배로 늘리다가(slow start) 임계치를 넘으면 조금씩만 늘리고(혼잡 회피), 패킷 손실이 감지되면 윈도우를 절반으로 확 줄이는 방식(AIMD: 더할 땐 선형, 줄일 땐 배수)으로 네트워크 용량에 맞춰 전송 속도를 계속 적응시키는 알고리즘.

ex) 같은 인터넷 회선에서 여러 사람이 동시에 다운로드해도 대역폭을 공평하게 나눠 쓰게 되는 이유.

NAT와 서브네팅

NAT & Subnetting

IPv4 주소가 부족한 상황에서, 한 공유기 안의 여러 기기가 사설 IP(192.168.x.x 등)를 쓰다가 외부와 통신할 때만 공유기의 공인 IP 하나로 변환해 내보내는 NAT(네트워크 주소 변환)와, 하나의 IP 대역을 서브넷 마스크로 잘게 쪼개 여러 개의 독립된 네트워크로 나누는 서브네팅. 이 둘 덕분에 한정된 공인 IP로도 수많은 사설 기기를 인터넷에 연결할 수 있음.

ex) 집 안의 스마트폰·노트북·TV가 모두 같은 와이파이 공유기의 공인 IP 하나로 인터넷에 나가는 원리.

ACID

ACID Properties

트랜잭션은 전부 실행되거나 전혀 안 되거나 둘 중 하나인 원자성(Atomicity), 제약조건을 항상 만족하는 상태로만 전이하는 일관성(Consistency), 동시 실행 트랜잭션이 서로 간섭하지 않는 것처럼 보이는 고립성(Isolation), 커밋된 결과는 시스템 장애 후에도 유지되는 지속성(Durability)을 보장해야 한다는 원칙. 고립성은 격리 수준을 낮추면 성능은 오르지만 이상현상(dirty read 등)이 생길 위험도 커지는 트레이드오프가 있음.

정규화

Normalization

한 속성 값이 다른 속성 값을 결정하는 함수적 종속성(functional dependency)을 분석해, 기본키가 아닌 속성이 기본키 전체가 아닌 일부에만 종속되는 부분종속(2NF 위반)이나, 다른 비키 속성을 거쳐서만 종속되는 이행종속(3NF 위반)을 제거하도록 테이블을 쪼개는 과정. 정규화를 많이 할수록 데이터 중복은 줄지만 조인이 늘어 조회 성능은 떨어질 수 있음.

트랜잭션 격리 수준

Transaction Isolation Levels

커밋 안 된 데이터를 읽는 더티 리드(dirty read), 같은 행을 두 번 읽었는데 값이 바뀌는 반복불가능 읽기(non-repeatable read), 같은 조건으로 다시 조회했는데 행 개수가 달라지는 팬텀 읽기(phantom read) 세 이상현상을 어디까지 허용할지에 따라 Read Uncommitted < Read Committed < Repeatable Read < Serializable 순으로 격리 수준이 강해짐.

B+ 트리 인덱스

B+ Tree Index

한 노드가 여러 개의 키(분기 인수, fanout)를 갖도록 만들어 트리 높이를 낮춘 균형 탐색 트리. 실제 데이터는 리프 노드에만 저장하고 리프끼리 연결리스트로 이어놓아서, 특정 값 탐색은 (는 분기 인수)이고 범위 탐색도 리프를 따라가면 되어 매우 효율적임 — 이게 대부분의 DB 인덱스가 B+트리를 쓰는 이유.

다중버전 동시성 제어

Multi-Version Concurrency Control (MVCC)

읽기 작업이 쓰기 작업을 락으로 막지 않도록, 데이터를 수정할 때 기존 값을 지우는 대신 새 버전을 추가로 만들어두고, 각 트랜잭션은 자신이 시작한 시점 기준의 스냅샷(예전 버전)을 읽게 하는 동시성 제어 기법. 읽기와 쓰기가 서로 블로킹하지 않아 락 기반 방식보다 동시 처리량이 훨씬 높아, PostgreSQL·MySQL(InnoDB) 등 현대 RDBMS 대부분이 채택하고 있음.

ex) 한 사용자가 데이터를 수정하는 동안에도 다른 사용자가 락 대기 없이 이전 값을 계속 조회할 수 있는 것.

쿼리 최적화와 실행계획

Query Optimization & Execution Plans

같은 결과를 내는 SQL 쿼리라도 테이블을 어느 순서로 조인하는지, 인덱스를 쓸지 전체 테이블을 훑을지에 따라 실행 시간이 수백 배 차이 날 수 있는데, DB 옵티마이저는 테이블 통계(행 수, 값 분포)를 바탕으로 여러 실행 방법의 예상 비용을 계산해 가장 빠를 것으로 예측되는 실행계획을 자동으로 선택함. 개발자가 이 실행계획을 직접 확인(EXPLAIN)해 예상과 다르게 느린 부분을 찾아 인덱스를 추가하는 등 튜닝하는 게 실무의 핵심 역량.

ex) 느린 쿼리를 EXPLAIN으로 분석해 인덱스 하나 추가로 실행 시간을 수십 배 줄이는 튜닝 작업.

웹서버 아키텍처

Web Server Architecture

요청마다 스레드/프로세스를 하나씩 할당하는 thread-per-request 방식은 구현이 단순하지만 동시접속이 많아지면 컨텍스트 스위칭 비용이 커지고, Nginx처럼 이벤트 루프 하나가 논블로킹 I/O로 수많은 연결을 처리하는 이벤트 기반 방식은 적은 자원으로 훨씬 많은 동시접속을 처리할 수 있음.

로드밸런싱과 캐싱

Load Balancing & Caching

요청을 서버에 순서대로 돌리는 라운드로빈이나 현재 연결 수가 가장 적은 서버로 보내는 최소연결 방식으로 트래픽을 분산하는 로드밸런싱과, 자주 조회되지만 자주 안 바뀌는 데이터를 메모리에 캐싱해 DB 부하를 줄이는 기법. 캐시 용량이 찼을 때 어떤 데이터를 지울지는 가장 오래 안 쓴 것부터 지우는 LRU(Least Recently Used)가 대표적.

컨테이너와 가상화

Containers & Virtualization (Docker/Kubernetes)

하이퍼바이저로 하드웨어 전체를 가상화해 완전히 독립된 OS를 여러 개 띄우는 전통적 가상머신과 달리, 컨테이너는 하나의 커널을 공유하되 리눅스의 네임스페이스(격리된 파일시스템·네트워크 뷰)와 cgroups(CPU·메모리 사용량 제한)로 프로세스를 격리해서, 훨씬 가볍고 빠르게 실행 환경을 격리함.

CI/CD 파이프라인

CI/CD Pipeline

개발자가 코드를 저장소에 올릴 때마다 자동으로 빌드·테스트를 실행해 문제를 즉시 발견하는 지속적 통합(CI)과, 테스트를 통과한 코드를 사람 개입 없이(또는 최소한의 승인만으로) 자동으로 운영 서버까지 배포하는 지속적 배포(CD)를 연결한 자동화 파이프라인. 배포 주기를 몇 주에서 하루에도 여러 번으로 단축시켜 소프트웨어 개발 속도를 근본적으로 바꿔놓음.

ex) 코드를 GitHub에 푸시하면 자동으로 테스트가 돌고 통과하면 몇 분 안에 실제 서비스에 반영되는 것.