개념 희소 테이블(Sparse Table)은 정적 배열에서 구간 질의를 O(1)에 처리하기 위한 자료구조이다. 특히 멱등 연산(min, max, gcd 등)에 적합하다. 멱등 연산 (Idempotent) f(a, a) = a 인 연산 - min(a, a) = a - max(a, a) = a - gcd(a, a) = a - OR(a, a) = a ...

개념 큰 문제를 작은 부분 문제로 나누어 풀고, 결과를 저장하여 재사용하는 알고리즘 설계 기법이다. 핵심 특징 최적 부분 구조: 큰 문제의 최적해가 부분 문제의 최적해로 구성됨 중복 부분 문제: 같은 부분 문제가 여러 번 반복 등장 메모이제이션/타뷸레이션: 한 번 계산한 결과를 저장하여 재계산 방지 DP vs 분할 정복 vs 그리...

개념 메모리 풀(Memory Pool)은 미리 할당한 메모리 블록을 관리하여 동적 할당의 오버헤드를 줄이는 기법이다. 동적 할당 vs 메모리 풀 항목 동적 할당 (new/malloc) 메모리 풀 할당 속도 느림 (OS 호출) 빠름 (배열 ...

문제 f(a) = a의 약수의 합 g(x) = f(1) + f(2) + … + f(x) 자연수 N이 주어질때 g(N) 구하기 접근법 처음에는 입력 받고 각 케이스마다 f(), g() 함수 돌려서 답을 구하게 할려고 했었다. 그런데 f 함수에서 소인수 분해를 해야 하나…? 이런 생각을 하게 되면서 시간초과가 발생할것을 알았다. 그 뒤로 내 머리로 생...

개념 네트워크 플로우는 소스(S)에서 싱크(T)로 흘려보낼 수 있는 최대 유량을 구하는 문제이다. 핵심 특징 용량 제한: 각 간선에 흘릴 수 있는 최대 유량이 정해져 있음 유량 보존: 중간 정점에서 들어오는 유량 = 나가는 유량 최대 유량 = 최소 컷: max-flow min-cut 정리 동작 원리 그래프 (용량): S --...

개념 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 표현 방식에 따라 시간/공간 복잡도가 달라진다. 그래프 종류 종류 설명 무방향 그래프 간선에 방향이 없음 방향 그래프 간선에 방향이 있음 ...

개념 단절점(Articulation Point): 이 정점을 제거하면 그래프가 2개 이상의 연결 요소로 분리되는 정점. 단절선(Bridge): 이 간선을 제거하면 그래프가 2개 이상의 연결 요소로 분리되는 간선. 핵심 특징 무향 그래프에서 정의 (방향 그래프는 별도 처리) DFS 트리 기반: DFS 방문 순서와 역방향 간선(back ed...

개념 트라이(Trie)는 문자열을 효율적으로 저장하고 검색하는 트리 자료구조이다. 접두사 트리(Prefix Tree)라고도 한다. 구조 (root) / | \ a b c /| | p n a / | | p t r / l (ap...

개념 방향 그래프에서 강한 연결 요소(Strongly Connected Component)란 임의의 두 정점 u, v 사이에 u→v, v→u 경로가 모두 존재하는 최대 부분 그래프이다. 핵심 특징 방향 그래프 전용: 무향 그래프에서는 연결 요소(CC)와 동일 SCC 내부: 어떤 정점에서 다른 어떤 정점으로든 도달 가능 SCC 축약 (...

개념 개방 주소법(Open Addressing)은 충돌 시 다른 빈 슬롯을 찾아 저장하는 방식이다. 모든 데이터가 해시 테이블 배열 내에 저장된다. Chaining vs Open Addressing 항목 Chaining Open Addressing 충돌 해결 ...