TIL 4일차

1. 트리

  이진트리의 종류

1) 이진트리 : 정점이 최대 2개의 자식을 가짐
2) 완전이진트리 : 마지막 레벨을 제외한 모든 정점이 채워짐
3) 포화이진트리 : 마지막 레벨까지 모두 채워짐
4) 편향 트리 : 정점히 한개로 한쪽으로 치우침

---

  이진트리의 응용

1) 이진탐색
2) 힙
3) AVL
4) 레드블랙트리

---

  힙

1) 최대 힙 : 가장 큰 루트 값
2) 최소 힙 : 가장 작은 루트 값

• 우선순위큐를 구현하기 위한 방법

• 우선순위 큐는 자료구조가 아닌 개념이므로 힙외에 다양한 방법으로 구현은 가능하다.

---

  힙의 구현 내용

1) 요소 추가
2) 요소 삭제

1) 요소 추가

• 트리의 가장 마지막 정점에 추가
• 추가 후 부모 정점과 우선순위를 판단하고 바꾼다.
• 이를 반복하여 힙을 설정 (이진트리이므로 해당 알고리즘은 O(logn) )

2) 요소 삭제

• 루트 정점만 삭제가능
• 가장 마지막 정점을 루트 정점으로
• 루트 정점과 자식 정점을 비교하여 우선순위에 따라 변경
• 우선순위가 변경 될때까지 반복

---

2. 트라이

문자열을 저장하고 효율적 탐색을 위한 트리형태 자료구조

---

  트라이 특징

루트는 비어있고 간선은 추가될 문자를 키로 가진다.
각 정점은 이전 정점 + 간선의 키 값이 된다.

---

3. 정렬

• 각각의 유리한 상황이 있다.

---

  정렬의 종류

1. 비교식 정렬 => O(n제곱)
   1) 버블정렬 : 인접 요소 검사
   2) 선택정렬 : 선택요소와 가장 우선순위가 높은 요소 교환
   3) 삽입정렬 : 인접 간의 값을 비교하여 밀어낸다
2. 분산식 정렬 (분할정복) => O(nlogn)
   1) 합병정렬 : 안정적인 정렬 알고리즘
   2) 퀵정렬 : 매우빠르나 최악의 경우 시간복잡도가 높다

---

  JS sort 함수

• array.sort()를 쓰면 ASCII 코드로 10이 2보다 오름차순이어도 1과 2를 비교해 정상적인 순서가 나오지 않는다.
• array.sort((a,b)=>a-b) 나 array.sort((a,b)=>b-a) 필요

---

4. 탐색

1. 선형탐색 => O(n)
2. 이진탐색 => O(logn)
   1) Array를 이용
   2) LinkedList를 이용 (이진탐색트리)

• 이진탐색 트리는 최악의 경우 편향된 트리가 될 수 있고 이를 해결하기 위해 AVL트리 / 레드-블랙트리가 존재한다.

---

5. BFS DFS

BFS

1. Queue를 이용하여 구현
2. 가까운 정점부터 탐색
3. 시간복잡도 : O(V+E) V:정점수 , E:간선수

---

DFS

1. Stack를 이용하여 구현
2. 시작정점부터 깊은 것을 먼저 찾는다.
3. 시간복잡도 : O(V+E) V:정점수 , E:간선수

---

6. 그리디

• 매 선택에서 지금 가장 최적의 답을 선택하는 알고리즘

---

그리디 알고리즘 종류

1. 크루스칼 알고리즘
2. 다익스트라 알고리즘

ex) 동전 최소 개수 반환 문제

---

7. 고차함수

‘다른 함수를 전달인자로 받거나 함수실행의 결과를 함수로 반환하는 함수

• ex) map , filter , reduce