Computer Science and Engineering/Data Structure

배열  자리를 나타내는 인덱스(index)와 동일한 자료형의 데이터 값으로 된 집합이 연속적인 형태로 되어 있는 자료구조이다. 연속적인 형태라는 것은 데이터 값이 메모리에 저장될 때 순차적으로 저장된다는 뜻이다. 이때 순차적으로 붙은 각 번호가 인덱스이다.또한 데이터의 자료형이 모두 동일하기 때문에 특정 값에 접근할 때 그 값의 인덱스를 알 수 있다면 메모리 주소 역시 알 수 있다. 즉 원소들이 연속적으로 배치되어 있기 때문에 각 원소에 접근할 때 시간복잡도가 $ \mathcal{O}(1) $ 인 임의접근(random access)이 가능하다.대부분 언어에서 기본적으로 별도의 라이브러리 없이 지원하며, 인덱스를 통해 배열의 값에 접근할 때 [] 를 주로 사용한다. 또한 대부분의 언어에서 배열 인덱스의 시..

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