무작위 알고리즘: 동전을 던져 더 빨라지다
무작위성을 계산 도구로 사용하는 무작위 알고리즘을 정리합니다. 라스베이거스와 몬테카를로의 차이, 무작위 퀵정렬의 기대 시간 분석, 오류 증폭과 다수결, 밀러–라빈 소수 판정과 무작위 알고리즘이 강력한 이유까지 직관과 함께 다룹니다.
일치하는 글이 없습니다.
142개의 글이 있습니다.
무작위성을 계산 도구로 사용하는 무작위 알고리즘을 정리합니다. 라스베이거스와 몬테카를로의 차이, 무작위 퀵정렬의 기대 시간 분석, 오류 증폭과 다수결, 밀러–라빈 소수 판정과 무작위 알고리즘이 강력한 이유까지 직관과 함께 다룹니다.
NP-난해 최적화 문제를 다항 시간에 다루는 근사 알고리즘을 정리합니다. 근사 비율의 정의와 최소화·최대화에서의 의미, 정점 덮개 2-근사와 그리디 집합 덮개의 분석, PTAS와 FPTAS의 계층, 근사 불가능성까지 직관과 함께 다룹니다.
한 문제의 어려움을 다른 문제로 옮기는 환원을 정리합니다. 다항 시간 다대일 환원의 정의와 방향성, 환원이 어려움과 쉬움을 동시에 전달하는 논리, 독립 집합과 정점 덮개의 여집합 환원 예시, NP-완전성 증명에서 환원이 하는 핵심 역할까지 직관과 함께 다룹니다.
P와 NP를 넘어 복잡도 클래스들의 전체 지도를 그립니다. 시간과 공간이라는 두 자원, 결정적·비결정적 계산의 차이, P ⊆ NP ⊆ PSPACE ⊆ EXPTIME의 포함 관계, co-NP와 사비치 정리, 그리고 어떤 분리가 증명되었고 무엇이 미해결인지 직관 중심으로 정리합니다.
어떤 문제가 본질적으로 어려운지 답하는 NP-완전성을 정리합니다. P와 NP의 정의, 답을 검증하는 것과 찾는 것의 차이, NP-완전과 NP-난해의 구분, 쿡-레빈 정리와 SAT, 그리고 어떤 문제가 NP-완전임을 보이는 환원의 역할까지 직관 중심으로 다룹니다.
다각형의 넓이를 구하는 신발끈 공식을 외적의 합으로 유도하고, 부호로 정점의 진행 방향까지 알아내는 법을 정리합니다. 격자 다각형에서 내부·경계 격자점으로 넓이를 세는 픽의 정리, 경계점 개수를 gcd로 구하는 기법과 점의 내부 판정까지 함께 다룹니다.
평면을 한 방향으로 쓸어가며 사건 순서대로 처리하는 스위프 라인 패러다임을 정리합니다. 사건 큐와 활성 집합이라는 두 자료구조, 선분 교차 검출을 O((n+k) log n)으로 줄이는 원리, 직사각형 넓이 합집합·가장 가까운 점 쌍 같은 응용까지 살펴봅니다.
두 선분이 교차하는지 정확히 판정하는 방법을 정리합니다. 네 번의 외적 부호로 일반 교차를 판정하는 원리, 일직선·끝점 접촉 같은 경계 사례 처리, 바운딩 박스 빠른 기각, 정수 좌표로 오차 없이 다루는 법과 교점 좌표 계산까지 구현과 함께 다룹니다.
평면 위 점들을 감싸는 가장 작은 볼록 다각형, 볼록 껍질을 구하는 알고리즘을 정리합니다. 외적을 이용한 우회전 판정, 앤드류 모노톤 체인과 그레이엄 스캔의 동작, O(n log n) 복잡도, 일직선 점 처리와 실전 주의점까지 구현과 함께 다룹니다.
계산기하학의 핵심 연산인 2D 외적을 정리합니다. 세 점의 회전 방향(CCW)을 부호로 판정하는 원리, 외적의 크기가 평행사변형 넓이와 행렬식이 되는 이유, 정수 좌표로 오차 없이 판별하는 법, 그리고 점이 선의 어느 쪽인지·각도 정렬 응용까지 다룹니다.
계산기하학의 기초인 점과 벡터를 코드로 다루는 법을 정리합니다. 벡터의 덧셈·뺄셈·스칼라곱, 크기와 정규화, 내적의 기하학적 의미와 부호 판정, 정수 좌표를 쓰는 이유와 부동소수점 오차 관리까지 실전 관점으로 살펴봅니다.
피보나치 수를 빠르게 계산하는 기법을 총정리합니다. O(log n) 빠른 배가(fast doubling) 공식의 유도와 구현, 모듈러 환경에서 거대한 인덱스를 다루는 피사노 주기, 그리고 GCD·캐시 성질까지 실전 관점에서 분석합니다.
선형 점화식을 전이 행렬로 표현하고 행렬 빠른 거듭제곱으로 n번째 항을 O(k³ log n)에 구하는 기법을 분석합니다. 피보나치 행렬 항등식, 일반 점화식의 행렬화, 그래프 경로 개수 세기 응용까지 구현합니다.
순열·조합의 기본과 파스칼 항등식, DP 테이블·곱셈 공식·팩토리얼 역원 전처리로 nCr mod p를 구하는 세 가지 방법을 비교합니다. 뤼카 정리, 중복조합, 카탈란 수까지 실전 조합론 도구를 정리합니다.
O(√n) 시도 분할, SPF 테이블로 O(log n) 다중 쿼리 분해, 밀러-라빈 소수 판정과 폴라드 로 알고리즘으로 64비트 수를 분해하는 방법까지 단계별로 구현합니다. 약수 개수·합 공식 응용도 함께 정리합니다.
에라토스테네스의 체로 1~n의 모든 소수를 O(n log log n)에 구하는 원리와 p²부터 지우기·√n 한계 최적화를 분석합니다. 비트 체·구간 체(Segmented Sieve)·선형 체와 최소 소인수 테이블까지 실전 변형을 정리합니다.
모듈러 역원의 존재 조건(gcd(a,m)=1)과 의미를 정리하고, 페르마 소정리·확장 유클리드·선형 점화식 세 가지 계산 방법을 구현합니다. 팩토리얼 역원 테이블과 nCr 계산, 합동식 나눗셈까지 다룹니다.
aⁿ mod m을 O(log n)에 계산하는 반복 제곱법(Binary Exponentiation)의 원리를 분석합니다. 재귀·반복 구현, 지수의 이진 분해, 페르마 소정리를 이용한 빠른 판정, RSA·디피-헬만 등 암호학 응용까지 정리합니다.
합동의 개념과 시계 산술 비유, 덧셈·뺄셈·곱셈의 모듈러 분배 법칙과 증명, 언어별 음수 나머지 함정, 오버플로 없이 큰 수를 다루는 누적 mod 패턴, 1e9+7이 표준 모듈러인 이유까지 정리합니다.
유클리드 호제법으로 GCD를 O(log n)에 구하는 원리와 증명, LCM과의 관계, 베주 항등식과 확장 유클리드 알고리즘 구현, 선형 디오판토스 방정식의 해 구하기까지 정수론 알고리즘의 출발점을 완전히 정리합니다.
트라이의 대표 응용 패턴을 정리합니다. 자동완성과 접두사 카운팅, 사전순 k번째 단어, 비트 트라이로 최대 XOR 쌍 찾기, 단어 사각형 같은 백트래킹 결합 패턴까지 구현 코드와 함께 분석합니다.
접미사 배열의 개념과 O(n log² n) 구축 알고리즘, Kasai 알고리즘으로 LCP 배열을 O(n)에 구하는 방법, 부분 문자열 검색·최장 반복 부분 문자열·서로 다른 부분 문자열 개수 응용까지 완전히 분석합니다.
아호-코라식(Aho-Corasick) 알고리즘의 트라이 구성, 실패 링크(Failure Link)·사전 링크(Dictionary Link) BFS 구축, O(n + 총 매칭)으로 k개 패턴 동시 탐색, 바이러스 스캐너·형태소 분석기 응용까지 완전히 분석합니다.
보이어-무어(Boyer-Moore) 알고리즘의 Bad Character 휴리스틱, Good Suffix 휴리스틱, 오른쪽-왼쪽 비교 전략, 전처리 테이블 구축, 평균 O(n/m) 성능 분석까지 완전히 다룹니다.
마나커(Manacher) 알고리즘의 핵심 아이디어인 문자열 변환(#삽입), P 배열, 오른쪽 경계 C·R을 이용한 O(n) 구현, 최장 팰린드롬 부분 문자열 탐색, 모든 팰린드롬 열거 응용까지 완전히 정리합니다.
Z-알고리즘의 Z 배열 정의, Z-box를 활용한 O(n) 구축, 패턴 검색에의 응용(pat#text), 문자열 주기성·팰린드롬 판별, KMP와의 관계까지 완전히 정리합니다.
롤링 해시(Rolling Hash)의 다항식 해시 원리, O(1) 갱신 공식, 접두사 해시 배열로 임의 부분 문자열 O(1) 쿼리, 이중 해싱으로 충돌 최소화, 최장 중복 부분 문자열·팰린드롬 판별 응용까지 완전히 다룹니다.
라빈-카프(Rabin-Karp) 알고리즘의 롤링 해시 원리, O(1) 해시 갱신, 허위 양성 처리, 다중 패턴 동시 검색, 이중 해싱으로 충돌 최소화까지 완전히 정리합니다.
KMP(Knuth-Morris-Pratt) 알고리즘의 실패 함수(Failure Function) 구축 원리, O(n+m) 탐색 과정, 구현 세부 사항, 다중 패턴 검색과 주기성 탐지 응용까지 완전 분석합니다.
AND·OR·XOR·NOT·SHIFT 기본 연산부터 최하위 비트 추출·2의 거듭제곱 검사·XOR 스왑 트릭, 비트마스크 DP(TSP·집합 커버링), popcount 최적화까지 비트 조작의 모든 것을 정리합니다.
백트래킹의 핵심 개념인 상태 공간 트리, 가지치기(Pruning), 그리고 N-Queens·순열·부분 집합 합 문제를 Python으로 완전 구현합니다. 재귀 템플릿과 최적화 기법까지 정리합니다.
두 문자열을 최소 횟수의 삽입·삭제·교체로 변환하는 편집 거리(Levenshtein Distance)의 DP 점화식, O(m·n) 공간 최적화, 역추적으로 실제 연산 복원, 맞춤법 교정·DNA 서열 비교 응용까지 심층 정리합니다.
LCS(Longest Common Subsequence)의 2D DP 점화식, 역추적으로 실제 수열 복원, 공간 최적화, 편집 거리·SCS·diff와의 관계까지 종합 정리합니다.
LIS(Longest Increasing Subsequence)를 O(n²) DP와 O(n log n) 이분 탐색 두 가지 방법으로 구현하고, 실제 수열 복원과 응용 문제까지 설명합니다.
트리 구조에서 DFS로 서브트리 상태를 합산하는 Tree DP 패턴을 독립 집합 최대 가중치, 트리 지름, 리루팅 기법까지 코드 예제와 함께 설명합니다.
비트마스크로 집합 상태를 표현하는 DP 기법을 TSP(외판원 문제), 작업 배분 최적화 등의 예제와 함께 비트 연산 패턴부터 구현까지 설명합니다.
구간 [i..j]를 분할 위치 k로 나누는 Interval DP 패턴을 대각선 채우기 방식과 함께 풍선 터뜨리기, 팰린드롬 분할, 돌 합치기 예제로 설명합니다.
행렬 연쇄 곱셈의 최적 괄호 순서를 구간 DP로 O(n³)에 찾는 알고리즘을 점화식 도출부터 코드 구현, 분할 위치 역추적까지 설명합니다.
동전 교환 문제의 두 변형 — 최소 동전 수(Coin Change I)와 경우의 수(Coin Change II) — 를 DP 점화식과 순회 방향 차이로 완전 정복합니다.
0/1 배낭을 기반으로 무한 배낭(Unbounded), 유계 배낭(Bounded), 분할 가능 배낭(Fractional) 변형들의 점화식 차이와 구현 패턴을 비교합니다.
0/1 배낭 문제의 DP 점화식 도출부터 2D 테이블 채우기, 역추적으로 선택 물품 복원, 1D 배열 최적화까지 완전 정복합니다.
동적 프로그래밍의 두 구현 전략인 메모이제이션(Top-Down)과 타뷸레이션(Bottom-Up)을 원리부터 공간 최적화까지 실전 코드와 함께 비교합니다.
동적 프로그래밍의 두 조건(최적 부분 구조·겹치는 부분 문제), 메모이제이션과 타뷸레이션, 피보나치로 시작하는 DP 사고법을 설명합니다.
빈도 기반 가변 길이 이진 코드를 생성하는 허프만 코딩의 트리 구성 알고리즘, 최적성 증명, 압축 효율을 설명합니다.
시작·종료 시간이 주어진 활동 집합에서 최대 개수의 호환 활동을 선택하는 고전적 탐욕 문제를 설명합니다.
마감 시간 기준 정렬로 최대 비겹침 구간을 선택하는 구간 스케줄링 최대화 문제와 탐욕 증명을 설명합니다.
탐욕 알고리즘의 원리, 탐욕 선택 속성, 최적 부분 구조, DP와의 비교, 동전 교환·거스름돈 등 예제를 설명합니다.
2D 평면에서 가장 가까운 두 점을 O(N log N)에 찾는 분할 정복 알고리즘의 원리, strip 탐색, 구현을 설명합니다.
분할 정복의 세 단계(분할·정복·결합), 시간 복잡도 분석, 병합 정렬·퀵 정렬·이진 탐색 적용 패턴을 설명합니다.
재귀의 개념, 기저 조건, 재귀 트리 분석, 꼬리 재귀 최적화, 반복 전환 패턴을 설명합니다.
오프라인 쿼리 처리의 개념, 온라인 vs 오프라인 비교, 주요 기법(Mo's, 정렬, 분할 정복, 오프라인 LCA)을 정리합니다.
Mo's Algorithm으로 정적 구간 쿼리를 O((N+Q)√N)에 처리하는 방법, 블록 분해 기반 쿼리 정렬, 구현 패턴을 설명합니다.
배열을 √N 크기 블록으로 나눠 구간 쿼리를 O(√N)에, 업데이트를 O(1)에 처리하는 제곱근 분해의 원리, 구현, Mo's Algorithm 연결을 설명합니다.
최대 부분 배열 합을 O(N), O(1) 공간에 구하는 카데인 알고리즘의 DP 원리, 구간 추적 구현, 최소·원형·최대 곱 변형을 설명합니다.
구간 일괄 업데이트를 O(1)에 처리하고 누적 합으로 O(N) 복원하는 차이 배열의 원리, 구현, 2차원 확장, 대표 응용을 설명합니다.
O(N) 전처리로 구간 합 쿼리를 O(1)에 처리하는 누적 합의 1차원·2차원 구현, 응용 패턴, 세그먼트 트리와의 비교를 설명합니다.
연속 부분 배열/문자열 최적화 문제를 O(N)에 해결하는 슬라이딩 윈도우의 고정·가변 크기 패턴, 대표 구현, 투 포인터와의 차이를 설명합니다.
두 인덱스를 독립적으로 이동해 O(N²)를 O(N)으로 줄이는 투 포인터 기법의 세 가지 패턴, 적용 조건, 대표 구현을 설명합니다.
크기 K 최소 힙을 이용한 O(N log K) Top-K 탐색, 빈도 기반 Top-K, 버킷 정렬 O(N) 풀이, Quickselect 비교를 설명합니다.
정렬 없이 k번째 작은 원소를 평균 O(N)에 구하는 퀵셀렉트의 파티션 원리, Lomuto 구현, Median of Medians 결정론적 알고리즘을 설명합니다.
O(2ᴺ) 완전 탐색을 O(2^(N/2) · log N)으로 줄이는 Meet in the Middle 기법의 원리, 부분합 문제 구현, 적용 조건을 설명합니다.
단봉 함수의 최댓값·최솟값을 O(log N)에 구하는 삼분 탐색의 원리, 정수·실수 구현 패턴, 이진 탐색과의 차이를 설명합니다.
최솟값의 최댓값·최댓값의 최솟값 형태 최적화 문제를 O(N log X)에 해결하는 파라메트릭 서치의 단조 함수 조건, 템플릿, 대표 문제 패턴을 설명합니다.
정렬된 배열에서 O(log N)에 값을 찾는 이진 탐색의 경계 조건, lower_bound·upper_bound 패턴, 오버플로우 방지, 실전 라이브러리 활용을 설명합니다.
배열을 처음부터 끝까지 순차 비교하는 선형 탐색의 기본 구현, Sentinel 최적화, Self-organizing 탐색, 실전 활용 패턴과 이진 탐색 전환 기준을 설명합니다.
동일 키의 상대 순서를 보존하는 안정 정렬의 정의와 중요성, 알고리즘별 안정성 비교표, 불안정 정렬을 안정으로 만드는 기법을 설명합니다.
메모리보다 큰 데이터를 정렬하는 외부 정렬의 청크 생성·K-way 병합 구조, 디스크 I/O 최소화 전략, Replacement Selection과 Double Buffering 최적화를 설명합니다.
Python과 Java의 기본 정렬 알고리즘인 팀 정렬의 Run 탐지·minRun 계산·갤로핑 병합·병합 불변식 등 핵심 기법과 실전 성능 특성을 설명합니다.
균등 분포 입력에서 평균 O(N)을 달성하는 버킷 정렬의 분배·정렬·합병 3단계, 버킷 수 선택 전략, 실수 정렬 활용 패턴을 설명합니다.
자릿수별 안정 정렬을 반복해 O(d(N+K))에 정수를 정렬하는 기수 정렬의 LSD·MSD 방식, 카운팅 정렬과의 연계, 실전 활용 패턴을 설명합니다.
비교 없이 O(N+K)에 정렬하는 카운팅 정렬의 세 단계(빈도 집계·누적합·역방향 배치), 안정 정렬 보장 원리, 기수 정렬과의 연계를 설명합니다.
Max-Heap을 이용해 항상 O(N log N)을 보장하는 힙 정렬의 Build-Heap 과정, heapify, 제자리 정렬 구현, 그리고 퀵/병합 정렬과의 실전 비교를 설명합니다.
피벗 선택과 파티션으로 평균 O(N log N)을 달성하는 퀵 정렬의 Lomuto·Hoare 파티션, 3-way 파티션, 랜덤 피벗, 최악 O(N²) 회피 전략과 실전 최적화를 설명합니다.
분할 정복으로 O(N log N)을 보장하는 병합 정렬의 원리, top-down·bottom-up 구현, 안정 정렬 특성, O(N) 추가 메모리, 역위 수 세기 응용을 설명합니다.
삽입 정렬을 간격(gap)으로 확장한 셸 정렬의 원리, Knuth·Hibbard·Ciura 간격 수열, O(N^1.5)~O(N log²N) 복잡도 분석, 불안정 정렬인 이유를 설명합니다.
정렬된 구간에 새 원소를 올바른 위치에 삽입하는 삽입 정렬의 원리, 안정 정렬 특성, 거의 정렬된 데이터에서 O(N) 성능, 이진 탐색 최적화, Tim Sort와의 관계를 설명합니다.
미정렬 구간에서 최솟값을 찾아 앞으로 이동하는 선택 정렬의 원리, O(N²) 비교·O(N) 교환 특성, 불안정 정렬인 이유, 버블 정렬과의 비교를 설명합니다.
인접 원소를 비교·교환해 큰 값을 오른쪽으로 밀어내는 버블 정렬의 동작 원리, 조기 종료 최적화, O(N²) 복잡도 분석, 안정 정렬 특성과 실전 활용 범위를 설명합니다.
트리에서 두 노드의 최소 공통 조상(LCA)을 O(N log N) 전처리, O(log N) 쿼리로 구하는 이진 리프팅 원리, up 테이블 구성, 쿼리 처리, 트리 거리 계산까지 설명합니다.
이분 그래프에서 최대 매칭을 구하는 헝가리안 DFS 알고리즘과 Hopcroft-Karp, König 정리(최소 버텍스 커버 = 최대 매칭), 그리고 유량으로의 환원을 설명합니다.
네트워크를 S·T 두 집합으로 나누는 최소 컷의 개념, Max-Flow Min-Cut 정리 증명, Dinic 완료 후 컷 복원 방법, 프로젝트 선택·이미지 분할 등 주요 응용을 설명합니다.
BFS 레벨 그래프와 DFS 블로킹 플로우를 조합한 Dinic 알고리즘의 O(V²E) 복잡도, 구현 패턴, 이분 매칭에서의 O(E√V) 특수 성능을 상세히 설명합니다.
증가 경로를 반복 탐색해 source에서 sink로의 최대 유량을 구하는 포드-풀커슨과 Edmonds-Karp의 잔여 그래프, 역방향 간선, 최대-유량 최소-컷 정리를 완전히 설명합니다.
모든 간선을 정확히 한 번 통과하는 오일러 경로·회로의 존재 조건과 히어홀저 알고리즘으로 O(E)에 경로를 구성하는 방법, 방향·무방향 그래프 모두 다룹니다.
제거하면 그래프가 분리되는 단절점(AP)과 단절선(Bridge)을 DFS의 disc/low 값으로 O(V+E)에 탐지하는 알고리즘을 완전히 이해합니다.
방향 그래프에서 서로 도달 가능한 노드 집합인 SCC를 DFS 2회의 코사라주와 DFS 1회의 타잔 알고리즘으로 O(V+E)에 구하는 방법을 완전 정리합니다.
시작 노드에서 최소 가중치 간선으로 트리를 확장하는 프림 알고리즘의 우선순위 큐 구현, 크루스칼과의 비교, 실전 활용까지 완전히 정리합니다.
간선을 가중치 오름차순으로 정렬해 사이클 없이 선택하는 크루스칼 알고리즘과 유니온 파인드의 조합으로 O(E log E)에 MST를 구성합니다.
3중 루프로 모든 쌍의 최단 경로를 O(V³)에 구하는 플로이드-워셜 알고리즘의 DP 원리, 음수 사이클 탐지, 경로 추적까지 완전히 파헤칩니다.
모든 간선을 V-1번 반복해 음수 가중치 그래프에서도 최단 경로를 구하고, V번째 완화로 음수 사이클을 탐지하는 벨만-포드 알고리즘을 완전히 이해합니다.
f(n) = g(n) + h(n) 공식으로 목표 방향을 예측하며 탐색하는 A* 알고리즘의 원리, 허용 가능 휴리스틱 조건, 격자 기반 구현을 알아봅니다.
우선순위 큐를 활용해 음수 없는 가중치 그래프에서 O((V+E)log V)에 최단 경로를 구하는 다익스트라 알고리즘을 구조부터 구현까지 완전 정복합니다.
경로 압축과 랭크 합치기로 O(α(n))에 집합 연산을 처리하는 유니온 파인드의 구조, 구현, 크루스칼 MST 응용까지 알아봅니다.
DAG에서 선후 관계를 만족하는 노드 순서를 구하는 위상 정렬의 원리, Kahn(BFS) 알고리즘, DFS 기반 구현, 사이클 감지까지 알아봅니다.
간선 가중치가 0 또는 1로 제한된 그래프에서 deque를 활용해 O(V+E)로 최단 경로를 구하는 0-1 BFS의 원리와 구현, 적용 패턴을 알아봅니다.
여러 시작점에서 동시에 BFS를 실행하는 기법으로, 모든 소스에 대한 최단 거리를 O(V+E) 한 번으로 구하는 방법과 대표 활용 패턴을 알아봅니다.
재귀·스택으로 그래프를 깊이 우선 탐색하는 DFS의 동작 원리, in/out 타임스탬프, 방향 그래프 사이클 감지, 위상 정렬 기반까지 알아봅니다.
큐를 이용해 그래프를 층위별로 탐색하는 BFS의 동작 원리, 최단 경로 보장 이유, 경로 복원 구현, 이분 그래프 판별까지 알아봅니다.
그래프를 코드로 나타내는 세 가지 방법의 공간·시간 트레이드오프를 분석하고, 각 방식이 적합한 알고리즘 상황을 정리합니다.
O(n log n) 전처리로 구간 최솟값(RMQ)을 O(1)에 쿼리하는 희소 테이블의 원리, 구현, 멱등 연산 제약, LCA 응용까지 살펴봅니다.
다차원 공간을 재귀적으로 분할해 최근접 이웃 탐색과 범위 탐색을 O(log n)에 처리하는 k-d 트리의 구조, 빌드, 검색 알고리즘을 알아봅니다.
lowbit 트릭으로 prefix sum을 O(log n)에 업데이트·쿼리하는 펜윅 트리의 구조와 구현, 역위 수·2D BIT 응용까지 알아봅니다.
구간 전체를 한 번에 업데이트하는 Lazy Propagation의 원리, push_down 구현, 범위 업데이트·쿼리 O(log n) 달성, 그리고 실전 활용 패턴을 알아봅니다.
배열의 구간 합/최솟값/최댓값을 O(log n)에 쿼리·업데이트하는 세그먼트 트리의 구조, 빌드, 쿼리, 포인트 업데이트 구현을 알아봅니다.
문자열 집합을 O(m)으로 검색하고 접두사 공유로 메모리를 절약하는 트라이의 구조, 삽입·검색·삭제 구현, 자동완성과 사전 검색 적용 사례를 알아봅니다.
이진 힙으로 구현하는 우선순위 큐의 개념, Python heapq 활용법, 커스텀 비교, 그리고 다익스트라·Top-K·스케줄링 실전 적용을 알아봅니다.
완전 이진 트리를 배열로 표현하는 힙의 최대/최소 힙 속성, O(log n) 삽입·삭제, O(n) 힙 구성, 그리고 힙 정렬과 실전 활용을 알아봅니다.
리프 연결 리스트로 범위 검색을 O(k)로 처리하는 B+ 트리의 구조, 삽입·삭제, MySQL InnoDB 클러스터드 인덱스 적용 사례를 알아봅니다.
다진 트리로 디스크 I/O를 최소화하는 B 트리의 속성, 삽입 시 노드 분할, 삭제 시 병합·재분배, 그리고 파일 시스템과 DB 엔진 적용 사례를 알아봅니다.
AVL, 레드-블랙, B, B+ 트리, 스킵 리스트를 성능·구조·사용처 기준으로 비교하고, 상황에 맞는 트리를 선택하는 기준을 알아봅니다.
5가지 속성과 리컬러링·회전으로 O(log n)을 보장하는 레드-블랙 트리의 원리, 삽입 수정 알고리즘, 그리고 AVL 트리와의 실전 비교를 알아봅니다.
균형 인수(BF)와 4가지 회전 연산으로 O(log n)을 보장하는 AVL 트리의 원리, 삽입·삭제 구현, 그리고 실전 적용 가이드를 알아봅니다.
이진 탐색을 트리에 적용한 BST의 불변 조건, 검색·삽입·삭제 연산, 그리고 편향 문제와 균형 트리의 필요성을 알아봅니다.
전위·중위·후위 순회(DFS)와 레벨 순서 순회(BFS)의 원리, 재귀·반복 구현, 그리고 각 순회 방식의 활용 사례를 알아봅니다.
자식이 최대 2개인 이진 트리의 완전·포화·완벽·편향 유형, 배열 표현, 그리고 이진 트리의 주요 성질과 구현을 알아봅니다.
루트·부모·자식·리프·깊이·높이 등 트리의 핵심 용어와 성질, 다양한 트리 종류와 그 용도를 정리합니다.
가장 최근에 사용되지 않은 항목을 교체하는 LRU 캐시 — HashMap과 이중 연결 리스트로 모든 연산을 O(1)로 구현하는 방법을 알아봅니다.
중복 없는 원소 관리에 최적화된 집합 자료구조 — HashSet과 TreeSet의 구현 원리, 집합 연산, Python set의 내부 동작을 알아봅니다.
비트 배열과 여러 해시 함수를 이용해 공간을 극적으로 절약하는 확률적 자료구조 블룸 필터의 원리, 거짓 양성률, Python 구현을 알아봅니다.
분산 시스템에서 노드 추가·제거 시 최소한의 키만 재배치하는 일관된 해싱의 원리, 가상 노드, Python 구현을 알아봅니다.
해시 테이블에서 링크드 리스트 없이 배열 내 빈 슬롯을 탐색하는 개방 주소법 — 선형 탐사, 이차 탐사, 이중 해싱의 원리와 구현을 알아봅니다.
해시 테이블의 충돌을 분리 체이닝으로 해결하는 방법, 링크드 리스트 기반 구현, 부하율과 성능의 관계를 알아봅니다.
좋은 해시 함수의 조건, 다항식 해싱, 암호학적 해시(SHA-256)와 비암호학적 해시(MurmurHash)의 차이, Python hash() 내부 동작을 알아봅니다.
키-값 쌍을 O(1) 평균으로 저장·조회하는 해시 테이블의 구조, 충돌 해결 전략, Python dict 내부 동작까지 알아봅니다.
확률적 레벨 배정으로 O(log n) 탐색·삽입·삭제를 달성하는 스킵 리스트의 구조, 알고리즘, Python 구현을 알아봅니다.
스택의 원소를 단조 증가 또는 단조 감소로 유지해 Next Greater Element, 히스토그램 최대 넓이 등을 O(n)에 해결하는 기법을 설명합니다.
양쪽 끝 삽입·삭제가 O(1)인 덱의 구조, Python collections.deque 활용, 슬라이딩 윈도우 최솟값까지 알아봅니다.
선형 배열 큐의 공간 낭비 문제를 나머지 연산으로 해결하는 원형 큐의 원리와 Python 구현을 알아봅니다.
FIFO 원칙으로 동작하는 큐의 개념, 배열·연결 리스트 구현, 선형 배열 큐의 함정과 BFS 응용까지 알아봅니다.
LIFO 원칙으로 동작하는 스택의 개념, 배열·연결 리스트 구현, 괄호 검사·함수 호출 스택 등 핵심 응용을 알아봅니다.
분할 정복 알고리즘의 점화식 T(n)=aT(n/b)+f(n)을 세 가지 경우로 빠르게 해결하는 마스터 정리를 설명합니다.
알고리즘의 재귀적 수행 시간을 수학적으로 표현하는 점화식의 개념, 대표 유형, 그리고 재귀 트리로 푸는 방법을 알아봅니다.
prev·next 포인터로 양방향 탐색이 가능한 이중 연결 리스트의 구조와 구현, Python deque의 내부 동작을 설명합니다.
노드와 포인터로 구성된 단일 연결 리스트의 구조, 삽입·삭제·역전 알고리즘을 Python으로 직접 구현합니다.
크기가 자동으로 늘어나는 동적 배열의 구조, 성장 인자의 원리, Python list와 Java ArrayList의 내부 동작을 설명합니다.
가장 기본적인 자료구조인 배열의 메모리 구조, O(1) 인덱스 접근 원리, 삽입·삭제의 비용을 다룹니다.
개별 연산이 비싸도 전체 평균이 저렴한 이유를 설명하는 분할 상환 분석과 세 가지 기법을 알아봅니다.
빅오(O), 빅오메가(Ω), 빅세타(Θ) 세 가지 점근적 표기법의 수학적 의미와 실무 활용법을 비교합니다.
알고리즘 복잡도를 표현하는 빅오 표기법의 규칙, 자주 쓰이는 복잡도 클래스, 실수하기 쉬운 함정까지 정리합니다.
시간 복잡도와 공간 복잡도의 의미와 계산 방법, 그리고 두 지표 간의 트레이드오프를 예제로 알아봅니다.
알고리즘의 시간·공간 복잡도를 분석하는 방법과 최선·평균·최악 경우의 의미를 설명합니다.
알고리즘의 정의와 좋은 알고리즘이 갖춰야 할 5가지 필수 조건을 예제 코드와 함께 알아봅니다.