Notice
Recent Posts
Recent Comments
Link
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 28 | 29 | 30 | 31 |
Tags
- 정렬
- java
- 기수정렬
- SNS
- C++
- 프로그래밍언어
- 선택알고리즘
- 자료구조
- 병합정렬
- 자바
- 퀵정렬
- 선택정렬
- 수학
- 버블정렬
- 재귀
- 프로그래밍
- DP
- 동적계획법
- 백트래킹
- 계수정렬
- 정수론
- 힙정렬
- 안드로이드
- 코딩테스트
- 백준
- 다이나믹프로그래밍
- Median of Medians
- 삽입정렬
- 알고리즘
- 동적프로그래밍
Archives
- Today
- Total
목록quickselect (1)
MODE::CREATIVE
숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)선택 알고리즘 1.선형 시간 선택 알고리즘(QuickSelect)2.최악의 경우 선형 시간 선택 알고리즘 선택 알고리즘이란 선택 알고리즘은 주어진 리스트에서 k번째로 작은(또는 큰) 요소를 찾는 알고리즘을 의미합니다. 이 알고리즘은 다양한 방법으로 구현될 수 있습니다. 선형 시간 선택 알고리즘은 최악의 경우에도 O(n)의 시간 복잡도를 가지는 알고리즘입니다. 이 알고리즘의 대표적인 예는 QuickSelect입니다. QuickSelect는 QuickSort 알고리즘을 기반으로 하며, 분할-정복 방식을 사용합니다. 피벗을 선정하고 이를 기준으로 리스트를 두 부분으로 나눈 후, k가 어느 부분에 있는지에 ..
Algorithms
2024. 2. 26. 16:18