728x90 페르마의 소정리 썸네일형 리스트형 [백준알고리즘] 11401번: 이항 계수 3 -Python [백준알고리즘] 11401번: 이항 계수 3 -Python https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 어렵다.. 처음에 풀다가 방법을 찾아봤다 그러다가 "페르마의 소정리"와 "확장 유클리드 호제법"으로 해결이 가능하다는 것을 확인하고 공부했던 내용을 다시 확인했다. 우선 "확장 유클리드 호제법"을 확인하고 해당 방법으로 문제를 해결했다. 이전에 공부했던 내용이라 다른 분의 블로그를 참조하니 이해가 쉬웠다. 해당 블로그의 링크는 아래이며 이해가 안되면 더 찾아보면.. 더보기 [백준알고리즘] 11051번: 이항계수 2 -C [백준알고리즘] 11051번: 이항계수 2 -C https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이번 문제도 이전 문제와 같이 이항 계수문제이다. 하지만 범위가 훨씬 더 커졌기 때문에 아까와 같은 방식으로 하려고 하면 int의 범위를 넘어서 overflow를 일으킬 것이다. double의 경우는 해보지 않았지만 속도가 느릴 것이다. 하지만 여기서는 모듈러 연산(Modular Arithmetic: 나머지 연산)을 이용해서 int범위 안에서 돌아가도록 할 것이다. 문제를 주었을 때 10007로 나눈 나머지를 구하라고 .. 더보기 이전 1 다음
