Computer Science/Algorithm2 [Swift] Quick Sort 구현해보기 [Swift] Quick Sort 구현해보기 퀵 정렬은 분할 정복 기법중에 하나다. 분할 정복이란 문제를 작은 두개의 문제로 분리하고, 각각 해결한 다음 결과를 모아서 문제를 해결하는 전략이다! 먼저 프로세스를 살펴보면 1. 배열 에서 이 될 하나의 원소를 고른다. 2. 피벗 앞에는 피벗보다 작은 값들이 오고, 피벗 뒤에는 큰 값이 오도록 배열을 두개로 나눈다. --> 이렇게 배열을 두개로 나누는 걸 분할이라고 한다. 3. 분할된 두개의 작은 배열에 대해 재귀적으로 과정을 반복한다. func quickSort(_ array: [Int]) -> [Int] { guard let first = array.first, array.count > 1 else { return array } let pivot = fi.. 2023. 4. 28. [Swift] 이진 탐색 구현 [Swift] 이진 탐색 구현 조건 1. 배열 내부의 데이터가 정렬되어 있어야 함 2. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 3. 이진 탐색은 위치를 나타내는 변수를 세 개 사용 -> 시작점, 끝점, 중간점 -> 중간점으로 찾으려난 데이터와 비교하여 다시 시작점 / 중간점 / 끝점 설정 언제 쓰면 좋을까? - 처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어갈 때 사용 구현 - 재귀 혹은 단순 반복문으로 구현이 가함 - 시간 복잡도: O(logN) - 아래는 재귀 함수를 호출하는 방식으로 구현 func binarySearch(_ array: [Int], _ target: Int, _ count: Int) -> Int { if array.count == 1 && array[0] == .. 2023. 4. 11. 이전 1 다음
