피보나치 함수를 구하는 문제이다 보통 피보나치 수열은 재귀함수를 이용해서 구할 수 있다. def fibo(x): if x == 1 or x == 2: return 1 else: return fibo(x-1) + fibo(x-2) 이런 식으로 구할 수 있는데 문제는 숫자가 조금만 커지게되면 연산횟수가 급격하게 증가하고 그에 따라서 속도도 엄청 느려지게 된다. 이런 문제를 메모이제이션(재귀함수이용) 또는 반복문을 이용해서 해결할 수 있다. 메모이제이션은 이미 한번 연산을 했던 값은 따로 저장해뒀다가 필요할때마다 찾아서 쓴다는 아이디어다. 말 그대로 따로 메모해둔다고 생각하면 된다. 반복문을 이용하는 방법은 작은 문제부터 하나하나씩 풀어나가는 방법이다. 결론적으로는 선형시간의 시간복잡도를 갖는다. 코드로 살펴..