윈디개 님의 블로그

[알고리즘 분석] - 피보나치

1. 피보나치 수열- 피보나치 수열알고리즘 측면에서 피보나치 수열을 들여다 보기 전에, 수학에서의 피보나치 수열을 정의하려고 한다. 피보나치 수열은 점화식으로 표현되는데 점화식은 다음과 같다.위 그림과 같이 피보나치 수열을 정의하면, F2부터는 그 전의 두항의 합이다. - 피보나치 수열_Python 그럼 위 피보나치 수열을 코드로 작성하면 어떻게 될까? 파이썬으로 나타내보자.def fib(n): if n == 0: return 0 if n == 1: return 1 else return fib(n-1)+fib(n-2) 위와 같이 파이썬 프로그램으로는 간단하게 재귀적 호출로 나타낼 수 있다. 이 코드로 fib(10)을 출력하면 fib(10) = 55라는..

[알고리즘 분석] - 수도코드 및 시간 복잡도

1. 알고리즘 분석 프롤로그- 수도코드(pesudo code) 프로그램을 작성할 때 수도코드로 우리가 작성하는 이유는 무엇일까? 이런 것까지 정리해야되나 싶지만 그래도 이유를 알고 나면 다음에 수도 코드에 대한 거부감은 없을 것 같으므로 정리는 해두려고 한다. 수도 코드에 대해 알아보자. 수도 코드는 알고리즘을 프로그래밍 언어로 구현할 때, 알고리즘의 흐름을 정리하기 위해, 언어 자체로 작성하기 보다, 사람이 작성할 때 조금 더 편한 쪽으로 작성한 코드이다. 그렇다고 개발자에 의해 막 작성된 코드는 아니고, C언어의 if, for 문 등 기본적인 문법자체는 지키면서 작성된 코드이다. 다음은 수도 코드의 장점이다.알고리즘 분석 및 수정 시 편리하다.유지 보수에 유리하다.협업 시 수도 코드를 보고 의견 ..