프로그래머스 - 피보나치 수 java :: 모듈로 연산

문제

코딩테스트 연습 - 피보나치 수 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

풀이

💣시도1: 재귀함수

보통 피보나치는 재귀로 풀면 쉽습니다. 단, 재귀함수는 연산해야 할 양이 많아지면 차지하는 메모리의 양도 많아지고 처리속도의 효율도 매우 좋지 않아요. n은 최대 10만까지 입력이 가능하므로 재귀로 푸는 방법은 좋지 않은 방법입니다.

(사실 저도 처음엔 재귀로 풀었다가 시간초과 나왔습니다.)

 

💣시도2: 반복문

재귀룰 포기하고 반복문으로 문제를 풀었습니다만... 문제는 7~14번이 계속 오류가 났어요.

원인은 바로 눈치챘어요. 정확히 fibo(47) -> fibo(48)로 넘어갈 때 피보나치 수가 int 자료형의 범위값을 넘어가요.

 

💣시도3: 반복문 + long 타입으로 계산

int 자료형의 범위를 넘어가니 long으로 해봤는데 바보같은 짓이죠...

48에서 int형 범위를 넘어갔는데 long으로 될 거라고 생각하다니... 무려 최대 인풋이 10만인데...ㅋㅋㅋ

 

📌힌트

3번째 시도까지 해보고 일반적인 계산으로는 절대 풀 수 없다는 걸 알았어요.

힌트는 1234567로 나눈 나머지에 있었어요. 정답은 모듈로 사칙연산을 활용하는 방법에 있었어요.

🎈모듈로 사칙연산 (덧셈) : \( (A + B) \% m = (( A \% m ) + ( B \% m)) \% m \)

모듈로에 대한 이해를 위해 제가 참고했던 페이지들은 하단에 링크를 남겨두었으니 보시면 이해하는 데 도움이 될 거예요.

 

 

📝풀이

public int solution(int n) {
	int count=2, mod=1234567;
	int f1=0, f2=1;
	
	while(n > count) {
		int temp = f2;
		f2 = ( (f1%mod) + (f2%mod) ) % mod;
		f1 = temp;
		count++;
	}
	
	return (f1+f2) % mod;
}

 

⚡테스트 케이스 처리속도: 0.01ms ~ 2.23ms

 

 

References

🎈모듈로 연산이란?

모듈로 연산이란? (개념 이해하기) | 암호학이란? | Khan Academy

모듈로 연산이란? (개념 이해하기) | 암호학이란? | Khan Academy

 

🎈모듈러 연산의 성질과 증명

모듈러 연산의 성질과 증명 :: 코린이의 얕은 블로그 (tistory.com)

모듈러 연산의 성질과 증명

 

🎈모듈로 연산

모듈로 연산(modulo operation) (tistory.com)

모듈로 연산(modulo operation)