자료 구조

자료 구조(data structure)는 컴퓨터에서 처리할 자료를 효율적으로 관리하고 구조화시키기 위한 학문이다.

자료 구조의 유형

• 선형구조

선형구조는 순차 리스트 또는 선형 리스트라고 부르며, 데이터를 저장할 때 연속적인 저장공간에 배정하는 자료구조로서 배열, 큐, 스택, 데크, 연결리스트 5가지 자료구조가 있다.

• 비선형구조

비선형구조는 그래프와 트리가 있다.

• 정렬

정렬(sort)이란 순서없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것이다. 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘으로, 삽입 정렬, 쉘 정렬, 선택 정렬, 버블 정렬, 퀵/병합 정렬, 히프 정렬, 기수 정렬, 외부 정렬 등이 있다.

• 배열

배열은 연속적인 기억 공간에 배정하며 각 요소들은 동일한 데이터 타입으로 <인덱스, 값>의 쌍으로 표현한다.

• 선형 리스트

선형 리스트는 물리적으로 일렬로 이루어진 자료구조이다. 배열을 이용하여 구현된다.

• 연결 리스트

연결 리스트(linked list)라고 부른다.

다중 연결 리스트는 각 노드들이 링크에 대한 필드가 2개 이상인 구조이다.

단순 연결 원형 리스트 마지막 노드 ptr이 첫 번째 노드를 가리키도록 연결한 리스트 형태이다. 마지막 노드에서 첫 번째 노드로 연결하는 방식이다.

이중 연결 원형 리스트는 새로운 노드를 어떤 노드의 앞에 삽입이나 삭제가 불가능한 단순 연결 리스트의 단점을 보완하기 위해 제안된 리스트이다.

• 스택

주기억장치에서 연속적인 공간을 배정하여 데이터를 저장하고 검색하여 사용할 수 있도록 제약을 가진 순서 리스트와 같은 자료구조이다.

• 자료 구조의 정의

자료구조는 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계이다.

자료 구조의 분류

자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 기억 공간의 크기에 따라 여러 가지 종류의 자료구조 중 하나를 선택할 수 있다.

자료구조의 종류로는 자료형에 따라 분류하는 단순 구조와 자료 간 관계가 1대1인 선형 구조, 1대다 혹은 다대다 구조인 비선형 구조, 마지막으로 파일 구조가 있다.

구현에 따라 배열, 튜플, 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 환형 이중 연결 리스트, 해시 테이블로 구분된다.

형태에 따라 선형 구조와 비선형 구조로 구분되며, 선형 구조에는 스택, 큐, 덱이 있고 비선형 구조에는 그래프와 트리가 있다.

시간 복잡도

컴퓨터 과학에서 알고리즘의 시간 복잡도는 입력을 나타내는 문자열 길이의 함수로서 알고리즘을 취해 시간을 정량화하는 것이다.

알고리즘의 시간 복잡도는 계수와 낮은 차수의 차항을 제외시키는 빅-오 표기법을 사용하여 나타낸다.

시간 복잡도는 기본적인 연산을 수행하는 데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는

알고리즘의 수행 시간은 동일 크기의 다양한 입력에 따라 달라질 수 있기 때문에, 최악의 시간 복잡도의 알고리즘 시간을 T(n)이라 했을 때, 이것은 크기 n의 모든 입력에 대해 걸리는 최대의 시간으로 정의할 수 있다.