컴퓨터과학·2025년 4월 24일
BFS와 DFS: 그래프 탐색의 두 축
미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?
#CS#Algorithm#Graph#Search
개발과 기술에 대한 이야기를 기록합니다.
미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?
종이 문서의 서명을 디지털화했습니다. 공개키로 검증, 개인키로 서명. 위조 불가능, 부인 방지. 블록체인과 HTTPS의 기술.
일단 무조건 반으로 쪼개고 본다. 쪼개고 합치면서 정렬하는 '분할 정복'의 정석. 퀵 소트보다 느리지만 변수를 주지 않는 모범생.
이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?
가장 기본이 되는 O(N²) 정렬 알고리즘 3대장. 왜 버블 정렬은 실제로 안 쓸까? 삽입 정렬이 퀵 정렬보다 빠를 때는 언제일까?
트리(Tree)가 족보라면, 그래프(Graph)는 거미줄입니다. 내비게이션 길 찾기와 페이스북 친구 추천의 알고리즘.
이진 트리는 메모리용입니다. 디스크(SSD/HDD)는 느리니까 트리 키를 낮추고 옆으로 뚱뚱하게 만들어서 디스크 I/O 횟수를 최소화했습니다. B-Tree vs B+Tree 차이와 MySQL 인덱스의 비밀.
지하철 노선도, 페이스북 1촌, 내비게이션 최단 경로. 세상을 점(Node)과 선(Edge)로 표현하는 가장 강력한 자료구조.
줄 선 순서대로 치료하는 건 동네 병원(Queue)이고, 응급실은 위급한 사람부터 치료한다(Priority Queue). O(1)의 비밀.
회사의 조직도. 뿌리(Root)는 하나지만 가지(Branch)는 여러 갈래로 뻗어나간다. 파일 시스템의 원리.
맛집 줄 서기부터 롤(LoL) 매칭, 그리고 백엔드의 핵심인 메시지 큐(Kafka)까지. 선형 큐의 문제점, 원형 큐(Ring Buffer) 구현, 그리고 스레드 안전한 Blocking Queue까지 파헤칩니다.
가장 늦게 들어간 게 가장 먼저 나온다(LIFO). 뒤로 가기 버튼, 계산기의 원리(RPN), 깊이 우선 탐색(DFS), 그리고 컴파일러의 괄호 검사까지.
배열은 아파트지만, 연결 리스트는 보물 찾기입니다. 노드와 포인터 구조, O(1) 삽입의 조건, 메모리 파편화(Fragmentation), 그리고 LRU Cache와 원형 연결 리스트 응용까지.
기차 좌석처럼 연속된 메모리를 쓰는 배열. O(1) 조회 속도의 비밀인 주소 계산 공식부터, CPU 캐시 지역성(Cache Locality), 버퍼 오버플로우 보안 이슈, 그리고 동적 배열의 내부 구현까지.
O(1)과 O(N^2)의 차이는 실제로 서버 운명을 가릅니다. 상환 분석, P vs NP, 튜링 머신, 그리고 공간 복잡도까지 Big O의 모든 것을 파헤칩니다.
과학 실험(try) 중에 불이 나면 소화기를 쏘고(catch), 불이 나든 말든 실험실 청소(finally)는 해야 한다.
C언어의 악명 높은 진입 장벽. 메모리 주소를 직접 조작하는 포인터는 강력하지만 위험합니다. 참조는 그것의 안전한 버전. Segfault의 공포와 nullptr의 악몽.
개발자가 어지럽힌 쓰레기(메모리)를 치워주는 야간 청소부. 편하지만 가끔 청소한다고 복도를 막아서 서버를 멈추게 함(Stop The World).
재귀의 치명적 단점인 '스택 폭발'을 막는 기술. 바통 터치만 하고 퇴근하는 똑똑한 함수들 이야기.
마트료시카 인형 열기. 종료 조건(Base Case)이 없으면 영원히 끝나지 않는 무한 루프의 늪에 빠집니다.
