All about Data Structure & Algorithm/심화 (8) 썸네일형 리스트형 라빈 카프 알고리즘 ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. 보이어 무어 알고리즘(Boyer moore) 홀짝 정렬(Odd-Even sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 홀짝 정렬은 배열을 오름차순으로 정렬하는 병렬 정렬 알고리즘이다. ㉠ 홀짝 정렬은 브릭 정렬(brick sort)이라고도 알려져있다. ② 홀짝 정렬은 분할 정복 전략(devide-and-conquer strategy)를 사용하는 병합 정렬을 기반으로 한다. ③ 홀짝 정렬의 기본 원리는 다음과 같다. ㉠ 홀수 인덱스의 인접한 두 요소를 비교한다. ㉡ 순서가 잘못되어 있으면 순서를 바꾼다. ㉢ 짝수 인덱스에 대해서 ㉠ ㉡을 시행한다. ㉣ 정렬이 완료될 때까지 ㉠ ㉡ ㉢를 반복한다. ④ 홀짝 정렬의 의사 코드(psuedo code)는 다음과 같다. HTML 삽입 미리보기할 수 없는 소스 ⑤ 비교적 구현이 매우 간단하지만, 최악의 경우 시간 복잡도가 O.. 향상된 퀵 정렬 셸 정렬(Shell Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 셸 정렬(shell sort)는 삽입 정렬의 일반화된 형태이며, 먼 거리에 있는 요소들 간의 교환을 가능하게 해서 성능을 높였다. ㉠ 셸 정렬은 셸의 방법(shell 's method)으로도 불린다. ② 셸 정렬의 최악의 시간 복잡도는 삽입 정렬과 마찬가지로 O(log(n))이다. ㉠ 그렇지만, 퀵 정렬 다음으로 셸 정렬이 두 번째로 빠르다. ③ 셸 정렬의 기본 원리는 다음과 같다. ㉠ 정수로 된 갭 시퀀스를 정한다. (h1>h2>h3>h4>...hk = 1) ⓐ 갭은 하위 배열 간의 간격을 의미하며, 최종적으론 하위 정렬 간의 간격이 1이 되어야 함을 의미한다. ⓑ 갭이 1씩 줄어드는 갭 시퀀스를 가진 셸 정렬이 삽입 정렬이다. 삽입 정렬(In.. 분할 정복(Divide and conquer) ① 분할 정복(divide and conquer)은 컴퓨터 과학과 알고리즘 설계에서 널리 사용되는 문제 해결 전략이다. ㉠ 분할(divide) : 분할 정복 알고리즘은 큰 문제를 작은 하위 문제로 분할하는 과정을 거친다. ㉡ 정복(conquer) : 분할된 하위 문제를 재귀적으로 해결하는 과정을 거친다. 하위 문제의 크기가 충분히 작아질 경우, 직관적인 방법으로 해결할 수 있다. ㉢ 결합(combinie) : 분할된 문제를 다시 결합하면서 원래의 큰 문제의 해결책을 구한다. ② 분할 정복을 사용하는 유명한 알고리즘의 예시는 병합/합병 정렬(merge sort), 퀵 정렬(quick sort), 고속 푸리에 변환(fast fourier transform, FFT), 쉬트라센의 행렬 곱셈(Strassen's.. 일반 마스터 정리(Generalized Master theorem) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 일반 마스터 정리(generalized master theorem)는 고급 마스터 정리(advanced master theorem)와 확장 마스터 정리(extended master theorem)으로도 불린다. ㉠ 일반 마스터 정리는 여러 가지 형태가 있으며, 비교적 이해하기 쉬운 형태를 소개할 것이다. ② 일반 마스터 정리는 마스터 정리에서 발전된 형태로 재귀 문제를 좀 더 포괄적인 방법으로 설명한다. ㉠ 광범위한 분할 정복 알고리즘의 시간 복잡도를 구할 수 있다. ⓐ n은 문제의 크기를 말한다. ⓑ a는 재귀에서 생성되는 하위 문제의 크기다. ⓒ b는 재귀의 매 단계에서의 하위 문제 크기를 의미한다. ⓓ n/b는 문제의 크기에 대한 하위 문제.. 마스터 정리(Master Theorem) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 마스터 정리(master theorem)는 복잡한 알고리즘(recursive algorithm)의 시간 복잡도를 구하기 위해 사용한다. ② 마스터 정리로 해결할 수 있는 알고리즘의 구조는 다음과 같은 꼴을 따른다. ㉠ a>=1, b>1 인 상수여야 한다. ㉡ f(n)이 점근적으로 양수 함수값을 가지는 함수여야 한다. ㉢ 설명의 편의를 위해 A항 B항이라고 칭하겠다. ③ A항은 상위 문제를 해결하기 위해 상위 문제(super problem)를 하위 문제(sub problems)로 분할하는 데 소요되는 시간 복잡도이다. ㉠ 상수 a는 재귀 함수가 호출하는 하위 재귀 함수의 숫자이다. ㉡ 하위 재귀 함수는 n/b의 크기로 분할된다. ㉢ 상위 문제의 1.. 이전 1 다음
