자료구조

• Array 순차 자료구조 : 시퀀셜 리스트 메모리상에서 일렬로 나열된 데이터 형
  • 삽입/삭제 : O(N)
  • 탐색 : O(1)
• Linked List 연결 자료구조 : 링크드 리스트 메모리상에선 분산되어있지만 하나의 노드가 다음 노드를 가르키 는 포인트가 있음
  • 삽입/삭제 : O(1)
  • 탐색 : O(N)

스택

• 후입선출 로써 LIFO 이다. 나중에 들어온 것이 제일 먼저 나간다.
  • 삽입/삭제 : O(1)
  • 탐색 : O(1)

큐

• 선입선출 로써 FIFO 이다. 먼저 들어온 것이 제일 먼저 나간다.
  • 삽입/삭제 : O(1)
  • 탐색 : O(N)

트리

• 계층구조로 구성된 자료 구조이며 트리의 모든 노드는 하나의 부모노드를 가진다.
• 부모노드가 없는 최상단 노드를 루트노드, 자식이 하나도 없는 최하단 노드를 리프 노드라고 한다.
  • 삽입/삭제 : O(logN)
  • 탐색 : O(logN)

힙

• 힙은 이진트리의 한 종류로써 두 가지 조건이 성립되는 이진트리를 의미한다.

  1. 완전 이진 트리어야 한다.
  2. 부모 노드와 자식 노드간에 크기 관계가 성립해야 한다.
  • 삽입/삭제 : O(logN)
  • 탐색 : O(logN)

  힙 자료구조의 삽입과 탐색 속도는 O(logN)입니다.

그래프

• 정점과 에지로 이루어진 형태의 자료구조. 에지의 방향성과 존재 유무에 따라 유향 그래프, 무향 그래프로 분리 된다.
• 에지가 가중치를 가지고 있다면 가중치 그래프 라고 부른다.
• 그래프는 행렬과 연결리스트를 활용하여 구현할 수 있는데 행렬의 경우 정점의 존재 여부와 상관없이 항상 N ^ 2의 공간 복잡도를 가진다.

해시

• 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 것. 해시 함수를 정의하면 배열의 인덱스를 원하는 값으로 넣거나 찾을 수 있음.
• 즉, 키를 이용해 값을 바로 찾아낼 수 있음.
  • 삽입/삭제 : O(l1)
  • 탐색 : O(1)