[SCCC] #1

PS, 시간복잡도, 정렬알고리즘, 이분탐색

• PS(Problem Solving) : 알고리즘을 설계하는 것

• 시간 복잡도 : 빅오, 오메가

• 정렬 알고리즘

  • 오름차순 : 1 2 3 4 5 ...
  • 내림차순 : 5 4 3 2 1 ...
  • 위상정렬 : a->b간선이 있으면 a가 b보다 앞에 오도록 설계

• 비교 기반 정렬

  • 버블정렬 : 주변에 있는 원소와 교환하면서 정렬하는 알고리즘
  • 선택정렬 : 가장 작은 원소를 맨 앞에 있는 원소와 교환하면서 정렬하는 알고리즘
  • 그외 : 삽입정렬, 병합정렬, 퀵정렬 등

• 비교함수 : bool Compare(T a, T b)

  • a가 b보다 반드시 앞에 나와야 하면 true, 그렇지 않다면 false
  • Strick Weak Ordering을 만족하야 함 -> a<=b 를 비교함수로 사용할 수 없음

• C++ 정렬 함수

  • std::sort(first, last, comp) : 시작주소, 끝주소, 비교함수
  • std:stable_sort() : 기존 순서 유지

• 이진 탐색/이분 탐색(Binaray Search) : 절반 잘라서 탐색. O(logN)