cedis 님의 블로그

DFS는 그래프를 깊게 탐색하는 방식입니다. 재귀 함수와 함께 이해하면 훨씬 쉽게 익힐 수 있습니다.DFS란?DFS(Depth-First Search)는 현재 갈 수 있는 길이 있다면 한 방향으로 끝까지 내려간 뒤, 더 이상 갈 곳이 없을 때 되돌아오면서 탐색하는 방식입니다.깊이 우선 탐색재귀 또는 스택 사용예제 그래프0 ─── 1│ │└ 2 ── 3시작 정점0에서 시작합니다.DFS의 느낌을 그림처럼 이해하기예를 들어 인접 리스트 순서가 그대로 유지된다면 다음과 같이 진행될 수 있습니다.0 → 1 → 2 → 3물론 DFS는 인접 정점의 저장 순서에 따라 방문 결과가 달라질 수 있습니다. 그래서 문제에 따라 DFS 결과가 여러 개 나올 수도 있습니다.재귀 호출 흐름1단계dfs(0)을 호출하고 0..

BFS는 그래프 탐색의 가장 기본이 되는 방법 중 하나입니다. 시작점에서 가까운 정점부터 층별로 방문한다는 점이 핵심입니다.BFS란?BFS(Breadth-First Search)는 가까운 정점부터 차례대로 탐색하는 방식입니다. 그래서 흔히 "너비 우선 탐색"이라고 부릅니다.핵심 자료구조큐(Queue)예제 그래프0 ─── 1│ │└ 2 ── 3시작 정점0에서 시작한다고 가정합니다.BFS가 큐를 쓰는 이유큐는 먼저 들어온 데이터가 먼저 나가는 구조입니다. 따라서 시작점 근처에서 발견한 정점들을 순서대로 처리할 수 있어, 자연스럽게 가까운 정점부터 탐색하게 됩니다.탐색 과정을 단계별로 보기초기 상태visited = [0]queue = [0]0을 꺼냄0과 연결된 정점은 1, 2입니다.visited =..

그래프 기초그래프 기본 - 인접 리스트 표현 완전 정리그래프 문제를 풀기 위해서는 먼저 그래프를 코드로 표현할 수 있어야 합니다. 그중 가장 자주 쓰는 방식이 바로 인접 리스트입니다.그래프란?그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다. 트리와 달리 일반적인 연결 관계를 자유롭게 표현할 수 있습니다.정점: 연결의 대상이 되는 점간선: 정점과 정점을 이어주는 선인접 리스트란?인접 리스트는 각 정점마다 연결된 다른 정점들의 목록을 저장하는 방식입니다.예시 형태{정점: [연결된 정점들]}왜 많이 쓸까?간선 수가 많지 않은 그래프에서 메모리 효율이 좋고, BFS/DFS 구현과도 잘 어울립니다.예제 그래프0 ─── 1│ │└ 2 ── 3간선이 [(0,1), (0,2), (1..

BST는 이진 트리에 정렬 규칙이 추가된 구조입니다. 이 규칙 덕분에 원하는 값을 훨씬 빠르게 찾을 수 있습니다.BST란?BST(Binary Search Tree)는 각 노드에 대해 다음 규칙을 만족하는 트리입니다.왼쪽 서브트리의 모든 값현재 노드 값보다 작다.현재 노드 값비교의 기준이 되는 값오른쪽 서브트리의 모든 값현재 노드 값보다 크다.예제 BST 구조5／ ＼3／ ＼247이 구조를 BST라고 부를 수 있는 이유5의 왼쪽에는 3, 2, 4처럼 5보다 작은 값들만 있습니다.5의 오른쪽에는 7처럼 5보다 큰 값만 있습니다.노드 3을 기준으로 봐도 왼쪽은 2, 오른쪽은 4로 같은 규칙을 만족합니다.검색 아이디어BST 검색은 현재 노드 값과 target을 비교하면서 진행합니다.비교 결과동작target == ..

이진 트리는 트리 자료구조의 가장 기본이 되는 형태입니다. 특히 순회(traversal)는 코딩 테스트와 자료구조 학습에서 반드시 이해해야 하는 핵심입니다.이진 트리란?이진 트리(Binary Tree)는 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리 구조입니다. 보통 왼쪽 자식(left), 오른쪽 자식(right)으로 구분합니다.핵심 특징각 노드는 최대 2개의 자식만 가진다.계층 구조를 표현하기 좋다.재귀와 함께 자주 등장한다.예제 트리 구조1／ ＼2／ ＼453구조 해석루트 노드는 1입니다.1의 왼쪽 자식은 2, 오른쪽 자식은 3입니다.2의 왼쪽 자식은 4, 오른쪽 자식은 5입니다.3, 4, 5는 자식이 없는 리프 노드입니다.순회(traversal)란?트리 순회란 트리의 모든 노드를 일정한 규칙..

"세 번째 WIL을 쓴다. 4주가 지났고, 블로그엔 67개의 글이 쌓였다.숫자보다 중요한 건 그 안에서 내가 무엇을 배웠는가이다."Week 3: Data Structures & Algorithms Deep Dive📌 이번 주 목표 3가지✅ 목표 1: 자료구조를 코드로 이해한다 — 배열이 아니라 직접 구현으로.✅ 목표 2: Redis를 쓰는 사람이 아니라, Redis를 만드는 사람이 된다.✅ 목표 3: 팀 프로젝트에서 내 코드가 팀의 코어 엔진이 될 수 있도록 설계한다.세 가지 모두 달성했다. 단, "만든다"의 의미가 각기 달랐다. 목표 1은 자료구조의 내부 동작 원리를 깨닫는 과정이었고, 목표 2는 라이브러리 없이 밑바닥부터 쌓아 올리는 고통이었으며, 목표 3은 단순 구현을 넘어 아키텍처를 고민하는 시..

크래프톤 정글 × 수요코딩회Redis를 직접 만들어보며배운 것들"Redis를 구현하라" — 단순한 과제를 티케팅 서비스로 확장한4인 팀 프로젝트 회고👥 4인 팀 🐍 Python Only 📦 PyMiniRedis 🎫 Ticketing ServicePrologueRedis를 쓰면서 한 번쯤은 생각해봤을 것이다."이거 대체 어떻게 동작하는 거야?"크래프톤 정글에서 수요코딩회 과제로 Redis를 직접 구현하는 팀 프로젝트가 주어졌다. 과제 자체는 간단했다. Redis라는 키워드를 받았고, 그걸 구현해보라는 것. 외부 라이브러리를 가져다 쓰는 게 아니라, Redis가 하는 일을 우리 손으로 직접 만들어보라는 의미였다.이 글은 그 과정에서 내가 직접 설계하고 구현한 것들, 팀과 병합하면서 배운 것들, 그리고..

빠른 Redis, 안전하게 운영하려면? ACL로 최소 권한을 설정하고, eviction으로 메모리를 관리하며, slowlog로 병목을 찾는 운영 필수 지식을 정리합니다.⚡ "빠른 만큼 운영이 중요합니다"Redis는 빠릅니다. 초당 수십만 건의 요청을 처리할 수 있죠. 하지만 빠른 만큼 잘못 사용하면 순식간에 메모리가 가득 차거나, 보안 허점이 생기거나, 갑자기 응답이 느려질 수 있습니다.시리즈 마지막 편인 이번 12편에서는 Redis를 안전하고 효율적으로 운영하기 위한 세 가지 핵심 영역을 다룹니다. 첫째는 보안(ACL) — 최소 권한 원칙으로 위험을 줄이는 방법. 둘째는 성능(eviction + pipelining) — 메모리를 관리하고 RTT를 최소화하는 방법. 셋째는 관측(slowlog + late..

Redis 서버 한 대의 메모리가 부족해졌을 때, 여러 노드에 데이터를 나눠 저장하는 클러스터를 이해합니다.💾 "메모리가 부족해지면 어떻게 하나요?"서비스가 성장하면서 Redis에 저장해야 할 데이터가 늘어납니다. 처음에는 서버 메모리를 늘리면(Scale-Up) 됩니다. 하지만 한 대 서버의 메모리에는 한계가 있습니다. 그때는 서버를 여러 대로 늘리는(Scale-Out) 방법이 필요합니다.Redis Cluster는 데이터를 여러 노드에 나눠서 저장하는 공식 분산 솔루션입니다. 각 노드는 전체 데이터의 일부만 담당하고, 클라이언트는 어떤 노드에 요청해도 올바른 노드로 자동 리다이렉트됩니다.Cluster는 Sentinel과 다릅니다. Sentinel은 "한 대가 죽으면 다른 한 대가 대신"하는 고가용성(H..

"Redis 서버 한 대가 다운되면 서비스가 멈추나요?" — 복제와 Sentinel로 장애에 강한 고가용성 구성을 만들어 봅니다.🔥 "서버 한 대 죽으면 서비스가 멈추나요?"새벽 2시, 갑자기 Redis 서버가 죽었습니다. 캐시도, 세션도, 실시간 기능도 모두 멈춥니다. 사용자들은 오류 화면을 보고, 고객 센터 전화가 빗발칩니다. 이런 상황을 막으려면 어떻게 해야 할까요?답은 이중화(Redundancy)입니다. 메인 서버(Primary)와 똑같은 데이터를 가진 복사본(Replica)을 항상 준비해 두는 것이죠. Primary가 죽으면 Replica가 즉시 역할을 이어받습니다. 이것이 고가용성(High Availability, HA)의 기본 원리입니다.Redis는 복제(Replication)로 Prima..