All about Data Structure & Algorithm/기본

 (14)
퀵 정렬(Quick Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 퀵 정렬(quick sort)은 분할 정복 (devide and conquer)을 이용한 대중적인 정렬 알고리즘 중 하나이다. ② 퀵 정렬의 최악의 경우의 시간 복잡도는 O(n^2)이지만 평균적인 경우의 시간 복잡도는 O(n log(n))인 특이한 정렬 방법이다. ③ 퀵 정렬의 기본 원리는 다음과 같다. ㉠ 배열에서 피벗 요소를 고른다. 피벗 요소는 임의로 선택될 수 있다. ㉡ 배열을 두 개의 하위 배열 A, B로 나눈다. 하위 배열 A는 피벗 요소보다 작은 값을, 하위 배열 B는 피벗 요소보다 크거나 같은 값을 분류한다. ㉢ 하위 배열 A와 B에 ㉠, ㉡을 재귀적으로 적용한다. ④ 퀵 정렬의 의사 코드(psuedo code)는 다음과 같다. H..
병합 정렬(Merge Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 병합 정렬(merge sort)은 분할 정복(devide and conquer)을 이용한 대중적인 정렬 알고리즘 중 하나이다. ㉠ 병합 정렬은 합병 정렬로도 불린다. ② 병합 정렬의 최악의 경우의 시간 복잡도는 O(nlog(n))으로 데이터의 크기가 큰 경우에 적절한 정렬 방법이다. ③ 병합 정렬의 기본 원리는 다음과 같다. ㉠ 정렬되지 않은 배열을 절반으로 나누는 행위를 배열의 사이즈가 1이 될 때까지 반복한다. ㉡ 사이즈가 같은 배열을 정렬하면서 배열을 하나로 합친다. ㉢ 합친 배열의 크기가 원래 배열이 될 때까지 ㉡를 반복한다. ④ 병합 정렬의 의사 코드(psuedo code)는 다음과 같다. HTML 삽입 미리보기할 수 없는 소스 ⑤ 병합..
선택 정렬(Selection Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 선택 정렬(selection sort)는 비교적 간단한 정렬 알고리즘이다. ㉠ 추가적인 메모리 공간이 필요하지 않지만, 알고리즘의 수행 시간이 O(n^2)이다. ② 삽입 정렬은 제자리 알고리즘(in-place algorithm) 중 하나이다. ㉠ 제자리 알고리즘은 자료 구조를 추가로 사용하지 않아 추가적인 메모리 공간이 필요하지 않다는 것을 의미한다. ③ 선택 정렬의 기본 원리는 다음과 같다. ㉠ 정렬된 부분 배열과 정렬되지 않은 부분 배열로 나눈다. ㉡ 정렬되지 않은 부분 배열에서 가장 작은(혹은 가장 큰) 요소를 찾는다. ㉢ 정렬되지 않은 부분의 첫 번째 인덱스(혹은 제일 뒤 인덱스)와 스왑한다. ㉣ ㉡과 ㉢를 반복해서 시행해서 전체 배열이 ..
이진 검색 알고리즘(Binary Search Algorithm) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 이진 검색 알고리즘(binary search algorithm)은 크기가 n인 정렬된 배열 안에 X가 존재하는 지를 탐색하기 위한 알고리즘이다. ㉠ 이진 검색 알고리즘은 이분 탐색 알고리즘, 이진 탐색 알고리즘, 이분 검색 알고리즘이라고도 불린다. ② 이진 검색 알고리즘을 이해하기 위한 가장 쉬운 예시로 업 앤 다운(up and down)을 들 수 있다. ㉠ 상대는 숫자 한 가지를 생각한다. ㉡ x보다 큰가? -> Yes -> x보다 작은 숫자 집합은 정답에서 제외된다. ㉢ x보다 큰가? -> No-> x보다 큰 숫자 집합은 정답에서 제외된다. ㉣ 정답 x를 찾을 때까지 ㉡과 ㉢을 반복한다. ③ 특정 x를 결정하는 가장 합리적인 방법이 상한과 하..
삽입 정렬(Insertion Sort)과 이진 삽입 정렬(Binary Insertion Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 삽입 정렬(insertion sort)는 비교적 간단한 정렬 알고리즘이다. ㉠ 추가적인 메모리 공간이 필요하지 않지만, 알고리즘의 수행 시간이 O(n^2)이다. ② 삽입 정렬은 제자리 알고리즘(in-place algorithm) 중 하나이다. ㉠ 제자리 알고리즘은 자료 구조를 추가로 사용하지 않아 추가적인 메모리 공간이 필요하지 않다는 것을 의미한다. ③ 삽입 정렬과 이진 삽입 정렬의 기본 원리는 정렬된 배열 A에 정렬할 요소를 집어넣는 것이다. ㉠ 삽입 정렬과 이진 삽입 정렬의 작동 원리는 다음과 같다. ⓐ 정렬할 배열을 정렬된 배열 A와 비정렬된 배열 B로 나눈다.(크기가 1인 배열은 정렬된 상태로 본다.) ⓑ 비정렬된 배열의 첫 번째 요소가..
버블 정렬(Bubble sort)과 교환 정렬(Exchange sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 버블 정렬(bubble sort)과 교환 정렬은 O(N^2)의 시간 복잡도를 갖는 정렬 알고리즘 중 하나이다. ㉠ 정렬의 가장 이상적인 상황에서의 시간 복잡도는 O(N)이다. ⓐ 모든 항목이 정렬되어 있을 경우 단순 탐색만 진행하면 되기 때문에 O(N)의 시간 복잡도를 갖는다. ㉡ 버블 정렬과 교환 정렬의 최악의 상황에서 시간 복잡도는 O(N^2)이다. ② 버블 정렬과 교환정렬의 기본적인 작동원리는 인접한 두 수를 비교해 위치를 바꾸는 것으로 동일하다. ㉠ 버블 정렬의 작동 원리는 다음과 같다. ⓐ 선택된 배열의 첫 번째 요소와 두 번째 요소를 비교한다. 만약 정렬되어 있지 않다면 둘의 위치를 바꾼다. ⓑ 인접한 다음 쌍으로 이동하고 배열의 끝에..

티스토리툴바