1. 시간복잡도
- 프로그램이 실행되는데 걸리는 시간
- Big-O 표기법: 상한(이것보단 위다/빠르다) 점근 → 최악(주로 사용)
- Big-Ω 표기법: 하한(이것보단 아래다/느리다) 점근 → 최선
- Big-θ 표기법: 평균
- O(1) > O(log n) > O(n) > O(n^2) > O(c^n)
- 상수는 큰 영향을 미치지 않으므로 전부 제거
2. DP(Dynamic Programming)
- 문제를 풀기 위해 문제를 여러 개의 하위 문제로 나누어 푸는 것
- 답을 한 번만 계산하고 이 결과를 재활용하는 memoization으로 속도를 향상시킬 수 있음 → 최적의 풀이법 찾아낼 수 있음
- ① 중복되는 작은 문제
- ② 최적 부분 구조
3. Sort
- Quick > Merge > Heap > Injection > Select > Bubble
- Stable: 동일한 key를 가진 node의 순서가 바뀌지 않은 것
3-1. Bubble Sort
- 서로 인접한 두 원소를 비교하여 정렬
- 시간복잡도: O(n^2)
- Stable
3-2. Select Sort
- 첫 번째 값을 나머지와 비교해서 최솟값과 교환
- 시간복잡도: O(n^2)
- Unstable
- 역순(내림차순)으로 된 배열을 정순(오름차순)으로 정렬 시 효율적
3-3. Injection Sort
- 두 번째 값부터 앞에 존재하는 원소와 비교해서 삽입
- 시간복잡도: O(n) ~ O(n^2)(평균)
- Stable
- 거의 정렬되어 있는 상태일때 효율적
3-4. Heap Sort
- Heap으로 만들어서 최댓값 or 최솟값부터 꺼내서 정렬
- 데이터 추가 시 제일 마지막 자식 노드에 추가하여 부모와 비교한 뒤 교환
- 데이터 삭제 시 루트를 없애고 자식과 비교하여 교환
- 시간복잡도: O(n * log n)
- Unstable
3-5. Merge Sort
- 크기가 1인 배열로 분할하고 합병하면서 정렬 → 실제로 정렬되는 건 합병'할 때
- 시간복잡도: O(n * log n)
- Stable
3-6. Quick Sort
- 첫 번째 값을 pivot을 설정하여 pivot보다 작은 값은 왼쪽에, 큰 값은 오른쪽으로 분할 → 왼쪽값과 오른쪽값 사이에 pivot을 삽입하고 두 그룹으로 비균등하게 분할
- 시간복잡도: O(n) ~ O(n^2)
- Unstable
- 거의 정렬되어 있는 상태에서 비효율적
+) Ref
https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/
https://blog.naver.com/zephyehu/150013176075
https://velog.io/@xoqja055/%EB%A9%B4%EC%A0%91-%EC%A4%80%EB%B9%84%EB%A5%BC-%ED%95%B4%EB%B3%B4%EC%9E%90-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
