![]()
모듈로 연산? 모듈로 연산은 어떠한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로 나머지 연산(mod)라고 한다(프로그래밍 언어에서 %연산자를 의미한ㄷ.). 정수론에서 모듈로 연산이라는것이 있는데, 이는 정수의 합과 곱을 어떤 주어진 수의 나머지에 대해 정의하는 방법이다. 모듈로 연산은 아래 세가지를 충족시킨다고 한다. 나머지는 이 공식에 부합하지 않는다고 한다. (A + B) % C = ((A % C) + (B % C)) % C (A - B) % C = ((A % C) - (B % C)) % C (A * B) % C = ((A % C) * (B % C)) % C 유도해보기 A,B를 각각 위와 같이 정의하고 유도해보면 아래와 같다. 이 원리를 이용해 풀었던 문제이다. https://www.acmicp..
URL : https://www.acmicpc.net/problem/15624 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 살펴보기 피보나치 관련 문제이다. 입력은 첫줄에 n이 주어지고 이 n은 1000000보다 작거나 같은 자연수 또는 0이다. 출력은 n번째 피보나치 수를 1000000007로 나눈 나머지를 출력하는 것이다. 문제 풀이 우선적으로 큰 수에 대한 피보나치 수이므로, 처음에 동적계획법을 이용해서 접근하였다. import sys sys.setrecursionlimit(10**6) saved = [None] * 10000001 def fibonacci(x): if x == 0: return..
