[알고리즘] 6. 자료구조

1. 자료구조 기본

1.1 컴퓨터 기본 커리큘럽

1.1.1 기본언어

1.1.2 자료구조

1.1.3 알고리즘

1.2 자료구조란?

데이터를 담는 구조

1.3 기본 자료 구조

1.3.1 변수

  • int x=4;

1.3.2 배열

  • int[] arr={0,1,2};
  • 장점: arr[i]번째 수를 바로 일 수 있음.
  • 딘잠: 데이터 넣고 빼기가 힘듬(배열 앞뒤로 다 이동시키고 삽입)

    1.3.3 링크드 리스트

  • 앞의 값이 다음 값을 알고있음
  • 장점: 데이터 넣고 빼기 용이
  • x[i]번째 값 알기 어려움(처음부터 탐색)

2. 기초 자료구조

자료구조가 설계된 목적을 이해해야함

  • 스택
  • 트리
  • 그래프

2.1 스택(Stack)

  • 선형 자료구조
in/out
  • LIFO(Last in first out)
  • push(), .pop(),
  • 스택 오버플로우란 push()할때 할당된 공간이 다 차서 넘치는것
  • 스택언더플로우란 공간에 데이터가 하나도 없을때 pop()하는것

2.1.1 스택 구현

  • push()
  • pop()
  • top()
  • size()

2.2 큐(Quque)

<-out <- in
  • FIFO(First in first out)
  • push(), .pop(),
  • 스택 오버플로우란 push()할때 할당된 공간이 다 차서 넘치는것
  • 스택언더플로우란 공간에 데이터가 하나도 없을때 pop()하는것

  • 큐의 문제점 : 공간활용이 안좋음 >> 해결 원형큐

2.2.1 원형큐

배열 공간을 원형으로 만들어서 함

2.2.2 큐 활용문제 예시

괄호가 올바른지 판단하기

2.3 트리(Three)

  • root
  • 노드(정점)
  • 간선
  • 트리의 재귀적성질

2.3.1 트리순회

  • 전위순회 : root-Left-Right
  • 중위순회 : Left-Root-Right
  • 후위순회 : Left-Right-Root

2.4 우선순의 큐

  • 큐에 넣고 우선순위가 높은것 순으로 뽑기
  • 배열을 이용한 우선순의 큐는 뽑고 다시채워야 해서 O(n^2)걸림->느림

2.4 힙(Heap)

부모값이 항상 자식보다 작은 이진트리

아래 트리에 4를 추가한다고 하면.

3
5 7
23 7 9 null

–4추가

3
5 7
23 7 9 4

4랑 7비교 4랑 7변경

3
5 4
23 7 9 7

4랑 3비교 유지 > 정렬끝!!

3
5 4
23 7 9 7

2.4.1 힙의 삽입의 시간복잡도

완전 이진트리의 높이

노드수 높이
1 1
2 2
3 2
4 3
5 3
6 3
7 3
8 4

노드의 개수가 n개일때의 높이 = logn

2^n-1

  • 힙 값 삽입의 시간복잡도=> O(logn)
  • 힙 값 삭제의 시간복잡도 => O(logn)

댓글

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×