The Story of Joon

에라토스테네스의 체는 소수를 구할 때 흔히 쓰는 방식이다. 구현도 쉽기 때문에 정수론과 관련된 PS 문제에서 자주 만날 수 있다. 일반적으로는 아래와 같이 구현한다. vector sieve_of_eratosthenes(int n) { vector sieve(n + 1); vector prime; for (int k = 2; k

Linear Algebra in Problem Solving (1) Linear Algebra in Problem Solving (2) (현 포스트) Linear Algebra in Problem Solving (3) 이 포스트에서는 선형대수학 시리즈의 전편에 이어 좀더 고급 알고리즘에 대해 다룬다. 전편에서 만든 코드베이스를 그대로 사용할 예정이므로 전편을 먼저 읽는 것을 권장한다. 특성다항식 \(n\times n\) 행렬 \(A\)의 특성다항식(characteristic polynomial) \(f_A\)는 아래와 같이 정의된다. \[f_A(x):=\det(xI-A)\] 이 다항식은 최고차항의 계수가 1인 \(n\)차 다항식이며, 아래와 같이 여러 성질을 가지고 있는 중요한 다항식이다. \(f_A(x..