개념 해를 찾는 과정에서 유망하지 않은 경로를 조기에 포기(가지치기)하고 다른 경로를 탐색하는 기법이다. 핵심 특징 DFS 기반 완전 탐색: 가능한 모든 경우를 탐색 가지치기(Pruning): 유망하지 않으면 더 진행하지 않고 되돌아감 상태 공간 트리: 가능한 선택들을 트리로 표현 완전 탐색 vs 백트래킹 ...

개념 레드-블랙 트리(Red-Black Tree)는 자가 균형 이진 탐색 트리로, 각 노드가 빨간색 또는 검은색을 가지며 5가지 속성을 만족한다. 5가지 속성 모든 노드는 빨간색 또는 검은색 루트는 검은색 모든 리프(NIL)는 검은색 빨간 노드의 자식은 모두 검은색 (연속 빨강 X) 각 노드에서 리프까지 검은 노드 수 동일 (...

개념 문제를 더 작은 부분 문제로 나누어 해결한 후, 결과를 합쳐서 원래 문제의 답을 구하는 알고리즘 설계 기법이다. 핵심 특징 Divide: 문제를 같은 유형의 작은 문제로 분할 Conquer: 부분 문제를 재귀적으로 해결 Combine: 부분 문제의 해를 합쳐서 원래 문제의 해 도출 부분 문제가 겹치지 않음: DP와의 핵심 차...

개념 AVL 트리는 자가 균형 이진 탐색 트리(Self-Balancing BST)로, 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1이다. 균형 인수 (Balance Factor) BF(node) = height(left) - height(right) 유효 범위: -1, 0, 1 BST와 비교 항목 ...

개념 매 단계에서 가장 좋아 보이는 선택을 하여 전체적으로 최적해를 구하는 알고리즘 설계 기법이다. 핵심 특징 탐욕적 선택 속성: 현재 최적 선택이 전체 최적해에 포함됨 최적 부분 구조: 부분 문제의 최적해로 전체 최적해 구성 가능 증명이 중요: 그리디가 최적해를 보장하는지 확인해야 함 DP vs 그리디 ...

개념 희소 테이블(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 --...