팩토리얼(factorial)의 비밀 - 스털링 근사 공식과 자리수 계산하기

1. 팩토리얼의 자리수 $$n! = 1\times2\times...\times n$$ 로 계산된다. 어떤 정수에 1~9까지 중 하나를 곱하면 자리수가 늘어날수도 있지만, 늘어나지 않을수도 있다 하지만 10 이상을 곱하면 최소한 1자리는 확실히 늘어난다. 이런 통찰에 근거해 10! 이상부터 생각해보면... 10! 이상은 이전 팩토리얼에 10 이상의 수가 계속해서 곱해진다는 특징이 있다 $$11! = 10! \times 11$$ $$12! = 11! \times 12$$ $$13! = 12! \times 13$$ ... 그러므로 10! 이상의 팩토리얼은 그 자리수가 유일하게 결정된다. 그 말은 팩토리얼의 자리수를 알면, 몇 팩토리얼인지도 계산이 가능하다. 2. 자리수를 계산하는 방법 123의 자리수는 3자리인데 $..

• format_list_bulleted 정수론
• · 2023. 1. 2.
• textsms

정수론 - 합과 곱은 왜 계속 나눠도 문제가 없는가? -

1. 문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 00과 1을 이용해서 만들 수 있는 길이 n의 이진수열의 개수를 15746으로 나눈 나머지를 구하는 문제 2. 풀이 가능한 경우의 수를 나열해서 규칙을 찾으면 간단해진다 1,2,3,5,8,...로 이어져서 피보나치 수열이라는 느낌이 온다 그래서 한번 해보면 from sys import stdin n = int(stdin.readline()) dp = [0] * 1000001 dp[1] = 1..

• format_list_bulleted 정수론
• · 2022. 9. 9.
• textsms

DFS/BFS 완전정복을 위한 재귀함수 기본이론

1. 재귀함수 DFS/BFS를 구현하려면 재귀함수도 이해하고 있어야한다 재귀함수는 자기 자신을 다시 호출하는 함수 def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() 이 코드를 실행하면 '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력한다 정의한 recursive_function()이 자기 자신을 계속해서 추가로 불러오기 때문이다 물론 어느정도 출력하다보면 오류 메시지를 출력한다 재귀의 최대 깊이를 초과했다는 애용으로 파이썬 인터프리터가 호출 횟수의 제한이 있기 때문이다 무한대로 재귀 호출을 할 수는 없으며 애초에 그런 문제 또한 출제될리는 없다 2. 재귀함수 예시 어느 한 컴퓨터공학과 학생..

• format_list_bulleted DFS BFS 정복기
• · 2022. 6. 30.
• textsms