say repository

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);
    }
}

코드

import sys
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    cnt0 = [1,0]
    cnt1 = [0,1]
    
    if n == 0:
        print(cnt0[0],cnt1[0])
    elif n ==1:
        print(cnt0[1], cnt1[1])
    else:
        for i in range(2,n+1):
            cnt0.append(cnt1[i-1])
            cnt1.append(cnt0[i-1] + cnt1[i-1])
        print(cnt0.pop(), cnt1.pop())

풀이

재귀 함수를 사용하면 시간 초과가 당연히 나고 다이나믹 프로그래밍을 활용해야한다.

Bottom-Up 방법으로 n이 0부터 n까지의 경우의 0과 1이 출현하는 빈도수를 구하자.

점화식을 만들기 위해 규칙을 찾아보면 다음과 같다.

• i번째 0 출현 = i-1 번째 1 출현
• i번째 1 출현 = i-1 번째 0 출현 + i-1 번째 1 출현

n이 0과 1일 때는 리스트에 넣어두고 n이 2일 때부터 반복문을 돌며 점화식을 수행한다.

cnt0과 cnt1 배열의 마지막 원소가 정답이다.

import sys
from collections import deque
n, k = map(int,sys.stdin.readline().split())
MAX = 100000
visited = [0] * (MAX+1)

def bfs():
    q = deque()
    q.append(n)
    while q:
        x = q.popleft()
        if x == k:
            print(visited[x])
            break
        for nx in (x-1, x+1, x*2):
            if 0<=nx<=MAX and not visited[nx]:
                visited[nx] = visited[x] + 1
                q.append(nx)
bfs()

풀이

수빈과 동생이 움직일 수 있는 조건이 0부터 100000 니까 max값을 준다.

그리고 bfs을 실행해서 처음 수빈이의 위치를 큐에 넣는다.

수빈이가 동생을 찾을 때까지

수빈이가 움직일 수 있는 경우인 걷기 x-1 와 x+1 , 순간이동 x*2 이 세 가지씩 그래프를 뻗어나간다.

그래프가 한 층씩 생길때마다 전 층의 값 +1을 해주고 동생을 찾으면 이 값을 리턴한다.

import sys
n = int(sys.stdin.readline())
chess = [0] * n
cnt = 0

def possible(x):
    for i in range(x):
        #행 돌면서
        #상하좌우 or 대각선에 퀸이 있다면 False 반환
        #여기서 대각선은 행-행 = 열-열
        if chess[i] == chess[x] or abs(chess[x]-chess[i]) == abs(x-i):
            return False
    return True

def solution(x):
    global cnt
    #재귀로 x가 계속 +1 되는데 x가 n이 되면 경우의 수 +1
    if x==n:
        cnt+=1
    else:
        for i in range(n):
            #chess판의 (x,i)에 퀸을 놓는다.
            chess[x] = i
            if possible(x):
                #퀸이 상하좌우, 대각선으로 공격할 수 없다면 다음 퀸 놓기
                solution(x+1)

solution(0)
print(cnt)

풀이

재귀함수 dfs와 백트래킹을 활용해 풀었다.

1) 퀸을 체스판에 놓는다.

chess[i] = j 는 ( i, j ) 에 퀸이 있다는 뜻이다.

2) 놓은 퀸의 상하좌우에 퀸이 있으면 False

3) 놓은 퀸의 대각선에 퀸이 있으면 False

4) 퀸의 개수가 입력값일 때 cnt+=1

python으로는 계속 시간초과가 난다.

pypy3로 통과했다.

python으로 시간초과가 나지 않는 방법이 있으면 알려주세요...

코드 1

import sys
t = int(sys.stdin.readline())
#스택
for i in range(t):
    string = sys.stdin.readline().rstrip()
    string += " "

    stack = []
    for j in string:
        if j != " ":
            stack.append(j)
        else:
            while stack:
                print(stack.pop(),end = "")
            print(' ',end="")

풀이 1

문자열을 넣고 거꾸로 출력을 하니까 스택 자료구조로 구현했다.

문자열을 스택에 넣고 " "을 만나면 pop() 한다.

주의할 점은 마지막 문자열 끝에 " "가 안 들어가니까 뒤집기가 안된다. 

그래서 마지막 문자열에도 " "을 넣어준다.

코드 2

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

#문자열 슬라이싱
for i in range(t):
    string = sys.stdin.readline().rstrip().split()
    for str in string:
        print(str[::-1],end=" ")
    print()

풀이 2

python은 문자열을 다루기 좋은 언어이다.

python의 장점을 활용해 " "마다 잘라서 str[::-1] 을 사용해 뒤집어줬다.

import sys
t = int(sys.stdin.readline())
def sol(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return sol(n-3) + sol(n-2) + sol(n-1)

for i in range(t):
    n = int(sys.stdin.readline())
    print(sol(n))

풀이

n이

1 일 때 1 -> 총 1가지

2일 때 1+1, 2 -> 총 2가지

3일 때 1+1+1, 1+2, 2+1, 3 -> 총 4가지

4일 때 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2 -> 총 7가지

5일 때 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+1+3, 1+3+1, 3+1+1, 2+3, 3+2, 2+2+1, 2+1+2, 1+2+2 -> 총 13가지

...

이렇게 구해보면 규칙을 찾을 수 있다.

점화식을 세워 구하면 된다.

f(n) = f(n-3) + f(n-2) + f(n-1) (단, n>3)

import sys
n, s = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))

def dfs(idx,sum):
    global cnt
    if idx>=n:
        return
    sum += arr[idx]
    if sum == s:
        cnt+=1
    dfs(idx+1, sum)
    dfs(idx+1, sum-arr[idx])

cnt = 0
dfs(0,0)
print(cnt)

풀이 1

백트래킹으로 구현했다. 

완전탐색을 하면서 불필요한 탐색은 가지치기하는 방법이다.

dfs을 하면서

1. 현재 arr [idx] 을 포함하는 경우

2. 현재 arr [idx] 을 포함하지 않는 경우

경우의 수를 가지치기 한다.

코드 2

import sys
from itertools import combinations
n, s = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))

#조합
cnt = 0
for i in range(1,n+1):
    comb = list(combinations(arr,i))
    for j in comb:
        if sum(j) == s:
            cnt+=1

print(cnt)

풀이 2

조합을 사용해서 크기가 1부터 n까지의 부분수열을 만들고 그 합이 s일 때 cnt+=1 한다.

import sys
import math

arr = [True for _ in range(1000001)]
for i in range(2,int(math.sqrt(1000001))):
    if arr[i]:
        j = 2
        while i*j<1000001:
            arr[i*j] = 0
            j+=1

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break

    flag = 0
    for i in range(3,len(arr)):
        if arr[i]:
            if arr[n-i]:
                print(n, "=", i, "+", n-i)
                flag = 1
                break
    if flag == 0:
        print("Goldbach's conjecture is wrong.")

주워진 범위 내의 모든 소수를 구할 때는 에라토스테네스의 체 알고리즘을 사용해야 효율적이다.

하지만, 처음에 arr의 크기를 1000001 로 주지 않고 입력받은 값으로 계속 반복문을 돌아서 시간 초과가 났다..

입력값의 조건 중 테스트 케이스의 개수는 100000개를 넘지 않는다고 쓰여 있다.

이 조건을 활용해 에라토스테네스의 체로 구현하면 시간 초과를 겪지 않는다.