백준 24416번

백준 24416번 풀이

1. 피보나치 함수 정의

1-1. top down 방식

• 상위 node 부터 필요한 값들을 하위 node에서 찾아가면서 연산
• 각 node는 메모이제이션 공간에 저장해놓는다.
• 함수 실행 시 메모이제이션 공간에 해당 노드가 존재하는 지 검색하고 있으면 그 값을 출력 > 중복 연산 피할 수 있음

# cnt = 0 # 함수 호출 횟수를 카운팅하기 위한 전역 변수
memo_top_down = [0] * 99999 # 수열을 저장해놓고 꺼내쓰기 위한 공간 / 0으로 초기화
def fibonacci_dynamic_top_down(n): # top - down 방식으로 표현한 피보나치 수열
    global cnt
    if n < 3: # 1, 2번째는 1로 처리 
        return 1
    elif memo_top_down[n-1] != 0:
        return memo_top_down[n-1]
    memo_top_down[n-1] = \
        fibonacci_dynamic_top_down(n-1) + fibonacci_dynamic_top_down(n-2)
    cnt += 1 # 코드2 카운팅
    return memo_top_down[n-1]

1-2. bottom-up 방식

• 하위 node 부터 차례대로 더하면서 상위 node를 연산
  • 중복 연산을 피하기 위해 가장 최근에 연산된 node 정보를 last_iter에 기억해놓는다.
  • 연산은 last_iter node의 바로 다음 node 부터 연산한다.
• 각 node는 메모이제이션 공간에 저장해놓는다.
• 함수 실행 시 메모이제이션 공간에 해당 노드가 존재하는 지 검색하고 있으면 그 값을 출력

# cnt = 0 # 함수 호출 횟수를 카운팅하기 위한 전역 변수
memo_bottom_up = [0] * 99999 # 수열을 저장해놓고 꺼내쓰기 위한 공간 / 0으로 초기화
last_node = 0 # bottom - up 방식에서 마지막으로 계산된 point를 저장하기 위한 공간
def fibonacci_dynamic_bottom_up(n): # bottom - up 방식으로 표현한 피보나치 수열
    global last_node, cnt
    if n < 3: # node 1, 2는 값 1로 처리 
        return 1
    if memo_bottom_up[n-1] == 0:
        for i in range(last_node + 1, n+1): # 가장 최근에 연산된 node의 바로 다음 node 부터 연산
            memo_bottom_up[i-1] = \
                fibonacci_dynamic_bottom_up(i-1) + fibonacci_dynamic_bottom_up(i-2)
            cnt += 1
            last_node = i # 현재 연산한 node의 정보를 last_node에 저장
    return memo_bottom_up[n-1]

1-3. 재귀함수

• 가장 기본적인 재귀함수 형태

def fibonacci_re(n): # 재귀 함수로 표현한 피보나치 수열
    global cnt
    if n < 3: # 1, 2번째는 1로 처리 
        cnt += 1 # 코드1 카운팅
        return 1
    else:
        return fibonacci_re(n - 1) + fibonacci_re(n - 2)

2. 입력 및 출력

• 백준 제출 답안은 다음과 같이 구한다.

n = int(input())
cnt = 0
fibonacci_re(n)
print(cnt, end = ' ')

cnt = 0
fibonacci_dynamic_top_down(n)
print(cnt)

5 8

• bottom-up 방식 비교

n = 36

%time result1 = fibonacci_re(n)
%time result2 = fibonacci_dynamic_top_down(n)
%time result3 = fibonacci_dynamic_bottom_up(n)

print(result1, result2, result3)

Wall time: 3.25 s
Wall time: 0 ns
Wall time: 0 ns
14930352 14930352 14930352

• 동적 계획법을 사용하지 않은 일반 재귀함수 형태에서는 시간이 훨씬 오래 걸린다.