가장 간단하지만 중요한
피보나치 수열은 알고리즘 수련을 할 때 가장 기초적으로 시도해보는 것들 중 하나이다. 내용은 다음과 같다.
첫째 항과 둘째 항이 각각 1이고 이후 n번째 항은 n-1번째 항과 n-2번째 항의 합인 수열을 피보나치 수열이라고 한다.
n을 입력했을 때, 이 수열의 n번째 항이 출력되도록 하시오.
쉽게 말해서, 첫번째 수와 두번째 수를 1이라고 두고, 그 다음부터는 전 두개의 수를 합한 것이다. 그래서 수열은
1: 1
2: 1
3: 2 (1+1)
4: 3 (1+2)
5: 5 (2+3)
6: 8 (3+5)
7: 13 (5+8)
8: 21 (8+13)
9: 34 (13+21)
10: 55 (21+34)
...
이 된다. 너무 쉬운 문제 아닌가? 이걸 못 맞추는 바보가 있을까. 솔직히 이거 할줄 모르면 어디가서 코딩할 줄 안다고 하고 다니면 안되지.
고등학교 공학 동아리에 지원했다. 서류 지원은 무난하게 합격, 코로나 시국으로 인해 원격으로 진행되는 원격 면접만 남아 있었다. 질문들은 모두 내 포부를 잘 드러내게 대답했다. 이어서 찾아온 간단한 코딩 테스트... 정올을 응시했었던 경험을 살려 빈 A4지를 책상 위에 올려두고 문제를 기다렸다.
피보나치 수열. 분명 옛날에 풀어봤던 문제다. '피보나치 수열'이라는 단어를 본 순간 안심했다. 속으로 웃으면서 다시 그 때의 기억을 되살려보았다. 옛날에 어떻게 풀었더라...
...옛날에 어떻게 풀었더라?? 기억이 나지 않는다.
어쩔 수 없이 문제를 다시 읽어본다. 첫 번째 수와 두 번째 수의 '합'. 합? 예제를 보자. 10을 넣었을때 55가 나온다... 1부터 10까지 더하면 55인데? 어, 첫째항이 또 1이네. 그럼 진짜 다 더하는 누적합 문제인가? 한번 해 보자.
오케이, 코드 다 짰고. 근데 왜 2를 넣었을때 1이 나와야 하는 것이냐. 음... 음? 2번째 항도 1이네? 뭐지... 아, 1씩 늘어니자 않고 뒤의 두개만큼 늘어나는구나. 그럼 for문을 돌며 1부터 10까지 더하는게 아니라 뒤의 두 항을 더한 값만큼 늘어나게 하면... 그러면 10을 넣었을 때 147이 나오는데? 뭐지? (당황)
그렇게 시간이 다 되고, 쉽다고 생각했던 문제는 끝내 풀지 못했다. 줌에서 나오자마자 나오는 헛웃음.
내가 왜 이걸 못풀었을까? 면접이 끝나자마자 문제를 다시 한번 들여다보았다.
...아, 수열의 합이 아니라 n번째 항을 구하는 것이었구나. 이 멍청이.
이 레포지토리는 현타올때마다 와서 피보나치 수열 코드 짜고 초심 되찾는 용도로 사용됩니다.
- 면접에서 짰던 멍청이 코드 0_stupid_wrong_fibonacci.c
- 면접 끝나고 5분만에 짠 정답 코드 1_after_five_minutes.c
- 예습의 단점을 진심으로 익힌 정보 시간에 짠 코드 2_boring_info.py
- 정보 시간에 배운 엑셀 상대 참조 실습 3_excel_relevant.xlsx
- 파이썬 튜플은 갓이야! 4_god_tuple.py
...그래서 동아리는 어떻게 되었냐고요? 다행히 붙었어요! 자소서를 잘썼나봐요 😊 뽑아주신 선배님들 감사합니당 :)