BOJ-11444 피보나치 수 6 Swift
문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.출력첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.내가 푼 풀이문제를 보았을때 이문제는..
BOJ-11401 이항 계수 3 Swift
문제자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.입력첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 4,000,000, 0 ≤ \(K\) ≤ \(N\))출력 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 출력한다.내가 푼 풀이수학적 지식의 벽을 느낀 문제였다... 다른사람의 풀이를 보고 이해하는데도 오래걸렸다.하지만 알아두면 좋을 것 같아서 이렇게 기록해둔다. 접근방법: 분할정복, 페르마의 소정리, 모듈러 연산, 이항계수, 지수법칙1. 이항계수 구하기: \(\binom{N}{K}\) = ${_N}C{_K}$ = $\frac{N!}{(N-K..
BOJ-10986 나머지 합 Swift
문제수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.입력첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)출력첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.내가 푼 풀이첫번째 접근방법: 세그먼트 트리(시간초과)구간합트리로 해당 구간합을 구해 나누어 떨어지는지 확인해보았다.구간합트리의 모든노드는 모든 구간합의 경우의수가 아니였고, 구간합트리를 만..
