The Story of Joon

Linear Algebra in Problem Solving (1) Linear Algebra in Problem Solving (2) Linear Algebra in Problem Solving (3) (현 포스트) 기존 두 포스트에서는 선형대수학에 등장하는 기본적인 행렬 연산과 행렬에 관련된 중요한 식을 어떻게 효율적으로 계산하는지에 대해 알아보았다. 하지만 PS에서 대놓고 이런 값을 구하라고 요구하는 문제는 드물고, 보통 선형대수학을 응용해야 하는 문제가 나오게 된다. 대표적인 예시가 1편에서 나왔듯이 XOR을 \(\mathbb{F}_2\)에서 벡터의 덧셈으로 생각하는 방식이다. 이 포스트에서는 좀더 고급 응용인, 조합론에서 선형대수학이 응용되는 예시를 다룬다. 이분 그래프의 인접 행렬 PS는 물론..

에라토스테네스의 체는 소수를 구할 때 흔히 쓰는 방식이다. 구현도 쉽기 때문에 정수론과 관련된 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..