[백준][동적 계획법 1] No.24416_알고리즘 수업 - 피보나치 수 1 01

 

24416번: 알고리즘 수업 - 피보나치 수 1

 

무작위로 문제를 푸는 방법도 재미있고 흥미로운 방법이지만,

내 실력의 수준을 알고 높여가기 위해서는 내가 얼마나 알고 어디까지 구현할 수 있는지 알아야 한다.

그래서 전부터 '단계별로 풀어보기'를 진행하고 있었다.

 

'브루트 포스'와 '백트래킹'의 단계도 중요해서 나중에 작성하겠지만,

지금 동적 계획법(다이나믹 프로그래밍)을 4문제 남겨두고 느낀 점이 있다.

 

'여러 가지 알고리즘을 제대로 파악하고 이해하고 작성할 줄 알아야 하고, 정말 중요하구나'

정렬, 브루트 포스, 백트래킹, 동적 계획법, 그리디, DFS, BFS, 탐색에 대해서는 전부 다 작성해보고자 한다.

 

본론으로 돌아와서 문제를 보자.

위에 있는 코드는 단순 재귀를 이용한 피보나치 수 의사 코드이고,

아래에 있는 코드는 다이나믹 프로그래밍(이하 DP)을 이용한 피보나치 수 의사 코드이다.

 

DP에 대한 자세한 설명은 따로 글을 작성한다.

알고리즘 - 동적 계획법(Dynamic Programming)

 

기본적인 피보나치 수는 1 1 2 3 5 8 13 21 ... 과 같이 앞의 두 수를 더하여 새로운 수를 얻는 규칙이다.

이때 가장 처음 수까지 연산을 계속하는 것이 아니라, 위의 값들을 배열에 저장한다.

그리고 배열에서 값을 꺼내주기만 하면 된다.

 

쉽게 풀어서 설명하자면, 8번 피보나치 수를 얻고자 한다고 가정해보자. (첫 번째 숫자와 두 번째 숫자는 1로 둠)

8번 수를 구하기 위해 6, 7번 수를 구해야 한다.

6번 수를 구하기 위해서는 4, 5번을. 7번 수를 구하기 위해서는 5, 6번 수를.

이런 식으로 모든 수가 1과 2로 표현이 될 때까지 연산을 반복한다.

N번째 숫자를 구할 때, N이 16만 돼도 연산 횟수가 1000번에 가까워진다.

 

그게 아니라 이번에는 DP를 이용해서 연산해보자. (마찬가지로 첫 번째와 두 번째는 1이다.)

dp = [0, 1, 1]이라는 형태의 배열을 선언한다.

(이때 dp = [1, 1]의 형태로 선언해도 상관없지만,

index(1)을 첫 번째 수로 두어서 쉽게 생각하려고 앞에 의미없는 0을 추가해줬다.)

 

N이라는 숫자는 N-1과 N-2를 더한 값이다.

이걸 반복문으로 만들어주면 아래와 같은 점화식을 가진다.

# 의사 코드
for N in range(3, NUM):
    dp[N] = dp[N-1] + dp[N-2]

 

DP에서 중요한 것은 반복하는 작은 문제들을 저장해두었다가 재활용하는 것이다.

 

그리고 고난도 DP일수록 배열을 여러 개 선언해야 하는 경우가 생긴다.

이때 연산하는 배열이 맞는지, 배열인지( "[ ]" ) 함수인지( "( )" )를 정확하게 구분해서 사용해야 한다.

왜냐하면 내가 그런 실수를 저질렀다...

 

제출 번호 47573217의 아래 제출이 첫 번째 풀이, 제출 번호 47574226의 위 제출이 두 번째 풀이이다.

메모리와 코드 길이는 크게 차이나지 않지만, 시간에서 엄청난 차이가 나는데 그건 밑에서 후술한다.

 

# ---------- 첫 번째 풀이 ----------

# ---------- Function ----------
def fibonacci_bruteForce(N):
    
    if N == 1 or N == 2:
        return 1
    
    return fibonacci_bruteForce(N-1) + fibonacci_bruteForce(N-2)

def fibonacci_dynamic(N):
    global dynamic_cnt
    
    if N == 1 or N ==2:
        dynamic_cnt += 1
        return 1
    
    if dynamic_list[N] != 0:
        dynamic_cnt += 1
        return dynamic_list[N]
    
    dynamic_list[N] = fibonacci_dynamic(N-1) + fibonacci_dynamic(N-2)
    
    return dynamic_cnt

# ---------- Main ----------
N = int(input())

bruteForce_cnt = 0
dynamic_cnt = 0
bruteForce_list = [0] * (N+1)
dynamic_list = [0] * (N+1)

print(fibonacci_bruteForce(N), fibonacci_dynamic(N)-1)
# 왜 fibonacci_dynamic에서 1을 빼야 정답과 같은지는 의문

'''
N:	1  2  3  4  5  6   7   8   9  10  11   12   13   14   15   16 
[N]:	1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
'''

첫 번째로 제출한 코드를 정말 그대로 가져왔다.

print 아래 주석을 보면 왜 내가 구한 답에서 1을 빼야 정답이 되는지 의문도 고스란히 적혀있다.

내 코드에서 배열인지( "[ ]" ) 함수인지( "( )" )를 정확하게 구분해서 사용해야 하지 않은 예시이다.

 

위에서 말했듯, dp를 [1, 1] (여기서는 [0, 1, 1])로 초기화하고 dp[N] = dp[N-1] + dp[N-2]를 구해야 했다.

근데 자세히 보면 대괄호가 아니라 소괄호이다. 여기서 불필요한 연산이 한 번 더 들어간 것이다.

시간도 오래 걸리고 오류도 잡아야 해서 두 번째 풀이를 작성했다.

 

# ---------- 두 번째 풀이 ----------

# ---------- Function ----------
def fibonacci(N):
    global cnt
    
    fibonacci_list[1], fibonacci_list[2] = 1, 1
    
    for i in range(3, N+1):
        cnt += 1
        fibonacci_list[i] = fibonacci_list[i-1] + fibonacci_list[i-2]
    
    return fibonacci_list[N]

# ---------- Main ----------
N = int(input())

cnt = 0
fibonacci_list = [0] * (N+1)

fibonacci(N)
print(fibonacci_list[N], cnt)	# fibonacci(N) 값은 실행횟수와 동일하다

# ---------- Comment ----------
'''
N:	1  2  3  4  5  6   7   8   9  10  11   12   13   14   15   16 
[N]:	1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
'''

우선 시간이 현저하게 줄은 이유는 기존의 피보나치 연산 과정이 빠졌다.

계산을 하다보니 N번째 피보나치 연산 횟수는 N번쨰 피보나치 수와 같다는 사실을 알았다.

이유는 각자 생각해보자.

 

그리고 지금 보니 함수에서 global이라는 걸 사용해 변수 값을 변경하고 있다.

(함수 외부에 있는 변수를, 함수 내부에서도 사용할 수 있는 전역 변수로 바꿔주는 예약어이다.)

fibonacci(N, cnt) 이렇게 받으면 되지만 뭔가 지저분해지는 기분이 들어서 자꾸 피하게 된다.

함수도 몇 개 없고 간단한 코드이기에, 그리고 나에게 있어서는 직관적이라 저렇게 자주 사용하지만...

저러면 강한 연결이 되어버리니 지양하는 쪽으로 코드를 짜야겠다.