주요 알고리즘 및 자료구조 구현 템플릿 요약

KMP 문자열 매칭 (KMP Pattern Matching) 패턴 문자열 내의 접두사와 접미사가 일치하는 최대 길이를 계산하여 불필요한 비교를 줄이는 알고리즘입니다. #include <iostream> #include <vector> #include <string> using namespace std; vector<int> compute_pi(const string& p) { int m = p.size(); vector<int> pi(m, 0); ...

9월 19일 12:04에 게시됨

Codeforces Round 991 (Div. 3) F - 구간 최대公约수와 차분 배열

문제 접근 이 문제는 구간 내에서의 최대公约수(GCD) 값을 구하는 문제이다. 핵심 아이디어는 차분(difference) 배열을 활용하는 것이다. 원래 배열에서 인접한 요소들의 차이를 구하면, 해당 구간의 GCD는 차분 배열의 특정 구간 GCD와 동일해진다. 따라서 우리는 구간 GCD를 효율적으로 구할 수 있는 자료구조를 사용하면 된다. 두 가지 대표적인 방법을 소개한다. 방 ...

7월 10일 06:27에 게시됨