전체 글85 자료구조 - 해시 자료구조 해시 (충돌, 체이닝, 자료구조)배열·연결리스트·트리·힙은 모두 데이터의 순서나 구조를 메모리에 어떻게 배치할지에 답을 준 자료구조였다. 해시 테이블은 완전히 다른 질문에 답한다. "키만 알면 그 값을 거의 즉시 찾을 수 있는 자료구조가 있을까?"라는 질문이며, 그 답이 평균 O(1) 시간의 조회·삽입·삭제를 보장하는 해시 테이블(Hash Table)이다. 파이썬 dict, 자바 HashMap, JavaScript Object, Redis 같은 거의 모든 현대 키-값 저장소의 토대가 해시 테이블이며, 그 위에서 데이터베이스 인덱스·캐시·세션 저장소·중복 제거 같은 일상적인 기능들이 동작한다. 본 글은 해시 함수·충돌 해결·시간복잡도와 실전 응용까지 세심하게 정리한다(출처: 위키백과 — Hash Table.. 2026. 5. 16. 자료구조 - 그래프 탐색 그래프 (BFS, DFS, 인접리스트)트리는 그래프의 특수한 형태(사이클 없음 + 단일 부모)였다면, 그래프는 그 제약을 모두 풀어 노드들이 임의의 방식으로 연결될 수 있는 가장 일반적인 자료구조이다. 도로망·SNS 인맥·웹 페이지의 하이퍼링크·전력망·항공 노선·통신 토폴로지·게임 맵까지, 현실 세계의 거의 모든 네트워크가 그래프로 모델링된다. 그래프 위에서 동작하는 탐색 알고리즘 BFS·DFS는 이후 등장하는 거의 모든 그래프 알고리즘(최단 경로·최소 신장 트리·위상 정렬 등)의 토대가 되며, 그 위에서 다익스트라·크루스칼·프림 같은 고급 알고리즘이 얹어진다. 본 글은 그래프의 정의·표현 방법·탐색 알고리즘을 세심하게 정리한다(출처: 위키백과 — Graph (abstract data type)). 제가.. 2026. 5. 16. 자료구조 - 힙과 우선순위큐 힙 자료구조 (우선순위큐, 정렬, 다익스트라)이진 트리 위에 정렬 규칙을 얹으면 BST가 되고, 그와는 또 다른 규칙(부모가 자식보다 항상 크다 또는 작다)을 얹으면 힙(Heap)이 된다. 힙은 BST와는 완전히 다른 사용 시나리오를 가지는데, 임의 키 검색이 아니라 최댓값 또는 최솟값을 반복적으로 꺼내는 작업에 특화되어 있다. 이 단순한 규칙 하나로 힙은 우선순위 큐의 표준 구현체, 힙 정렬의 핵심 도구, 다익스트라 최단 경로의 가속기 역할을 동시에 수행한다. 본 글은 힙의 정의·연산·시간복잡도부터 우선순위 큐와 실전 응용까지 세심하게 정리한다(출처: 위키백과 — Heap (data structure)). 제가 학교 알고리즘 수업에서 다익스트라 알고리즘을 처음 배우며 가장 충격이었던 게 우선순위 큐 한.. 2026. 5. 16. NoSQL CAP MongoDB Redis NoSQL (CAP, MongoDB, 캐시)관계형 데이터베이스(RDB)는 50년 가까이 데이터 저장의 표준이었지만, 2000년대 후반부터 그 표준이 모든 영역에 맞지 않는다는 사실이 분명해졌다. 대량의 비정형 로그·실시간 캐시·소셜 네트워크의 그래프 관계 같은 영역에서 RDB의 스키마와 ACID가 오히려 발목을 잡는 경우가 늘었다. 본 글은 이 빈자리를 채우기 위해 등장한 NoSQL의 네 가지 유형, 분산 시스템 설계의 핵심 정리인 CAP 정리, 그리고 가장 자주 만나는 두 NoSQL인 MongoDB와 Redis의 실전 선택 기준을 정리한다(출처: 위키백과 — NoSQL). 제가 4학년 비정형 데이터 처리 수업에서 처음 MongoDB로 뉴스 기사 만 건을 그대로 JSON으로 던져 넣고 인덱스 한 줄만 추.. 2026. 5. 15. 파티셔닝 샤딩 스케일 파티셔닝 (수평, 수직, 샤딩)데이터베이스 한 대로 처리할 수 있는 행 수와 디스크 용량에는 분명한 상한이 있다. 한 테이블에 1억 행이 쌓이면 인덱스 트리 깊이가 깊어져 같은 쿼리가 10배 느려지고, 디스크가 가득 차면 새 행을 받지 못한다. 본 글은 이 상한을 푸는 두 단계 기법인 파티셔닝(Partitioning)과 샤딩(Sharding)을 다룬다. 수평 파티셔닝·수직 파티셔닝의 차이, 같은 DB 안에서의 파티셔닝과 여러 DB로 쪼개는 샤딩의 차이, 그리고 두 기법이 만드는 새로운 운영 부담까지 4학년 데이터베이스 시스템 수업 맥락에 비추어 정리한다(출처: 위키백과 — Partition (database)). 제가 학교 캡스톤에서 5만 행짜리 로그 테이블이 6개월 만에 1200만 행이 되면서 조회가 .. 2026. 5. 15. 락과 데드락 동시성 락과 데드락 (공유, 배타, 비관)같은 데이터를 여러 트랜잭션이 동시에 만지면 결과가 어긋날 수 있다는 문제는 격리 수준만으로 다 풀리지 않는다. 격리 수준이 "어떤 이상 현상을 허용할지"를 정하는 정책이라면, 락(Lock)은 그 정책을 실제로 강제하는 메커니즘이다. 본 글은 락의 두 기본 유형인 공유락·배타락의 호환 규칙, 데드락이 발생하는 4가지 조건과 데이터베이스가 그것을 감지·해결하는 방식, 그리고 비관적 락과 낙관적 락의 선택 기준을 4학년 데이터베이스 시스템 수업과 본인의 캡스톤 운영 경험에 비추어 정리한다(출처: 위키백과 — Lock (database)). 제가 학교 캡스톤에서 결제와 적립금 동시 처리 로직을 짜다가 동시에 두 사용자가 같은 적립금 행을 건드리는 순간 한쪽이 무한 대기에 빠진.. 2026. 5. 15. 이전 1 2 3 4 5 6 7 8 ··· 15 다음