poorman

https://www.acmicpc.net/problem/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

해결 방안 - 1

1. 너비우선탐색(BFS) 알고리즘을 이용하여 N 값이 1이 될때까지 탐색한다.

2. FIFO 큐를 사용하기 위해서 collections.deque를 이용하여 popleft로 값을 꺼낸 후에 새로운 노드를 append한다.

3. 노드 값은 [value, count] 형태로 사용하고 너비 우선 탐색이므로 value가 1이 되는 순간의 count를 리턴한다.

소스 코드 - 1

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())

def BFS(x):
    cnt = 0
    Q = deque([(x,cnt)])
    while(Q):
        x,cnt = Q.popleft()
        if x == 1:
            return cnt
        if x % 3 == 0:
            Q.append([x//3,cnt+1])
        if x % 2 == 0:
            Q.append([x//2,cnt+1])
        Q.append([x-1,cnt+1])
    return -1

print(BFS(N))

수행시간 : 2372ms

해결 방안 - 2

1. 깊이우선탐색(DFS) 알고리즘을 이용하여 N 값이 1이 될때까지 탐색한다.

2. LIFO 스택을 사용하여 pop으로 값을 꺼낸 후에 새로운 노드를 append한다.

3. 노드 값은 [value, count] 형태로 사용하고 value 값이 1이 되는 순간의 count값으로 min_count의 최소 값을 갱신한다.

4. 최소 count 값만 구하면 되기 때문에 min_count보다는 더 깊게 탐색하지 않는다.

5. 깊이 우선 탐색이 모두 끝났을 때 min_count값을 리턴한다.

소스 코드 - 2

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
def DFS(x):
    min_cnt = x
    cnt = 0
    Q = deque([(x,cnt)])
    while(Q):
        x,cnt = Q.pop()
        if cnt >= min_cnt:
            continue
        if x == 1:
            min_cnt = min(min_cnt, cnt)
        Q.append([x-1,cnt+1])
        if x % 2 == 0:
            Q.append([x//2,cnt+1])
        if x % 3 == 0:
            Q.append([x//3,cnt+1])
    return min_cnt

print(DFS(N))

수행시간 : 1272ms

* 해당 문제는 BFS/DFS의 탐색에 시간이 많이 소요되어 비효율적이다.

해결 방안 - 3

1. 재귀함수를 이용하여 현재 위치에 도달하는 최소 코스트를 리턴한다.

2. 현재 위치의 최소 코스트에 도달하기 위해서는 2,3으로 나누어 떨어지는 거리(x//2,x//3) + 나머지 거리(x%2,x%3) + 1이다. f(x) = min( f(x//3) + x%3 + 1, f(x//2) + x%2 + 1)

3. 거리가 1일때는 0, 거리가 2,3일때는 1의 코스트가 든다. f(1) = 0, f(2) = 1, f(3) = 1

소스 코드 - 3

import sys
input = sys.stdin.readline

N = int(input())
def fnc(x):
    if x == 1:
        return 0
    elif x <= 3:
        return 1
    return min(fnc(x//3) + x%3 + 1, fnc(x//2) + x%2 + 1)
print(DP(N))

수행시간 : 72ms

https://www.acmicpc.net/problem/10826

문제

피보나치 수는 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. 재귀 함수를 이용한다. f(n+2) = f(n+1) + f(n)

2-1. 함수 f(n)는 n이 0일때 0, 1일때 1을 리턴한다.

2-2. n이 2이상의 경우에 f(n-2) + f(n-1)을 리턴한다.

소스코드 - 1

n = int(input())

def fibonacci(x):
    if x == 0:    return 0
    if x == 1:    return 1
    return fibonacci(x-1) + fibonacci(x-2)
    
print("%d" % fibonacci(n))

*재귀 함수를 사용하는 경우에 x가 커질수록 메모리 사용량과 연산 시간이 증가하여 시간 초과로 실패한다.

해결 방안 - 2

1. Dynamic Programming 알고리즘으로 n-1, n-2번째의 수만 메모리에 갱신하여 연산해 나간다.

2. 파이썬의 특징을 활용하여 x, y = y, x+y 연산으로 x에는 n-1번째 값을, y에는 n-1번째와 n-2번째의 합을 취한다.

소스코드 - 2

n = int(input())

def fibonacci(k):
    x, y = 0, 1
    for i in range(k):
        x, y = y, x+y
    return x 

print("%d" % fibonacci(n))