페르마의 소정리를 이용한 큰 수의 모듈러 연산 역원 찾기 (combination 계산에 이용)
https://uneducatedjungler.tistory.com/120
밀러 라빈 알고리즘을 이용한 소수 판별 (큰 수에서는 확률적, 1e15 이하 작은 수에서는 확정적 판별 가능)
https://uneducatedjungler.tistory.com/121
폴라드 로 알고리즘을 이용한 소인수분해 (유사난수와의 비교로 구한 랜덤인수를 밀러 라빈으로 소수 판별)
https://uneducatedjungler.tistory.com/133
오일러 피 함수 (소인수분해를 이용한 빠른 계산)
class 6에 정수론 관련 문제가 좀 있어 이쪽을 파다보니 조금 깊게 들어간 것 같다. 풀 수 있는 P1~D4 문제가 몇개 생겨서 풀었더니 P4가 됐다.
week06의 목표는 세그먼트 트리와 KMP의 이해와 응용으로 두고 있다.
지난주는 RB트리 구현량이 빡세서 아예 손놓고 있다가 마지막 이틀정도 시간이 남아서 몰아서 풀었는데, 이번 week 06은 이해가 중요하고 구현량은 그리 많지 않아 보이니 알고리즘도 꾸준히 병행해봐야겠다.
'PS 공부 기록' 카테고리의 다른 글
| Platinum III, CLASS 6 (0) | 2021.12.17 |
|---|---|
| Week 06 알고리즘 공부 기록 [세그먼트 트리] (0) | 2021.12.16 |
| 12월 알고리즘 PS 계획 (희망회로) (0) | 2021.12.07 |
| 플래티넘 (2) | 2021.12.01 |
| 골?드 (0) | 2021.11.17 |