개념 소수(Prime Number)는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수이다. 핵심 특징 소수 판별: 주어진 수가 소수인지 확인 소수 생성: 범위 내 모든 소수를 구함 소인수분해: 합성수를 소수의 곱으로 분해 소수 판별 O(√N) 판별 bool isPrime(long long n) { if (n <...

개념 유클리드 알고리즘은 두 정수의 최대공약수(GCD)를 효율적으로 구하는 알고리즘이다. 확장 유클리드는 GCD와 함께 ax + by = gcd(a, b)의 해를 구한다. 핵심 특징 유클리드: gcd(a, b) = gcd(b, a % b) 확장 유클리드: ax + by = gcd(a, b)의 정수해 (x, y)를 구함 모듈러 역원: ...

개념 CCW(Counter-Clockwise): 세 점의 방향 관계를 판별하는 기초 연산. 볼록 껍질(Convex Hull): 주어진 점들을 모두 포함하는 가장 작은 볼록 다각형. 핵심 특징 CCW: 외적의 부호로 반시계/시계/일직선 판별 볼록 껍질: 2D 점 집합의 외곽선 계산 기하 알고리즘의 기초: 선분 교차, 다각형 면적 등에 ...

개념 텍스트 내에서 패턴을 효율적으로 찾는 알고리즘들이다. 핵심 특징 브루트포스: O(NM) - 모든 위치에서 비교 KMP: O(N+M) - 실패 함수로 불필요한 비교 생략 라빈-카프: O(N+M) 평균 - 해싱으로 빠른 비교 Z 알고리즘: O(N+M) - Z 배열로 매칭 KMP 알고리즘 패턴의 접두사/접미사 정보를 활용하여...

개념 배열이나 리스트에서 두 개의 포인터를 사용하여 O(N)에 문제를 해결하는 기법이다. 핵심 특징 투 포인터: 두 포인터가 같은/다른 방향으로 이동하며 조건 탐색 슬라이딩 윈도우: 고정 또는 가변 크기의 구간을 이동하며 처리 O(N²) → O(N): 이중 for문을 단일 순회로 최적화 투 포인터 유형 1. 같은 방향 이동 (l...

개념 해를 찾는 과정에서 유망하지 않은 경로를 조기에 포기(가지치기)하고 다른 경로를 탐색하는 기법이다. 핵심 특징 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 그리디 ...