오늘은 DP(다이나믹 프로그래밍) 유형인 백준 2748번 문제, 피보나치 수 2를 풀어보겠습니다!
< 문제 확인 >
https://www.acmicpc.net/problem/2748
📌 문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
이 문제는 주어진 자연수 n에 대해, n번째 피보나치 수를 구하는 것이다.
피보나치 수열의 대표적인 수학적 정의이고 내용은 아래와 같습니다.
" F(0) = 0, F(1) = 1 / F(n) = F(n-1) + F(n-2) (n ≥ 2) "
피보나치 수열의 구현 방법은 총 2가지로,
바로 재귀적인 방법과 반복적 접근(동적 프로그래밍) 방법으로 나눌 수 있습니다.
자연수 n은 최대 90까지 가능하므로 재귀적인 방법으로 접근할 경우
시간복잡도가 매우 커지므로 더 효율적인 DP 방법으로 구현해보도록 하겠습니다!
✅ DP(동적 프로그래밍)란?
큰 문제를 작은 하위 문제로 나누어 해결하는 알고리즘입니다. 하위 문제들은 한 번만 계산하고,
그 결과를 메모리에 저장해두었다가 필요할 때 재사용하여 중복 계산을 피할 수 있습니다.
이를 통해 시간 복잡도를 줄이고 효율적으로 문제를 해결합니다!
피보나치 수열에서 F(n)을 계산할 때, 이전 두 수 F(n-1)과 F(n-2)를 이용합니다.
이 과정에서 이미 계산된 값을 재사용하므로, 중복 계산을 피할 수 있는 것입니다.
재귀함수로 구현한 기본적인 피보나치 수열은 아래와 같습니다.
def fibonacci(num):
if (num == 1):
return 1
if (num == 0):
return 0
return fibonacci(num-1) + fibonacci(num-2)
이 방법은 똑같은 계산을 여러번 반복하므로 값이 커질수록 정말 비효율적입니다.
2가지 방법의 시간복잡도를 비교해보도록 하겠습니다.
✔️ 가능한 시간복잡도
1) 재귀적인 방법
O(2^n)으로 매우 비효율적이고 n이 커질수록 성능이 급격히 떨어집니다 ㅠㅠ
2) DP(동적 프로그래밍)
O(n)으로 피보나치 수열의 n번째 값을 효율적으로 구할 수 있습니다!
📌 코드 설계하기
- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성
1. 자연수 n을 입력받습니다.
2. 특별한 경우인 n이 0과 1일 때의 값을 처리합니다.
3. 반복적 접근을 통해 피보나치 수열 값을 계산합니다.
4. 계산된 n번째 피보나치 수를 출력합니다.
📌 시도 회차 수정 사항 (Optional)
무문 별하게 “맞았습니다”가 나올 때까지 수정하는 형태의 문제 풀이를 반복하면,
내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.
- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
📌 정답 코드
# 자연수 n 입력
n = int(input())
# 특별한 경우 먼저 처리
if (n == 0): print(0)
elif (n == 1): print(1)
else:
# 초기 피보나치 수 설정
a, b = 0, 1
# F(2)부터 F(n)까지 계산
for _ in range(2, n + 1):
a, b = b, a + b
print(b)
다이나믹 프로그래밍 알고리즘을 활용한 대표적인 유형인 피보나치 수열 문제를 풀어보았습니다.
재귀적인 방법보다 시간복잡도를 훨씬 줄일 수 있었고 이 알고리즘을 잘 활용한다면
문제 풀이에서 많은 이득을 볼 수 있을 것 같습니다 ㅎㅎ

코테 챌린지 3기 파이팅 :)
@why_dev_says_no
'코딩테스트 > 알고리즘' 카테고리의 다른 글
[백준 / python] 1010번 다리 놓기 (0) | 2024.08.23 |
---|---|
[백준 / python] 2775번 부녀회장이 될테야 (0) | 2024.08.22 |
[백준 / python] 1654번 랜선 자르기 (0) | 2024.08.20 |
[백준 / python] 7759번 먹을 것인가 먹힐 것인가 (0) | 2024.08.19 |
[백준 / python] 10816번 숫자 카드 2 (0) | 2024.08.18 |