피보나치 수열과 DP[백준 피보나치 비스무리한 수열]

🧮 백준 14495번: 피보나치 비스무리한 수열

오늘은 피보나치를 DP로 풀어내는 문제를 풀어볼 거에요.

---

🧩 피보나치 수열?

피보나치 수열이란 첫째, 둘째 항이 1이고 그 뒤의 항은 바로 앞의 두 항의 합인 수열입니다.

F(n): 1, 1, 2, 3, 5, 8, 13, ...

일반적으로 피보나치를 구하는 알고리즘을 코드로 구현할 때는 재귀함수를 사용합니다.

def fivo(n):
    if n <= 1:
        return n
    return fivo(n - 1) + fivo(n - 2)

이렇게 재귀함수로 피보나치 수열을 구할 경우 시간복잡도는 O(2^N) 이 됩니다.

해당 시간복잡도는 O(n^2)보다도, n^3보다도 성능이 좋지 않습니다.

그래서 우리는 이 경우를 피하기 위해, 그리고 DP를 배우기 위해 피보나치를 DP로 구현하게 됩니다.

---

💡 DP(다이나믹 프로그래밍 | 동적 계획법)?

자료들이 생각보다 많은 내용을 담고 있어서 완벽히 이해하기보단,

어느 정도 개념을 이해한 뒤 문제를 풀고 이해에 도움을 주는 방식으로 접근하는게 좋다생각하여 코드를 쓰면서 적겠습니다!

DP란 하나의 큰 문제를 여러 개의 작은 문제로 나누고, 그 결과를 저장하여 큰 문제를 해결할 때 사용하는 알고리즘 설계 기법입니다.

---

📉 재귀 구조 예시

피보나치 수열의 구조를 살펴보면 다음과 같습니다:

식 = f(n) = f(n-1) + f(n-2)
fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) → 1
│   │   │   └── fib(0) → 0
│   │   └── fib(1) → 1
│   └── fib(2)
│       ├── fib(1) → 1
│       └── fib(0) → 0
└── fib(3)
    ├── fib(2)
    │   ├── fib(1) → 1
    │   └── fib(0) → 0
    └── fib(1) → 1

하나의 피보나치 수열의 값을 구하기 위해 하위 피보나치들을 끝없이 호출하고 있습니다.

이 경우, 하위 피보나치에서 구한 값들을 저장해두고 재활용할 수 있습니다.

---

✅ DP로 푸는 코드

a = 10

def fivo(n):
    if n <= 3:
        return 1
    dp = [0] * (n + 1)
    dp[1] = dp[2] = dp[3] = 1  # 초기값 정의

    for i in range(4, n + 1):
        dp[i] = dp[i - 1] + dp[i - 3]  # 바텀업 (점화식)
    return dp[n]

fivo(a)

짠. 뭔가 많아졌고, 재귀가 제거되었습니다.

---

📌 문제의 수열 설명

피보나치 비스무리한 수열은 아래와 같습니다:

f(n) = f(n-1) + f(n-3)
f(1) = f(2) = f(3) = 1

수열을 나열하면:

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...

문제를 보면 피보나치처럼 비스무리ㅣㅣㅣ 한데 조금 다른 수열입니다. (개념은 같습니다)

---

💻 코드 설명

if n <= 3:
    return 1
dp = [0] * (n + 1)

dp[1] = dp[2] = dp[3] = 1  # 초기값 정의

• 문제의 1, 2, 3 항이 1이기 때문에 n이 3이거나 작을 때 1로 조기 return 시켜줍니다.
• n 길이만큼 수를 저장하기 위해 dp 배열을 만들어줍니다.
• 여기서 dp 배열의 index 0번은 버리는 값입니다.

---

🧠 DP 개념 설명

dp 배열을 만들어준 것이 바로 작은 문제의 결과를 저장하기 위한 것입니다.
여기엔 결과 저장을 하는 것에는 두 가지 이름이 존재합니다.

• 메모이제이션 (Memoization)
• 테뷸레이션 (Tabulation)

---

🔁 점화식 및 반복문

for i in range(4, n + 1):
    dp[i] = dp[i - 1] + dp[i - 3]  # 점화식

• 작은 값부터 하나씩 반복문을 돌면서
  f(n) = f(n -1) + f(n - 3) 의 값을 dp 배열의 index 4부터 저장합니다.
  (index 1, 2, 3은 이미 1로 초기화되어 있음)

---

📐 DP 용어 정리

📌 점화식

문제를 풀기 위한 수식입니다.


여기에서는 f(n) = f(n-1) + f(n-3) 이 점화식이 됩니다.

---

🔽 Bottom-UP

• 이름 그대로 아래에서부터 위로 연산값을 누적하는 방식입니다.
• 반복문을 통해 해결하는 방식으로, 저장 방식을 Tabulation 이라고 부릅니다.
• "테이블에 값을 채워나간다" 하여 이런 이름이 붙었습니다.

---

🔼 Top-Down

• 큰 문제에서 작은 문제로 내려가며 해결하는 방식입니다.
• 재귀함수를 통해 구현되며, 이미 계산된 값을 저장하고 재사용합니다.
• 저장 방식을 Memoization 이라고 부릅니다.

---

🔄 Top-Down 코드 예시

def fivo(n, memo={}):
    if n in memo:  # 이미 값이 저장되어 있으면 꺼내서 사용
        return memo[n]

    if n <= 3:
        return 1

    memo[n] = fivo(n - 1, memo) + fivo(n - 3, memo)  # 점화식
    return memo[n]  # 수열의 n번째 값 return