알고리즘

알고리즘

이진 탐색 트리

• 모든 데이터가 한쪽으로 쏠려있는 경우
  • 예를 들면 가장 오른쪽 노드의 14 다음 15, 16, 17 이런식으로 계속 오른쪽 밑으로 내려가면 logn에 끝나는 것이 아닌 n 순차 탐색이다.

B Tree

• 위의 이진 탐색 트리의 단점으로 인해 나타난 것

• 무조건 높이가 같음.

Dijkstra 알고리즘과 A* 알고리즘

A* 알고리즘

A* 알고리즘 예시

1. A → B 갈때 5분 걸림
   1. g(n) = 5
2. B → F 갈때 가는 노드들
   1. B → D → E → C → F
   2. B → E → C → F
   3. B → C → F
3. 그래서 최적의 경로로 예상하는 것은 A → B → C → F 이다.
   1. 왜냐면 예상은 걸리는 가중치가 아닌, 노드의 개수로 예상하기 때문
4. h(n) = 10 + 4 = 14, f(n) = 5 + 14 = 19
   1. 그래서 f(n) = 19로 처음에 정해진다.
   2. 매우 빠르게 해답을 찾았지만, 항상 최적은 아님.

정렬 알고리즘

• 대부분의 정렬 알고리즘은 O(n^2)이다.
• 퀵정렬의 알고리즘만 O(nlogn)이 나오기는 하지만, 어차피 Big O 표기법은 최악의 상태를 의미하기 때문에 퀵정렬도 O(n^2)이다.

기수 정렬

• 1의 자리부터 시작해서 마지막자리 까지 비교해 정렬
• 다른 정렬들과는 다르게 O(n)이다.

Stack

• 후입선출
• 자판기 옆 종이컵 수거함
  • 가장 처음 넣은 것이 가장 마지막에 나옴.

Queue

• 선입선출
• 은행, 음식점 같은 곳에서 줄을 서있으면 가장 먼저 온 사람이 가장 먼저 서비스를 받는 것