자료 구조

복잡도

시간 복잡도

• 빅오 표기법 ('O()')

공간 복잡도

• 자원 공간의 양 (ex. a= [3] )

선형 자료 구조

연결리스트

• 데이터를 감싼 노드를 포인터로 연결하여 공간적인 효율성을 극대화 시킨 자료구조
• 삽입, 삭제 O(1) , 탐색 O(n)

배열

• 같은 타입의 변수로 이루어짐
• 크기가 정해져 있고, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
• 삽입, 삭제 O(n) , 탐색 O(1)
• 랜덤 접근, 순차 접근
• 배열, 연결리스트 비교
  • 배열 - 상자를 순서대로 나열한 데이터 구조기 때문에 몇번째 상자인지만 알면 바로 요소를 가져올 수있음
  • 연결리스트 - 상자를 선으로 연결한 형태의 데이터 구조기 때문에 요소를 알기 위해서는 하나씩 찾아봐야함.

벡터

• 동적으로 요소를 할당할 수 있는 동적 배열
• 컴파일 시점에 개수를 모를경우 사용
• 중복 허용, 순서가 있으며 랜덤 접근이 가능
• 탐색과 맨 뒤의 요소를 삭제하거나 삽입할 경우 O(1)
• 맨 뒤나 맨앞이 아닌 요소를 삭제하고 삽입할 경우 O(n)

스택

• LIFO(Last In First Out)
• 재귀 함수
• 웹 브라우저 방문 기록 등에 쓰임
• 삽입 삭제 O(1), 탐색 O(n)

큐

• FIFO(First In First Out)
• CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비우선탐색, 캐시 등 사용
• 삽입 삭제 O(1), 탐색 O(n)

비선형 자료구조

그래프

• 정점과 간선으로 이루어진 자료구조
• 가중치 - 간선과 정점 사이에 드는 비용

트리

• 그래프의 일종이며 부모와 자식 계층 구조
• 간선 수 = 노드수 - 1
• 루트노드 - 가장 위에 있는 노드
• 내부 노드 - 루트 노드와 리프노드 사이에 있는 노드
• 리프 노드 - 맨 마지막에 위치한 노드
• 이진트리
  • 자식노드의 수가 2개이하인 트리
  • 정이진 트리 - 자식노드가 0 또는 두개인 이진트리
  • 완전 이진 트리 - 마지막 레벨을 제외한 레벨이 모두 채워져 있고 마지막 레벨에서 왼쪽부터 채워져야 함
  • 변질 이진 트리 - 자식노드가 하나씩만 있는 트리
  • 포화 이진 트리 - 모든 노드가 꽉 차 있는 트리
  • 균형 이진 트리 - 왼쪽노드와 오른쪽 노드의 높이 차이가 1 이하인 이진트리
• 이진 탐색 트리
  • 노드의 왼쪽은 노드의 값보다 작고, 노드의 오른쪽은 노드의 값보다 높은 값이 들어있는 트리
  • 탐색시 O(logn) 이지만 최악의 경우(선형적 - 한쪽으로 쏠리는 경우) O(n) 걸림
• AVL 트리
  • 왼쪽과 오른쪽의 균형을 맞추기 위한 이진 트리
  • 탐색, 삽입, 삭제 O(logn)
• 레드 블랙 트리
  • 각 노드에 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하여 삽입, 삭제에도 트리가 균형을 이루도록 만듦
  • 탐색, 삽입, 삭제 O(logn)

힙

• 완전 이진트리 기반 자료구조
• 최소 힙 - 루트 노드에 있는 키는 모든 자식에 있는 키중에서 가장 큰 값, 각 노드와 자식노드 간에도 같은 규칙이 이루어져야함
• 최대 힙 - 루트 노드에 있는 키는 모든 자식에 있는 키중에서 가장 작은 값, 각 노드와 자식노드 간에도 같은 규칙이 이루어져야함
• 최대 힙 삽입시 마지막 노드에 삽입후 부모 노드들과 크기를 비교하며 자기 자리를 찾아감
• 최대 힙 삭제시에는 루트노드를 삭제하고 마지막 노드가 최대 값이기 때문에 루트 노드 자리에 마지막 노드 값을 넣음

우선순위 큐

• 대기열에서 우선순위가 높은 요소가 먼저 제공되는 힙 기반 자료 구조(Dequeue())

맵

• 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 래드 블랙트리 기반으로 형성된 자료구조
• 해시테이블 구현시 사용(정렬 X)

set

• 중복된 값 없이 저장하는 자료구조

해시테이블

• 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블
• 삽입, 삭제, 탐색 O(1)