개념 하나의 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 다익스트라와 달리 음수 가중치 간선이 있어도 동작하며, 음수 사이클을 탐지할 수 있다. 핵심 특징 음수 가중치 허용: 다익스트라가 못 하는 것을 할 수 있음 음수 사이클 탐지: 무한히 짧아지는 경로가 있는지 판별 모든 간선을 V-1번 반복: 매 반복마다...

개념 펜윅 트리(Fenwick Tree), 또는 이진 인덱스 트리(Binary Indexed Tree, BIT)는 구간 합을 효율적으로 계산하는 자료구조이다. 세그먼트 트리와 비교 항목 펜윅 트리 세그먼트 트리 메모리 O(N) O(4N) ...

개념 하나의 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 음수 가중치가 없는 그래프에서 동작한다. 핵심 특징 단일 출발점 최단 경로: 하나의 시작점에서 모든 정점까지의 최단 거리 탐욕적 접근: 현재까지 가장 가까운 정점을 선택하여 확장 음수 간선 불가: 음수 가중치가 있으면 올바른 결과를 보장하지 않음 동...

개념 세그먼트 트리(Segment Tree)는 구간에 대한 질의와 업데이트를 효율적으로 처리하는 이진 트리 자료구조이다. 특징 특징 설명 구간 질의 구간 합, 최솟값, 최댓값 등을 O(log N)에 계산 점 업데이트 특정...

개념 방향 그래프(DAG: Directed Acyclic Graph)에서 정점들을 간선의 방향을 거스르지 않도록 나열하는 알고리즘이다. 핵심 특징 선행 조건 처리: A → B이면 A가 반드시 B보다 먼저 나옴 DAG에서만 가능: 사이클이 있으면 위상 정렬 불가능 결과가 유일하지 않음: 여러 유효한 순서가 존재할 수 있음 동작 원리...

개념 유니온 파인드(Union-Find)는 서로소 집합(Disjoint Set)을 표현하고 관리하는 자료구조이다. 핵심 연산 연산 설명 Find 원소가 속한 집합의 대표(루트) 찾기 Union 두 집합을 하나로 합치기 ...

NoSQL NoSQL이란? Not Only SQL - 관계형 모델(테이블)이 아닌 다양한 데이터 모델 사용 - 대규모 분산 환경에서의 확장성과 유연성에 초점 - 스키마가 유연하거나 없음 (Schema-less / Schema-flexible) RDBMS vs NoSQL 구분 RDBMS NoSQL...

개념 그래프에서 한 경로를 끝까지 탐색한 후 되돌아와 다른 경로를 탐색하는 알고리즘이다. 핵심 특징 깊이 우선 탐색: 더 이상 갈 곳이 없을 때까지 깊이 들어감 스택(Stack) 또는 재귀 사용: LIFO 특성 백트래킹의 기반: 모든 경로/조합 탐색에 활용 동작 원리 그래프: 1 --- 2 --- 5 | |...

개념 힙(Heap)은 완전 이진 트리 기반의 자료구조로, 부모-자식 간의 대소 관계를 유지한다. 힙의 종류 종류 조건 루트 최대 힙 (Max Heap) 부모 ≥ 자식 최댓값 최소 힙 (Min Heap) ...

회복(Recovery)의 개념 시스템 장애 발생 시 데이터베이스를 장애 이전의 일관된 상태로 복원하는 것. ACID의 원자성(Atomicity)과 지속성(Durability)을 보장한다. 장애 유형 1. 트랜잭션 장애 (Transaction Failure) - 논리적 오류: 잘못된 입력, 데이터 미존재 - 시스템 오류: Deadlock...