#TIL_21.8.9

정렬

• 요소들을 일정한 순서대로 열거하는 알고리즘
• 특징
  정렬 기준을 사용자가 정할 수 있음
  비교식 정렬 / 분산식 정렬
  삽입, 선택, 버블, 머지, 힙, 퀵 등 다양한 정렬 방식 존재
• 비교식 정렬
  다른 요소와 비교를 하며 정렬하는 방법
  • 버블 정렬
    서로 인접한 두 요소를 검사하여 정렬
    O(n^2)
  • 선택 정렬
    선택한 요소와 가장 우선순위가 높은 요소를 교환하여 정렬
    O(n^2)
  • 삽입정렬
    선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 정렬
    O(n^2)
• 분산식 정렬
  요소를 분산하여 정렬하는 방법
  • 분할 정복
    문제를 작은 2개의 문제로 분리하고, 더이상 분리가 불가능 할 때 처리한 후 합치는 방법
    다양한 알고리즘에 응용
    - 합병 정렬
    분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘
    요소를 절반으로 나누고, 하나만 남을 때 까지 반복 -> 두 요소끼리 정렬하여 합치는 작업을 반복
    O(n log n)
  • 퀵 정렬
    분할 정복 알고리즘을 이용하여 평균적으로 빠르지만, 최악의 경우 2차 시간이 걸림 (불안정 정렬)
    피벗(보통 첫번째 요소)을 기준으로 기준보다 작은 값을 좌측으로, 큰 값을 우측을 나눔 -> 나뉜 배열에서 피벗을 각각 설정하여 좌, 우측으로 나누는 과정을 반복 -> 더이상 나눌 수 없는 상태가 되면 합침
    O(n log n)
    

---

이진 탐색

• 선형 탐색
  순서대로 하나씩 찾는 탐색 알고리즘
  O(n)
• 이진 탐색
  Up and Down
  정렬이 되어있는 요소들을 반씩 제외하며 찾는 알고리즘
  배열 혹은 이진트리로 구현이 가능하다
  O(log n)
  정렬이 되어있다면 가급적 이진 탐색을 사용하자! (상당히 빠름)
  - left = 0, right = array.length - 1, mid = (left + right) / 2
  -> 찾는 값이 mid 보다 작다면 right = mid - 1,
  -> 찾는 값이 mid 보다 크다면 left = mid + 1
  • 문제점
    최악의 경우 한쪽으로 편향된 트리가 될 수 있다. (계속 감소하거나, 계속 증가하거나)
    이 경우, 순차 탐색과 동일한 시간복잡도를 가짐
    이럴 경우 AVL 트리, 레드-블랙 트리 자료구조를 이용할 수 있다.
    

---

느낀점

오늘은 특강이 두개나 잡혀있기도 했고, 개인적으로 할 일이 있어서 많은 강의를 듣진 못하였다..ㅜ

배열을 사용하는 정렬은 그래도 익숙했지만, 삽입정렬은 실제로 응용해 본 적은 없었고 주로 사용하는건 버블정렬 혹은 선택정렬 뿐이기도 했다.

정렬을 Linked List 로 구현하는 것을 보니 너무 머리가 아프기 시작했지만.. 개념은 숙지했고, 실제로 응용해 보는 것이 남아있다..

이진 탐색은 실제로 알고리즘 문제를 풀면서 사용해본 개념이라 어떤 상황에서 이진 탐색 알고리즘을 사용해야 하는지 빠른 파악을 할 수 있게끔 연습해야겠다.

그리고 이전 날짜 강의의 실습문제를 풀면서 남은 시간을 보냈는데 결국 풀지는 못했다..
내일은 구글링으로 참고해가면서 풀어보려고 한다.

진도가 너무 뒤쳐지지 않게 관리해야겠다. 🥲