이번 시간에는... 이번 시간에는 본 시리즈를 시작하게 된 계기가 된 뤼카의 정리를 한번 살펴보고자 한다. 시작하기에 앞서, 이 정리는 아래 링크를 기반으로 내가 이해한 내용을 덧붙여 작성했음을 밝혀 둔다. 틀린 부분, 내가 잘못 이해한 부분 혹은 논리적 비약이 생기는 부분이 있을 수 있으니 의문점이 생긴다면 댓글로 알려주면 매우매우매우 감사하겠다! https://ko.wikipedia.org/wiki/%EB%A4%BC%EC%B9%B4%EC%9D%98_%EC%A0%95%EB%A6%AC 뤼카의 정리 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 뤼카의 정리(Lucas' theorem, -定理)는 수론과 조합론에서 이용되는 정리로, 프랑스인 수학자 에두아르 뤼카(Édouard Luca..

이번 시간에는... 이번 시간에는 시도해 볼 수 있는 방법중 하나로 확장 유클리드 호제법을 사용해보자. 사실 조합을 구할 때 확장 유클리드 호제법이 쓰이는 일은 잘 없다(대부분 모듈러 연산을 위해 소수를 제시하고, 페르마 소정리를 이용해 풀 수 있기 때문이다). 하지만 확장 유클리드 호제법 역시 다양한 상황에서 사용될 수 있고, 특히 CS에서는 현대 암호학의 근간인 RSA 알고리즘에도 사용되므로 깊게 이해하고 넘어가보자. 확장 유클리드 호제법 이 포스팅에서도 정리된 바 있지만.. 2023.12.05 - [알고리즘 문제/백준] - [백준/3955] 캔디 분배 (Python) [백준/3955] 캔디 분배 (Python) Problem : https://www.acmicpc.net/problem/3955 39..

들어가기에 앞서.. 사족이라 접은 글로 남깁니다 :) 더보기 백준 온라인 저지를 풀면서, 내가 모르던 알고리즘과 수학 공식들을 종종 보게 된다. 그 때마다 구글링과 위키피디아를 뒤적거리면서 알고리즘을 찾아내고, 그걸 적용시키며 "아, 나는 이 문제를 이해했구나!" 라고 자만하게 된다. 하지만 사람 기억이 원체 시원찮아야지. 그 알고리즘을 적용해야 하는 다른 문제를 맞닥뜨리면, 어느 새 금붕어마냥 알고리즘을 다 까먹고 다시 똑같은 과정을 반복하게 된다. 실제로는 풀이하는 흉내만 냈을 뿐인 셈이다. 두 번째로, 이러한 새로운 정리를 문제 풀이 과정 중에 포스팅하면 나도, 그리고 어쩌다 이 블로그에 들어오는 사람들도 헷갈리기 시작한다. 제대로 정리되지 않은 셈이다. "나는 유클리드 호제법을 알고 싶은데, 알고..