RAEDME

복잡도

시간 복잡도

• 코드의 입력에 따라 실행되는데 걸리는 시간을 의미한다.

공간 복잡도

• 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 의미한다.

• 정적 변수로 선언돈 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함된다.

선형 자료 구조

• 데이터를 감싼 노드를 포인터로 연결해서 공간적 효율성을 극대화 시켰다.

• 삽입과 삭제는 O(1)이 걸리며 탐색에는 O(n)이 걸린다.

• 구성요소가 일렬로 나열되어 있다.

종류

연결리스트

• 싱글 연결 리스트 : next 포인터만 가진다.

• 이중 연결 리스트 : next와 prev 포인터를 가진다.

• 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가르킨다.

배열

• 같은 타입의 변수들로 이뤄져있고 크기가 정해져 있으며, 인접한 위치에 있는 데이터를 모아놓은 집합이다.

랜덤 접근과 순차적 접근

• 직접 접근이라고 하는 랜덤 접근은 동일한 시간에 배열과 같은 순차적인 데이터가 있을때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능이다.

백터

• 백터는 동적으로 요소를 할당할 수 있는 동적 배열이다. 컴파일 시점에 개수를 모른다면 백터를 사용해야 한다.

• 삽입 시 공간을 만들어야 해 배열보다 좀 더 걸릴 수 있다.

스택

• 가장 마지막으로 들어간 데이터가 가장 첫 번쨰로 나오는 성질을 가진 자료구조이다.

큐

• 먼저 집어넣은 데이터가 먼저 나오는 성질이다.

비선형 자료구조

• 일렬로 나열하지 않고 순서나 관계가 복잡한 구조를 말한다.

이진 트리

• 자식의 노드 수가 두 개 이하인 트리를 의미한다.

이진 탐색 트리

• 작은것은 왼쪽 큰것은 오른쪽으로 정착한다.

• 그렇기 떄문에 O(log n)의 복잡도를 가지나 최악의 경우 O(n)을 가지게 된다.

AVL 트리

• 이잔 탐색 트리의 최악의 경우를 방지하기 위해 항상 균형을 잡게 하도록 설정하는 구조이다.

레드 블랙 트리

• 루트 노드를 레드로 정하고 자식은 블랙으로 설정해 만드는 트리이다.

힙

• 최대 힙 : 새로운 값이 루트보다 크면 루트노드와 교환한다.

• 최소 힙 : 새로운 값이 루트보다 작으면 루트노드와 교환한다.

유선 순위 큐

• 힙을 기반으로 우선순위 높은 것이 먼저 제공 된다.