[til] 알고리즘 백준 14495

🧑‍💻 오늘의 문제: 피보나치 비스무리한 수열

• 출처: 백준 온라인 저지 (BOJ)

• 문제 요약:
  피보나치 비스무리한 수열을 다음과 같이 정의한다.

  f(n) = f(n-1) + f(n-3)
  단, 초기값은 f(1) = f(2) = f(3) = 1 이다.

  자연수 n이 주어졌을 때, 이 수열의 n번째 수를 구하는 문제이다.

📌 풀이 과정

• 수열을 저장할 배열을 선언하고 초기값을 미리 채워준다.

• 반복문을 사용하여 4번째 수부터 n번째 수까지 계산하여 배열에 저장한다.

• 마지막으로 배열의 n번째 값을 출력한다.

🖥️ 내가 작성한 코드

python복사편집import sys

n = int(sys.stdin.readline())

fibonacci_arr = [1, 1, 1]
if n > 3:
    for i in range(3, n):
        fibonacci_num = fibonacci_arr[i-1] + fibonacci_arr[i-3]
        fibonacci_arr.append(fibonacci_num)

print(fibonacci_arr[n-1])

💡 문제 해결 방법과 복기

• 기본적인 DP(동적 프로그래밍) 유형의 문제였다.

• 점화식 그대로 코드를 작성했고, 특별히 어려운 부분은 없었다.

• 메모리를 조금 더 절약하고 싶다면 배열 대신 변수 몇 개만 써서 공간을 최적화할 수도 있을 것 같다.

---

🔍 추가적으로 찾아본 더 좋은 풀이 방법

다른 사람들의 풀이를 참고해보니, 더 효율적인 메모리 관리를 위해 배열을 쓰지 않고 변수 몇 개로만 관리하는 방법이 있었다.
왜냐하면 피보나치 수열과 비슷하게 특정 인덱스만 기억하면 되는 문제라서 배열 전체를 저장하지 않아도 되기 때문이다.

최적화된 코드 예시

python복사편집import sys

n = int(sys.stdin.readline())

a, b, c = 1, 1, 1
for _ in range(4, n + 1):
    a, b, c = b, c, a + c

print(c)

이 코드의 장점:

• 배열을 사용하지 않아 공간복잡도 측면에서 효율적이다.

• 간단한 변수만을 사용하므로 메모리 사용량이 적다.

---

✨ 느낀점 & 앞으로의 계획

• 단순히 문제를 해결하는 것에서 그치지 않고, 다른 사람들의 풀이를 찾아보며 효율적이고 간결한 코드를 배우는 습관이 중요하다고 느꼈다.

• 앞으로 하루 하나씩 꾸준히 알고리즘 문제를 풀면서, 문제 풀이 실력뿐 아니라 다양한 최적화 테크닉도 함께 익혀야겠다.