공부 저장소

2020/02/21 검색 결과

해당 글 3건

행렬 AB와 BA의 고유값(eigenvalue)은 서로 같은가?

두 행렬의 크기가 서로 달라 고유값의 개수가 다를 수도 있지만, 놀랍게도 추가적인 고유값들은 모두 0이다. 즉 $AB$의 고유값을 $x_1, x_2, \dots x_n$, $BA$의 고유값을 $y_1, y_2 \dots, y_m$ ($n \leq m$이라 가정) 으로 두면, $x_1 = y_1, x_2 = y_2, \dots, x_n = y_n$, $y_{n+1} = y_{n+2} = \cdots = y_m = 0$ 을 만족하는 재배열이 존재한다는 것이다. 보조정리 1. $A$가 $m \times n$, $B$가 $n \times m$ 행렬이라고 하자. 그렇다면 아래를 만족한다. $$ tr(AB) = tr(BA) $$ (증명 생략) 보조정리 2. $$ tr ((AB)^k) = tr ((BA)^k) $$ ..

Mathematics 2020. 2. 21. 14:46

백준 온라인 저지 - 13970. Power towers

오일러 파이 함수(Euler's totient function)은 정수론적 함수이다. $$\phi(n) = \left| \{ 1\leq m \leq n : \gcd(m, n) = 1 \} \right|$$ 로 정의된다. 페르마 소 정리부터 오일러 정리 등 KMO에서도 많이 다룬다. 코딩에서는 어디에 쓰일까? 단적인 예로는 확장 유클리드 호제법 없이 modular inverse를 구할 때 사용된다. $a^{\phi(p) - 1} \mod p$가 바로 $p$에 대한 $a$의 modular inverse이다. 좀 더 어려운 예시로는.. https://www.acmicpc.net/problem/13970 13970번: Power towers In this example, as M = 10, we are inte..

Problem Solving 2020. 2. 21. 13:56

문자열 Hashing에 대하여

Hash는 특정 조건을 만족하는 함수이다. 정의역은 굉장히 넓고 그에 비해 치역은 좁다. 그래도 충분히 넓어서 서로 다른 정의역 원소에 대해 함수값이 충돌할 가능성이 적다. 치역은 보통 C++에서의 long long 등의 자료 형태로 표현되어 처리하기 간단하다. 그렇기 때문에 해시값이 같은 경우 두 대상은 서로 같을 확률이 아주 높다. 특히 부분 문자열에 대한 문제에서 많이 사용한다. 부분 문자열끼리 서로 완벽하게 비교하는데 걸리는 시간은 너무 오래 걸린다. 그렇기 때문에 해시값을 통해 비교와 처리를 하는 경우가 많다. 문자열 Hashing을 사용하는 문제 예시 https://www.acmicpc.net/problem/10840 10840번: 구간 성분 첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로..

Problem Solving 2020. 2. 21. 00:00