[250505 TIL] 코딩테스트 피보나치 수, 카펫

1️⃣코딩테스트

[피보나치 수]

https://github.com/swehio/Baekjoon/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/12945.%E2%80%85%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%E2%80%85%EC%88%98

🔹피보나치 수를 푸는 두가지 방법

1. 재귀함수

점화식 F(n) = F(n-2) + F(n-1)을 이용한 재귀 호출 방법

n이 50 이상일 때 시간 초과 문제 발생

 

2. 반복문

for문을 이용한 동적 계획법

메모이제이션을 활용해 재귀 호출 횟수 감소 가능

❓메모이제이션
계산한 값을 저장해두었다가 쓸 일이 있을 때 활용
저장 자료구조로는 배열 추천 

🔹피보나치 수가 매우 커질 때

n번째 피보나치 수의 n이 매우 크다면 자료형의 범위를 넘어가 오버플로우가 발생할 수 있다.

→ 모든 단계에서 % 연산을 사용하여 모든 연산에서 오버플로우가 일어나지 않게 해주어야 함

💡나머지 연산의 성질
(a + b) % m = ((a % m) + (b % m)) % m

이를 문제에 적용하면
F(n) % m = (F(n-1) + F(n-2)) % m = (F(n-1) % m + F(n-2) % m) % m

 

[카펫]

https://github.com/swehio/Baekjoon/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/42842.%E2%80%85%EC%B9%B4%ED%8E%AB