[알고리즘_Programmers] 7주차 1번 문제 및 풀이

이제 Level 1의 프로그래머스 알고리즘 문제들은 다 풀고, Level 2로 넘어왔다.

 

역시 Level up이 되서 그런지, 문제들이 좀 어려운 편인 것 같다.

 

기존에 알던 방식으로 풀면 런타임 에러...즉, 시간 초과 문제가 발생한다 하하핳...(정말 화가 난다 ㅎ)

 

때문에 7주차 문제들. 즉, Level 2 알고리즘 문제들부터는 1개의 문제씩 풀이를 포스팅하겠다.

 

오늘은 7주차의 첫 번째 문제인 "피보나치 수" 문제에 대한 풀이를 진행하겠다.

 

<문제>

 

<1. 나의 풀이>

 

• 처음엔 아~ 정말 쉬운 문제네! 그냥 재귀 호출 사용하면 되겠다 ^^! 라고 생각했으나...ㅎㅎ 괜히 Level 2 문제가 아니었다.
• 재귀 호출을 사용해서 풀 경우, n이 커지면 시간 복잡도가 엄청나게 커지므로 런타임 에러(시간 초과) 문제가 발생한다.
• 따라서 다른 풀이 방법을 생각해내야만 했다.

 

• 고민해 본 결과, for 문을 사용해서 풀어보면 좋겠다는 생각을 했다.
• 우선 n이 0 이면 0, n이 1 이면 1이라고 처리해주었다.
• n이 2 이상인 경우에는 a = 0, b = 1이라는 초기값을 설정해주고, result라는 변수에 두 값을 합한 값을 넣어주도록 했다.
• 합한 값을 result에 넣어준 후에는 a 를 b로, b를 result 값으로 각각 변경해주었다.

ex) a, b, result 변수에 들어가는 값들이 어떻게 처리되는지를 이해하기 쉽게 표로 정리해 보았다.

a	b	result
0	1	1
1	1	2
1	2	3
2	3	5

 

<2. 다른 사람의 풀이>

 

• 다른 사람들은 어떻게 풀었는지 확인해보았다. 전반적으로 내가 푼 풀이와 유사하나, 코드가 훨씬 더 간결함을 볼 수 있다.
• a, b = b, a + b 이라는 파이썬의 특성(?)을 사용하여 손쉽게 값을 변경해주었다.
• 난 왜 이런 스킬들이 안 떠오르는지 ㅎㅎㅎ...^^

 

다음 문제들은 더 현명하게 잘 풀 수 있기를 바라며...포스팅을 마치겠다!! ^^