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

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

1

int` `fibonacci(``int` `n) {``  ``if` `(n == 0) {``    ``printf``(``"0"``);``    ``return` `0;``  ``} ``else` `if` `(n == 1) {``    ``printf``(``"1"``);``    ``return` `1;``  ``} ``else` `{``    ``return` `fibonacci(n‐1) + fibonacci(n‐2);``  ``}``}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력 1

1
2
3
4

3
0
1
3

예제 출력 1

1
2
3

1 0
0 1
1 2

힌트

출처

• 문제를 번역한 사람: baekjoon
• 어색한 표현을 찾은 사람: cyj101366
• 데이터를 추가한 사람: doju, wonrok97

알고리즘 분류

• 다이나믹 프로그래밍

풀이

소스코드

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

import sys

input = sys.stdin.readline
t = int(input())

cnt0 = [1, 0]
cnt1 = [0, 1]

for i in range(2, 41):
    cnt0.append(cnt0[i - 1] + cnt0[i - 2])
    cnt1.append(cnt1[i - 1] + cnt1[i - 2])

for _ in range(t):
    n = int(input())
    print(f"{cnt0[n]} {cnt1[n]}")

1. 카카오 vs 네이버, 글로벌 콘텐츠 무한경쟁

카카오 vs 네이버, 글로벌 콘텐츠 무한경쟁 : 네이버 뉴스 (naver.com)

카카오는 래디쉬, 네이버는 왓패드를 앞세워 글로벌 웹소설 플랫폼 경쟁에 나설 전망이다.

카카오가 래디쉬를 인수하는 핵심 이유는 IP 비즈니스이며, 영화, 드라마, 게임 등 다른 장르로 IP를 확장할 수도 있고, 온라인동영상서비스(OTT) 업체에 IP를 판매하는 것도 가능하며, 또한 웹소설 시장에 최대한 빠르게 진입해 네이버에 ‘IP 비즈니스 패권’을 넘겨주지 않기 위해서다.

2. 애플·구글 전방위 로비, 美 인앱결제 강제금지법 저지

애플·구글 전방위 로비, 美 인앱결제 강제금지법 저지 : 네이버 뉴스 (naver.com)

애리조나 주는 인앱결제 강제를 금지한 ‘HB2005’ 법을 세계 최초로 통과시키면서 큰 관심을 모았다. 하지만 애플, 구글의 강력한 로비 때문에 결국 이 법이 무산되면서 또 다른 논란이 예상된다.

3. “웨이브서 디즈니 영화 못본다” 韓상륙 앞두고 OTT 제휴 중단

“웨이브서 디즈니 영화 못본다” 韓상륙 앞두고 OTT 제휴 중단 : 네이버 뉴스 (naver.com)

SK텔레콤과 지상파 3사가 연합한 온라인동영상서비스(OTT) 웨이브에서 다음 달부터 어벤져스, 겨울왕국 등 월트 디즈니의 주요 콘텐츠를 볼 수 없게 된다. OTT 디즈니플러스의 한국 시장 진출을 앞두고 기존 제휴를 정리하고 있는 것으로 분석된다.

4. ‘디도스 사태’ 10년이 지났어도…여전히 허술한 한국 인터넷망

‘디도스 사태’ 10년이 지났어도…여전히 허술한 한국 인터넷망 : 네이버 뉴스 (naver.com)

3월24일 디도스 공격으로 네이버 일부 서비스가 중단됐다. 네이버 화면 갈무리

지난달 24일 네이버 포털(이하 네이버)이 서비스거부(Ddos·이하 디도스) 공격을 받아 일부 서비스가 중단돼 이용자들이 불편을 겪는 가운데, 네이버 관계자가 “블로그와 카페 등 일부 서비스 쪽만 당했다. 검색과 온라인쇼핑몰 등 메인 서비스용 아이피(회선)는 공격받지 않았다.”라고 말했다.

이 관계자는 “네이버 대상 디도스 공격은 이전에도 자주 있었지만 잘 막아냈다. 이번 공격은 우리의 대응 능력을 넘는 수준이었다”고 설명했지만, 컴퓨터 보안 전문가들과 누리꾼들 사이에선 이번 사태와 관련해 중요하게 짚어봐야 할 지점이 따로 있다는 지적이 나온다.

5. [단독] ‘웹툰’ 이름 네이버만 쓰나…美日이어 韓서도 상표등록

[단독] ‘웹툰’ 이름 네이버만 쓰나…美日이어 韓서도 상표등록 : 네이버 뉴스 (naver.com)

네이버가 국내외에서 ‘웹툰(webtoon)’ 상표권 선점에 나섰다. 이미 미국과 일본 같은 주요 시장에선 상표권을 획득한 것으로 확인됐다. 미국·일본·유럽 시장으로 진출하고 있는 국내 웹툰 플랫폼 기업들은 “네이버가 언제든지 웹툰이란 표현을 쓰지 못하게 할 수 있어 사실상 해외에서 경쟁 사업자를 견제하는 것”이라며 네이버가 추후 문제 삼을 수 있어 노심초사하고 있다.

6. “스마트주문→네이버주문” 확대…수수료 공짜인 ‘비대면주문’ 왜 키울까

“스마트주문→네이버주문” 확대…수수료 공짜인 ‘비대면주문’ 왜 키울까 : 네이버 뉴스 (naver.com)

네이버가 ‘네이버 주문’을 본격적으로 확대하기 시작했다. 네이버는 지난 2019년 9월 ‘스마트 주문(당시 QR코드 기반)’이라는 명칭으로 비대면 주문 서비스를 도입한 이후 대부분의 기간동안 수수료를 받지 않고 있다.

돈이 안되는 서비스인데도 네이버가 공을 들이는 것은 네이버페이 이용자 증가로 이어질 수 있다는 점, 특정 음식에 관심을 보이는 이들이 검색한 페이지에서 바로 주문까지 할 수 있도록 할 수 있게 해 검색의 질을 높일 수 있다는 점, 상생할 수 있다는 점 등 복합적인 요인이 작용했고, 특히 네이버페이 결제 시 혜택을 제공하는 방식으로 네이버페이 가맹점을 빠르게 넓힐 수 있다.

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

문제

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

힌트

• 피보나치 수를 구하는 여러가지 방법
• 
• 

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 수학
• 분할 정복을 이용한 거듭제곱

풀이

소스코드

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

문제

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

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 수학
• 다이나믹 프로그래밍

비슷한 문제

• 2747번. 피보나치 수
• 2748번. 피보나치 수 2
• 2749번. 피보나치 수 3
• 10826번. 피보나치 수 4

풀이

소스코드 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

문제

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

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 다이나믹 프로그래밍
• 임의 정밀도 / 큰 수 연산

비슷한 문제

• 2747번. 피보나치 수
• 2748번. 피보나치 수 2
• 2749번. 피보나치 수 3
• 10870번. 피보나치 수 5

풀이

소스코드 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

문제

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

힌트

• 피사노 주기

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 수학
• 분할 정복을 이용한 거듭제곱

비슷한 문제

• 2747번. 피보나치 수
• 2748번. 피보나치 수 2
• 10826번. 피보나치 수 4
• 10870번. 피보나치 수 5

풀이

소스코드 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

문제

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

힌트

출처

알고리즘 분류

• 수학
• 다이나믹 프로그래밍

비슷한 문제

• 2747번. 피보나치 수
• 2749번. 피보나치 수 3
• 10826번. 피보나치 수 4
• 10870번. 피보나치 수 5

풀이

소스코드 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번 피보나치 수

문제

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

힌트

출처

알고리즘 분류

• 수학
• 구현

비슷한 문제

• 2748번. 피보나치 수 2
• 2749번. 피보나치 수 3
• 10826번. 피보나치 수 4
• 10870번. 피보나치 수 5

풀이

소스코드 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))

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

문제

크기가 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

힌트

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: doju
• 잘못된 조건을 찾은 사람: dreammusic23

알고리즘 분류

• 수학
• 분할 정복
• 분할 정복을 이용한 거듭제곱
• 선형대수학

시간 제한

풀이

소스코드

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번 행렬곱셈

문제

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()