전공/C++ 검색 결과

13 개의 검색 결과가 있습니다.

전공/C++

알고리즘 : 정렬 #3 (Shell Sort, Heap Sort)

지금까지 대표적인 정렬 다섯개에 대해 알아보았습니다. 이번엔 좀 더 응용된 정렬인 Shell Sort(쉘 정렬), Heap Sort(힙 정렬)에 대해 알아보겠습니다. Shell Sort (쉘 정렬) Shell Sort(쉘 정렬)는 Insertion Sort(삽입 정렬)를 변형한 정렬입니다. 먼저 Shell sort에는 "gap" 이 존재합니다. 이 gap을 미리 정해 두고, gap만큼 벌어진 것들 끼리 삽입 정렬을 해주는 겁니다. 그림으로 보겠습니다. 다음 배열 a[]를 정렬하려 하는데, gap을 1 ← 4 ← 13 으로 정했다고 합니다. 무슨 뜻일까요? 일단 첫 시작은 gap=13 이라니까 한번 보도록 합시다. 그러고선 앞서 정한 gap만큼 건너 뛴 원소들끼리 삽입 정렬을 해줍니다. 이 때 3번째 원소..

2022. 4. 20. 00:24

전공/C++

알고리즘 : 정렬 #2 (Mergesort, Quicksort, Stable)

이번에 알아볼 것은 Mergesort(합병 정렬), In-place Quicksort(제자리 퀵 정렬)이며, 정렬의 Stable함을 소개하며 마치겠습니다. Merge Sort (합병 정렬) Mergesort에 들어가기 전, 저번에 복잡도의 점화식에 대해 소개할 때 이상한 코드 하나를 가져왔었죠? BinarySearch(a[], key, left, right) // a[mid] = key인 인덱스 mid를 반환 if (left a[mid] : return (BinarySearch(a, key, mid+1, right)); } } else return -1; // key 값이 존재하지 않음 end BinarySearch() 바로 이 코드입니다. 그 때 말했듯 이 함수를 실행하면 절반짜리 입력으로 재귀호출을 ..

2022. 4. 19. 09:04

전공/C++

알고리즘 : 정렬 #1 (Bubble Sort, Insertion Sort, Selection Sort)

정렬 알고리즘(Sorting Algorithm)은 알고리즘 설계의 처음이자 마지막입니다. 정렬 알고리즘은 n개의 숫자가 주어졌을 때 이를 기준에 맞게 정렬하는 알고리즘으로, 개발자들은 지난 100년간 이 정렬 알고리즘의 실행 시간을 줄이기 위해 노력해왔습니다. 오늘 소개할 정렬은 제일 기본적인 정렬 세 가지입니다. - Bubble Sort (버블 정렬) - Insertion Sort (삽입 정렬) - Selection Sort (선택 정렬) 위 세 가지 정렬은 모두 구조가 간단하며 O(n²)의 시간 복잡도를 가집니다. 따라서 잘 쓰이지는 않지만 다른 정렬의 기초가 되죠. Bubble Sort (버블 정렬) 먼저 Bubble Sort(버블 정렬) 입니다. 이러한 크기 7 짜리의 배열 S가 있고, 우리는 이..

2022. 4. 19. 05:00

전공/C++

알고리즘 : 마스터 정리(Master Theorem)

어찌저찌 점화식을 구했는데, 이를 전개해서 복잡도를 알아내는 것도 쉽지만은 않다는 것을 저번 시간에 보았습니다. 하지만 우리는 언제나 방법을 찾아냅니다. 바로 "마스터 정리(Master Theorem)"입니다. T(n) = aT(n/b) + f(n) 꼴의 점화식이 있다고 합시다. 물론 여기엔 조건이 붙습니다. 1. f(n)은 asymptotically positive function 이어야 함. 2. a≥1 and b>1 의 상수여야 함. 3. the regularity condition that af(n/b) ≤ cf(n) for some constant c < 1. 음... 2번 빼고는 무슨 말인지 도통 모르겠네요. 대충 설명을 드리자면, f(n)은 positive function이어야 함, 즉 음수..

2022. 4. 18. 08:14

전공/C++

알고리즘 : 복잡도의 점화식

이진 탐색 알고리즘이 다음의 수도 코드로 주어졌습니다. BinarySearch(a[], key, left, right) // a[mid] = key인 인덱스 mid를 반환 if (left a[mid] : return (BinarySearch(a, key, mid+1, right)); } } else return -1; // key 값이 존재하지 않음 end BinarySearch() 이 코드가 뭔지 분석하자는 말은 아니고, 단순히 복잡도 분석만 해보도록 하겠습니다. 참고로 수도 코드(pseudo code)란 실제 코드의 대략적인 기능만 써놓은 일종의 요약본 입니다. 먼저 이 BinarySearch 함수는 a[]라는 배열, key, left, right를 인자로 받습니다. 대충 이런 배열에 대해 Binar..

2022. 4. 18. 07:32

전공/C++

알고리즘 : 복잡도(Big O notation, Omega notation)

지난 글의 마지막에 코드의 복잡도를 알아보는 시간에, n, n+1, n+2, 2n, .... 은 O(n)에 속한다고 하였는데, O(n)은 일종의 "카테고리"라고 생각하시면 됩니다. 이렇게 묶은 이유는 코드에 따라서 복잡도 카테고리가 달라지기 때문입니다. 이러한 복잡도 카테고리는 O(1) : constant complexity O(loglogn) O(logn) : logarithmic complexity O(n) : linear complexity O(nlogn) O(n²) : quadratic complexity O(n³) : cubic complexity O(2ⁿ) : exponential complexity 으로 나뉘어 집니다. O(1)은 입력한 자료 수에 무관하게 1번만 연산되는 알고리즘입니다. f..

2022. 4. 18. 06:09