[알고리즘] 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)

• 선형 자료구조

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

2.1.1 스택 구현

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

2.2 큐(Quque)

• 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를 추가한다고 하면.

–4추가

4랑 7비교 4랑 7변경

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

2.4.1 힙의 삽입의 시간복잡도

완전 이진트리의 높이

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

2^n-1

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