알고리즘 강의 2

지난 강의 정리

• 스택
• 큐
-> 쉬우니까 넘어감

그래프

• 유향/무향
• cycle
• 연결형/비연결형
• 표현방법
- 인접 행렬/인접 리스트

트리

• 종류
- 일반트리/이진트리/완전이진트리/red-black 트리/이진검색트리 ...

• 표현

• 인접행렬
• 인접리스트

• 힙(Heap)
• 순회(pre/post/...)

STL(Standard Template Library)

• #include <stack>
• #include <queue>

등등

힙(HEAP) 추가 스터디

Max Heap만 구현할 줄 알면 됨

• 연산

• 현재 최댓값 관찰 (top)
• 최댓값 제거 (pop)
  • = root 삭제
  • 1) 없어져야 할 위치에 있는 노드를 루트로 올린다(맨 마지막 노드)
  • 2) 둘 중에 더 큰 자식노드를 선택해 그 방향으로 내려간다.
• 임의의 값 추가 (push)
  • 새로 추가한 값(자식노드)이 부모노드보다 클 경우, 힙의 성질을 만족할 때까지 부모노드와 위치 교환

• 부모노드가 자식노드보다 크거나 같다
• 1차원 배열로 구현 가능

• 구현방법

• PriorityQueue Lib. 사용(Java/C++)

Indexed Tree

• 숫자의 갱신과, 주어지는 구간에 대해서 원하는 연산을 (합, 최댓값, 최솟값) O(log n)의 시간복잡도로 해결해 줄 수 있는 자료구조

• 가장 많이 쓰이는 종류 : Sum Indexed Tree

Sum Indexed Tree

• 높이 : log N + 1
• 부모노드의 값은 두 자식노드 값의 합

• root : 모든 노드값의 합

• 같은 레벨에 3개 이상 연속해서 있다면, 그 중 두 개는 상위 레벨로 올릴 수 있다.
--> 즉, 같은 높이에 최대 2개의 노드까지만 더함

구현방법 (서치해서 다시 정리하기...설명 놓쳤다)

• 들어오는 데이터가 맨 밑줄에 들어옴
• Sum Heap과 유사

• 들어오는 데이터가 2의 제곱수가 아닐 경우 --> 데이터의 수를 충족하는 만큼 배열을 추가해준뒤, 남은 곳은 덧셈의 항등원인 0으로 채워준다.