Data Structure & Algorithm
3주차 - 재귀로 짜는 이진 트리 순회, 그리고 BST가 성능을 보장하는 이유
전위/중위/후위 순회를 재귀로 구현하며 결과 배열을 함수 밖에 두는 대신 중첩 함수로 감싸는 방법부터, 이진 트리 구조 자체는 탐색 성능을 보장하지 않는다는 것, 균형이 무너지면 O(log n)이 O(n)이 되는 이유, 캐시 지역성 때문에 DB가 이진 트리 대신 B+트리를 쓰는 이유까지.
Week 03
이번 주에 배우고 이해한 것들.
13개의 기록 최신순
Operating System
3주차 - 리눅스 커널이 쓰는 버디 시스템, 2의 거듭제곱으로만 메모리를 관리하는 이유
seglist의 크기 클래스에 물리적 제약을 더한 버디 시스템 — 반으로 쪼개고, XOR 한 번으로 O(1)에 짝을 찾아 병합하고, 그 대가로 최대 50%까지 내부 단편화를 감수하는 구조를 seglist와 비교하며 정리.
Data Structure & Algorithm
3주차 - DP는 재귀가 반복하는 일을 기억해두는 것, 피보나치와 계단 오르기로 확인
재귀가 같은 하위 문제를 계속 반복 계산할 때 memo로 기억해두는 하향식(탑다운) DP와, 밑바닥 값부터 채워 올라가는 상향식(바텀업) DP를 피보나치 수열과 계단 오르기 문제로 각각 구현.
Data Structure & Algorithm
3주차 - 그래프 탐색, BFS와 DFS를 직접 구현하며 비교
인접 리스트로 무방향/방향 그래프를 만드는 것부터, Queue로 너비 우선 탐색하는 BFS와 재귀로 깊이 우선 탐색하는 DFS를 각각 구현하고 장단점을 비교. 시간 복잡도는 둘 다 O(V+E).
Data Structure & Algorithm
3주차 - Greedy는 매 순간의 최선이 전체 최선이 되는 상황, 거스름돈과 회의실 배정으로 확인
매번 가장 큰 동전을 고르는 거스름돈 문제와, 종료 시간이 가장 빠른 회의부터 고르는 회의실 배정 문제로 그리디 알고리즘이 '순간의 최선'을 반복하는 원리를 확인.
Computer Architecture
3주차 - HDD는 왜 느리고 SSD는 왜 빠를까
HDD는 기계적으로, SSD는 반도체로 동작한다는 차이에서 출발해서 Platter/Track/Sector 구조와 NAND Page/Block 구조, Wear Leveling까지 정리.
Data Structure & Algorithm
3주차 - LCS(최장 공통 부분수열)를 DP 테이블로 구하기
두 문자열을 각각 행과 열에 두고, 같으면 대각선 위에 1을 더하고 다르면 위/왼쪽 중 최댓값을 가져오는 방식으로 LCS 길이를 채워나가는 DP 테이블 구현.
Operating System
3주차 - 가용 블록을 어떻게 관리할까: Implicit / Explicit / Segregated Free List
동적 메모리 할당기가 가용 블록을 관리하는 세 가지 방식을 검색 범위가 좁아지는 순서로 정리 — 크기 필드로 유추하는 implicit부터, pred/succ 포인터로 연결하는 explicit, 크기 클래스별로 리스트를 쪼개는 seglist까지.
C & Compiler
3주차 - Pointer Aliasing 때문에 컴파일러가 최적화를 포기하는 순간
포인터 두 개가 같은 메모리를 가리킬 수 있다는 가능성 하나가 어떻게 레지스터 캐싱, 명령어 재배치, SIMD 벡터화까지 막는지, 그리고 지역 변수와 restrict가 그 가능성을 어떻게 없애는지 정리.
Data Structure & Algorithm
3주차 - 트리가 한쪽으로 쏠리는 것을 막는 균형 이진 트리, RB트리
BST가 데이터 쏠림으로 O(n)까지 느려질 수 있다는 문제에서 출발해서, RB트리의 색 규칙과 Black Height, 그리고 Rotation·Recoloring으로 Double Red를 복구하는 과정을 정리.
Data Structure & Algorithm
3주차 - 위상 정렬, 순서 관계와 위상이 같은 개념인 이유
위상 수학의 '위상'이 순서 관계와 일대일 대응한다는 것에서 출발해서, DAG의 모든 간선 (u,v)에서 u가 v보다 앞에 오도록 정렬하는 위상 정렬을 구현하고 장단점을 정리.
Computer Architecture
3주차 - 음수는 왜 2의 보수로 표현할까
1의 보수는 0이 2개 생긴다는 한계에서 출발해서, 2의 보수가 왜 덧셈 회로 하나로 뺄셈까지 처리하는지, 그리고 carry를 버려도 되는 이유를 Modulo 연산 관점으로 정리.
Graphics
3주차 - JPEG, PNG, GIF는 왜 다르고, 손실은 어디서 생길까
JPEG/PNG/GIF 세 포맷의 장단점을 정리하고, 손실은 부호화가 아니라 색상 양자화 단계에서 생긴다는 것부터 색 밴딩·디더링·하이라이트 클리핑까지.