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..

Linear Algebra in Problem Solving (1) (현 포스트) Linear Algebra in Problem Solving (2) Linear Algebra in Problem Solving (3) 선형대수학(linear algebra)은 벡터 공간(vector space)과 선형 변환(linear transformation)에 대해서 다루는 학문으로, 여러 분야에서 많은 응용이 되고 있고 수학에서의 중요성 또한 매우 높다. 컴퓨터 과학도 예외는 아닌데, 이런 이유로 많은 학교에서 컴퓨터 과학/공학과에서 기초 선형대수학을 필수 과목으로 지정하기도 한다. 이 포스트 시리즈에서는 PS에서 등장하는 선형대수학 관련 문제들을 해결하기 위한 여러 가지 선형대수학 알고리즘을 다룰 예정이다. 일반..