알고리즘

재귀 (Recursion) 재귀함수는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 가장 대표적 예가 팩토리얼, 피보나치 수열이다. 팩토리얼은 아래와 같이 정의된다.$$ n ! = \begin{cases} 1 & \quad n = 0 \\ n \times (n-1) ! & \quad n \geq 1 \end{cases} $$ $ n ! $ 을 계산하기 위해 $ (n-1) ! $ 을 계산하는 것이다. 결국 팩토리얼 계산을 위해 다시 팩토리얼을 계산해야 한다.피보나치 수열 역시 아래와 같이 정의되기 때문에 재귀함수라 할 수 있다.$$ F_0 = 0, \quad F_1 = 1, \quad F_{n+2} = F_{n+1} + F_{n} $$$ F_{n+2} $ 를 계산하기 위해 $ F_{n+1} $ 과 $ F..

자료구조와 알고리즘 자료구조는 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장에 관한 것이다. 예를 들어, 선입선출 방식이 필요한 데이터가 있다면 이러한 데이터를 효율적으로 관리하기 위해 큐(queue)라는 선입선출형 자료구조를 활용할 수 있다.알고리즘은 문제를 해결하는 절차나 방법을 자세히 설명하는 과정이다. 자연어, 흐름도(flow chart), 슈도코드(pseudo-code), 프로그래밍 언어 등으로 표현할 수 있다. 효율적인 알고리즘을 설계하기 위해서는 시간 복잡도와 공간 복잡도 등을 고려해야 한다.프로그램은 이러한 자료구조(혹은 자료)와 알고리즘이 결합된 결과물이다. 예를 들어 계산기 프로그램을 만든다고 가정하자. 계산기 프로그램을 개발하기 위해서는 우선 계산에 필요한 데이터 ..

시간 복잡도 (Time Complexity) 복잡도란 알고리즘이 얼마나 많은 자원을 소비하는지 나타낸다. 같은 동작을 할 때 적은 자원을 소비하는 알고리즘이 성능이 좋은 알고리즘이므로 복잡도는 알고리즘의 성능, 효율성을 나타내는 척도이다.복잡도는 시간 복잡도와 공간 복잡도로 나뉘는데, 시간 복잡도는 알고리즘의 연산 횟수를 말하고, 공간 복잡도는 알고리즘을 위한 메모리 공간을 말한다. 시간 복잡도가 커진다는 것은 연산 횟수가 늘어난다는 것이고, 공간 복잡도가 커진다는 것은 필요한 메모리 공간이 많아진다는 것이다.컴퓨팅 메모리가 부족한 상황이 아니라면 주로 신경써야 할 것은 시간 복잡도이다. 시간 복잡도를 나타낼 때는 다양한 표기법이 사용되는데 주로 사용되는 것이 빅오 표기법이다. 빅오 표기법 빅오 표기법은..