[백준] 11444번 피보나치 수6
2021-04-04
Algorithm / Python

[백준] 11444번 피보나치 수6

출처: [백준] 11444번 피보나치 수6

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 3363 1774 1450 57.494%

문제

피보나치 수는 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, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

예제 입력 1

1
1000

예제 출력 1

1
517691607

힌트

출처

알고리즘 분류

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sys

input = sys.stdin.readline

N = int(input())
mod = 1000000007
fibo = {}


def fibo_dp(n):
    if n <= 1:
        return n
    elif fibo.get(n):
        return fibo[n]
    else:
        if n % 2 == 1:  # 홀수
            m = (n + 1) // 2
            temp1 = fibo_dp(m)
            temp2 = fibo_dp(m - 1)
            fibo[n] = temp1 ** 2 + temp2 ** 2
            fibo[n] %= mod
            return fibo[n]
        else:  # 짝수
            m = n // 2
            temp1 = fibo_dp(m - 1)
            temp2 = fibo_dp(m)
            fibo[n] = (2 * temp1 + temp2) * temp2
            fibo[n] %= mod
            return fibo[n]


print(fibo_dp(N))


[백준] 10870번 피보나치 수5
2021-04-04
Algorithm / Python

[백준] 10870번 피보나치 수5

출처: [백준] 10870번 피보나치 수5

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 32430 20856 18483 65.290%

문제

피보나치 수는 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, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

1
10

예제 출력 1

1
55

힌트

출처

알고리즘 분류

비슷한 문제

풀이

소스코드 1 (재귀를 이용한 다이나믹 프로그래밍)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys

input = sys.stdin.readline

n = int(input())

fibo_memo = [-1] * 99


def fibo_dynamic(n):
    if 0 < n <= 2:
        return 1
    elif n == 0:
        return 0
    if fibo_memo[n] != -1:
        return fibo_memo[n]
    fibo_memo[n] = fibo_dynamic(n - 1) + fibo_dynamic(n - 2)
    return fibo_memo[n]


print(fibo_dynamic(n))

[백준] 10826번 피보나치 수4
2021-04-04
Algorithm / Python

[백준] 10826번 피보나치 수4

출처: [백준] 10826번 피보나치 수4

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 8506 2779 2352 39.437%

문제

피보나치 수는 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, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 10,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

1
10

예제 출력 1

1
55

힌트

출처

알고리즘 분류

비슷한 문제

풀이

소스코드 1 (반복문을 이용한 다이나믹 프로그래밍)

1
2
3
4
5
6
7
8
9
10
11
12
13
import sys

input = sys.stdin.readline
fibo = [-1] * 10001
fibo[0] = 0
fibo[1] = 1

N = int(input())

for i in range(2, N + 1):
    fibo[i] = fibo[i - 1] + fibo[i - 2]

print(fibo[N])
[백준] 2749번 피보나치 수3
2021-04-04
Algorithm / Python

[백준] 2749번 피보나치 수3

출처: [백준] 2749번 피보나치 수3

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 17482 5649 4570 38.230%

문제

피보나치 수는 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, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

1
1000

예제 출력 1

1
228875

힌트

  • 피사노 주기

출처

알고리즘 분류

비슷한 문제

풀이

소스코드 1 (반복문을 이용한 다이나믹 프로그래밍)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys

input = sys.stdin.readline

mod = 1000000
p = int(mod / 10 * 15)  # 피사노주기에 의해 M = 10^k 일 때, k > 2 라면, 주기는 항상 15 × 10^(k-1) 입니다
fibo = [0] * p
fibo[1] = 1

N = int(input())

for i in range(2, p):
    fibo[i] = fibo[i - 1] + fibo[i - 2]
    fibo[i] %= mod

print(fibo[N % p])

[백준] 2748번 피보나치 수2
2021-04-04
Algorithm / Python

[백준] 2748번 피보나치 수2

출처: [백준] 2748번 피보나치 수2

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 54967 21274 17729 38.752%

문제

피보나치 수는 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, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

1
10

예제 출력 1

1
55

힌트

출처

알고리즘 분류

비슷한 문제

풀이

소스코드 1 (반복문을 이용한 다이나믹 프로그래밍)

1
2
3
4
5
6
7
8
9
10
11
12
13
import sys

input = sys.stdin.readline
fibo = [-1] * 100
fibo[0] = 0
fibo[1] = 1

N = int(input())

for i in range(2, N + 1):
    fibo[i] = fibo[i - 1] + fibo[i - 2]

print(fibo[N])

소스코드 2 (재귀를 이용한 다이나믹 프로그래밍)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys

input = sys.stdin.readline

n = int(input())

fibo_memo = [-1] * 99


def fibo_dynamic(n):
    if n <= 2:
        return 1
    if fibo_memo[n] != -1:
        return fibo_memo[n]
    fibo_memo[n] = fibo_dynamic(n - 1) + fibo_dynamic(n - 2)
    return fibo_memo[n]

print(fibo_dynamic(n))

[백준] 2747번 피보나치 수
2021-04-04
Algorithm / Python

[백준] 2747번 피보나치 수

출처: [백준] 2747번 피보나치 수

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 128 MB 41190 19031 15550 47.730%

문제

피보나치 수는 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, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

1
10

예제 출력 1

1
55

힌트

출처

알고리즘 분류

비슷한 문제

풀이

소스코드 1 (반복문을 이용한 다이나믹 프로그래밍)

1
2
3
4
5
6
7
8
9
10
11
12
13
import sys

input = sys.stdin.readline
fibo = [-1] * 100
fibo[0] = 0
fibo[1] = 1

N = int(input())

for i in range(2, N + 1):
    fibo[i] = fibo[i - 1] + fibo[i - 2]

print(fibo[N])

소스코드 2 (재귀를 이용한 다이나믹 프로그래밍)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys

input = sys.stdin.readline
fibo = [-1] * 99


def fibo_dp(n):
    if n <= 1:
        return n
    elif fibo[n] != -1:
        return fibo[n]
    else:
        fibo[n] = fibo_dp(n - 1) + fibo_dp(n - 2)
    return fibo[n]


N = int(input())
print(fibo_dp(N))
[백준] 10830번 행렬제곱
2021-04-03
Algorithm / Python

[백준] 10830번 행렬제곱

출처: [백준] 2740번 행렬곱셈

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 10162 3490 2817 34.179%

문제

크기가 N x N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

예제 입력 1

1
2
3
2 5
1 2
3 4

예제 출력 1

1
2
69 558
337 406

예제 입력 2

1
2
3
4
3 3
1 2 3
4 5 6
7 8 9

예제 출력 2

1
2
3
468 576 684
62 305 548
656 34 412

예제 입력 3

1
2
3
4
5
6
5 10
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1

예제 출력 3

1
2
3
4
5
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512

힌트

출처

알고리즘 분류

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import sys

input = sys.stdin.readline

N, B = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]


def matrix_multiple(a, b):
    if b == 1:
        for i in range(N):
            for j in range(N):
                a[i][j] %= 1000
        return a
    else:
        if b % 2 == 0:  # 제곱수가 짝수일 때 AAAAAA --> (A^2)^2^2
            temp_matrix = [[0 for _ in range(N)] for _ in range(N)]
            c = matrix_multiple(a, b // 2)
            for i in range(N):
                for j in range(N):
                    for k in range(N):
                        temp_matrix[i][j] += c[i][k] * c[k][j]
                    temp_matrix[i][j] %= 1000
            return temp_matrix

        else:  # AAAAA --> (A^2)^2 * A
            temp_matrix = [[0 for _ in range(N)] for _ in range(N)]
            c = matrix_multiple(a, b - 1)
            for i in range(N):
                for j in range(N):
                    for k in range(N):
                        temp_matrix[i][j] += c[i][k] * a[k][j]
                    temp_matrix[i][j] %= 1000
            return temp_matrix


result = matrix_multiple(matrix, B)
for row in result:
    for value in row:
        print(value, end=" ")
    print()

[백준] 2740번 행렬곱셈
2021-04-03
Algorithm / Python

[백준] 2740번 행렬곱셈

출처: [백준] 2740번 행렬곱셈

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6980 4853 4230 71.610%

문제

N x M크기의 행렬 A와 M x K크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오.

입력

첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다.

출력

첫째 줄부터 N개의 줄에 행렬 A와 B를 곱한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.

예제 입력 1

1
2
3
4
5
6
7
3 2
1 2
3 4
5 6
2 3
-1 -2 0
0 0 3

예제 출력 1

1
2
3
-1 -2 6
-3 -6 12
-5 -10 18

힌트

출처

  • 잘못된 조건을 찾은 사람: bupjae
  • 문제의 오타를 찾은 사람: ekdns7952
  • 잘못된 데이터를 찾은 사람: WeissBlume

알고리즘 분류

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
A_matrix = [list(map(int, input().split())) for _ in range(N)]

M, K = map(int, input().split())
B_matrix = [list(map(int, input().split())) for _ in range(M)]

result_matrix = [[0 for _ in range(K)] for _ in range(N)]

for n in range(N):
    for k in range(K):
        for m in range(M):
            result_matrix[n][k] += A_matrix[n][m] * B_matrix[m][k]

for row in result_matrix:
    for value in row:
        print(value, end=" ")
    print()

!!![백준] 11401번 이항 계수3
2021-04-02
Algorithm / Python

!!![백준] 11401번 이항 계수3

출처: [백준] 11401번 이항 계수3

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

출력

를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

1
5 2

예제 출력 1

1
10

힌트

  • 페르마의 소정리 이용

출처

알고리즘 분류

시간 제한

풀이

소스코드 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
mod = 1000000007


def power(a, b):
    if b == 0:
        return 1
    else:
        if b % 2 == 0:  # B가 짝수일 때
            return (power(a, b // 2) ** 2) % mod
        else:
            return (power(a, b // 2) ** 2 * a) % mod


# Factorial dp
fact = [1 for _ in range(N + 1)]

for i in range(2, N + 1):
    fact[i] = fact[i - 1] * i % mod

child = fact[N]
parent = (fact[K] * fact[N - K]) % mod

# 페르마의 소정리
print((child % mod) * (power(parent, mod - 2) % mod) % mod)

# -------------------------------------------------
# for i in range(2, N + 1):
#     fact[i] = fact[i - 1] * i
#
# child = fact[N]
# parent = fact[K] * fact[N - K]

# print(int(child / parent) % mod) ==> 메모리초과

[백준] 1629번 곱셈
2021-04-02
Algorithm / Python

[백준] 1629번 곱셈

출처: [백준] 1629번 곱셈

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1

1
10 11 12

예제 출력 1

1
4

힌트

출처

알고리즘 분류

시간 제한

풀이

소스코드 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys

input = sys.stdin.readline


def power(a, b):
    if b == 1:
        return a % C
    else:
        if b % 2 == 0:  # B가 짝수일 때
            return power(a, b // 2) ** 2 % C
        else:
            return power(a, b // 2) ** 2 * a % C


A, B, C = map(int, input().split())
print(power(A, B))

소스코드 2

1
2
3
4
5
6
7
import sys

input = sys.stdin.readline

A, B, C = map(int, input().split())
print(pow(A, B, C))

팔로우

카테고리

최근 글

태그

알고리즘190
Python182
백준172
IT뉴스92
IT Issues92
구현65
자료구조55
네이버39
카카오30
스택26
JS24
Javascript24
자바스크립트24
큐22
문자열20
수학16
Programming16
애플15
그래프 탐색15
해시15
핀테크14
너비 우선 탐색14
BFS14
프로그래머스14
Spring Boot14
Java14
그래프13
DFS13
구글12
그리디12
×