패스트캠퍼스 챌린지 17일차

패스트캠퍼스 챌린지 17일차

비선형 자료구조

<비선형 자료구조: 앞과 뒤의 요소가 1:n으로 배치되어있는 자료구조>

트리:

트리의 자식노드 수를 '디그리(차수)'라고 함.

레벨: '단'의 갯수

이진트리 (디그리<= 2)를 가장 많이 사용

Complete binary tree 이진트리의 레프트 노드부터 채워지는 형태

heap: Max heap/Min heap (중복가능)

heap sort

priority queue

Fully complete binary tree 두개씩 다 달린것

binary search tree 중복불가

parent를 중심으로 left는 자기보다 작은값, right는 자기보다 큰 값을 가짐

avl트리, 레드블랙트리 (밸런스를 맞춰준다)

log2n는 평균값, skewed tree가 부적절한 이유

트리/그래프를 쭉 도는것 traversal

preorder inorder postorder

inorder traversal를 하면 binary search tree는 sorting이 된다 -> 순서대로 다 정렬됨

* Collection Framework의 Treeset, TreeMap이 binary search tree로 구현되어 있음

그래프: 구글맵 등

vertex(edge)

edge

인접행렬/인접리스트

BFS/DFS

해싱: JDK내에 라이브러리 존재 / Dictionary

Key/value pair로

index는 순서와는 무관하기 때문에 내가 넣은 순서와 무관하게 데이터가 출력됨

키는 유일, value는 중복될수도

hashfunction을 어떤식으로 만드느냐에 따라 분포도가 달라짐

collition관리: hashtable/chaining

- hashtable (2차원배열)

슬롯에 나란히 들어있는 애들을 synonym이라고 함

버켓(row)이 크고 슬롯(column)이 크면 오버헤드 발생

-chaining

linkedlist 활용

https://bit.ly/37BpXiC

※ 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

내일부터 스프링할거얌~ 알고리즘도 다시 해야지 ㅎㅎ

from http://hardblackpencil.tistory.com/50 by ccl(A) rewrite - 2021-09-23 00:00:21