[Algorithm] BOJ 28212. Classical Summation Problem

https://www.acmicpc.net/problem/28212 \(1\) 이상 \(n\) 이하의 자연수 \(k\)개로 이루어진 임의의 쌍 \((a_1, ..., a_k)\)에 대하여 함수 \(y=|x-a_1|+...+|x-a_k|\)가 최소가 되는 \(x\)의 값들 중 최솟값을 모든 가능한 \((a_1, ..., a_k)\) 쌍에 대하여 구한 후 그 합을 \(998244353\)으로 나눈 나머지를 출력하는 문제입니다. 시간 제한은 \(2\)초, 메모리 제한은 \(1024\)MB입니다. 함수 \(y=|x-a_1|+...+|x-a_k|\)가 최소가 되는 \(x\)의 값들 중 최솟값이 \(i\)라는 것은, \(a_1, ..., a_k\)을 오름차순으로 정렬했을 때 \(1\) 이상 \(i-1\) 이하..

• format_list_bulleted Programming/Algorithm
• · 2025. 7. 13.
• textsms

[Algorithm] BOJ 17372. 피보나치 수의 최대공약수의 합

본 글에서 사용되는 나누기 연산은 모두 몫 연산입니다.https://www.acmicpc.net/problem/17372  \(10^9\) 이하의 자연수 \(n\)에 대하여, \(\sum_{i=1}^n\sum_{j=1}^n \gcd(f_i, f_j)\)을 \(10^9+7\)로 나눈 나머지를 구하는 문제입니다. 시간 제한은 \(1\)초, 메모리 제한은 \(512\)MB입니다. 여기에서 \(\{f_n\}_{n \in \mathbb{N}}\)은 \(f_1=f_2=1, f_{n+2}=f_{n+1}+f_n\)으로 정의되는 피보나치 수열입니다. \[\text{(Ans.)}=\sum_{i=1}^n\sum_{j=1}^n \gcd(f_i, f_j)\]  먼저, \(\gcd(f_i, f_j)=f_{\gcd(i, j)}\)..

• format_list_bulleted Programming/Algorithm
• · 2024. 9. 6.
• textsms

[Algorithm] KMP

pi 배열과 ans 배열을 채우는 함수를 하나로 묶어 간단히 만든 코드다. 단, 함수 안에서 반복문이 \( i=1 \)부터 돌아가기 때문에 키워드를 찾고 싶은 문자열 앞에 $, #과 같이 쓰지 않는 문자열을 추가해 주어야 함에 유의하자. #include using namespace std; string s, p; vector pi, ans; void kmp(string s, string p, vector& f) { int n=s.size(), m=p.size(); int j=0; for(int i=1;i0&&s[i]!=p[j])) j=pi[j-1]; if(s[i]==p[j]) f[i]=++j; } } int main() { getline(cin, s); getline(cin, p); s="$"+s; pi..

• format_list_bulleted Programming/Algorithm
• · 2024. 1. 4.
• textsms

[Algorithm] Manacher's Algorithm

Manacher's Algorithm(매내처 알고리즘) 1. 개요 본 알고리즘은 문자열의 특정 문자를 중심으로 하는 palindrome(팰린드롬)의 최대 반지름을 \( O(N) \)에 계산하는 알고리즘이다. 여기에서, 홀수 길이 팰린드롬의 반지름은 중심 문자와 말단 문자의 index(인덱스) 차이로 정의된다. 이를테면, 문자열이 abcba 인 경우에 중심 문자는 2번 인덱스의 c 이고 말단 문자는 0번 (또는 4번) 인덱스의 a 이므로 반지름은 2가 되는 것이다. naïve한 경우에는 각 인덱스에 대해 양쪽으로 문자를 확장해 가면서 비교한다. 이 경우에는 모든 문자가 같은 최악의 경우에 \( O(N^2) \)의 시간복잡도를 갖는다. \( N \) 이 \( 10^5 \) 이상인 문제에는 적용하기 어렵다. ..

• format_list_bulleted Programming/Algorithm
• · 2024. 1. 3.
• textsms