심화 정렬 알고리즘 문제 풀이 handsukite.tistory.com/119?category=987470 [Sorting] 1181. 단어 정렬 #include #include using namespace std; string arr[20000]; int n; bool compare(string a, string b) { if(a.length() b.length()) return 0; else // 길이가 같.. handsukite.tistory.com handsukite.tistory.com/120?category=987470 [Sorting] 1431. 시리얼 번호 #include #include using namespace std; string a.. onYouTube/Algorithm 2021. 4. 4. 06:37
계수 정렬(Counting Sort) "계수 정렬" : 크기를 기준으로 세는 알고리즘 시간 복잡도 : O(N) '범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘 크기를 기준으로 개수만 세주면 되기 때문에 위치를 바꿀 필요가 없음 모든 데이터에 한 번씩만 접근하기 때문에 효율적 class Sort { public int[] Counting_Sort(int[] arr, num) { int[] count = new int[num]; for(int i = 1; i onYouTube/Algorithm 2021. 4. 4. 05:19
힙 정렬(Heap Sort) "힙 정렬" : 힙 트리 구조를 이용하는 정렬 방법 모든 원소를 기준으로 힙 생성 알고리즘(Heapify Algorithm) 사용 내림차순을 위해서는 최대 힙을, 오름차순을 위해서는 최소 힙을 구성 시간 복잡도 : O(N * logN) 항상 O(N * logN)을 보장 병합 정렬과 퀵 정렬만큼 빠르지만, 더 우위에 있음 단순히 속도만 비교하면, 퀵 정렬이 더 빠르기 때문에 일반적으로 많이 사용되지는 않음 추가적인 배열이 필요하지 않기 때문에, 메모리 측면에서 몹시 효율적 "힙 생성 알고리즘" : 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘 하나의 노드에 대해서 수행 하나의 노드를 제외하고는 최대 힙으로 구성되어 있는 상태라고 가정 시간 복잡도 : O(logN) "힙(Heap.. onYouTube/Algorithm 2021. 4. 3. 21:12
C++ STL sort( ) 함수 다루기 sort( ) 함수는 C++ algorithm 헤더에 포함되어 있음 sort( ) 함수는 기본적으로 오름차순 정렬을 수행 sort(배열의 시작점 주소, 마지막 주소 + 1) #include #include using namespace std; int main(void){ int a[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2}; sort(a, a+10); for(int i = 0; i < 10; i++) { cout onYouTube/Algorithm 2021. 4. 2. 20:24
병합 정렬(Merge Sort) "병합 정렬" : 일단 정확히 반으로 나누고 나중에 정렬 시간 복잡도 : O(N * logN) 정확히 반으로 나누기 때문에, 최악의 경우에도 O(N * logN)을 보장 단계의 크기 : logN (데이터 개수 : N) 정렬 자체에 필요한 수행 시간 : N 대표적인 '분할 정복' 방법을 채택한 알고리즘 재귀함수로 구현 합치는 순간에 정렬을 수행 반드시 정렬에 사용되는 배열은 '전역 변수'로 선언해야 함 기존의 데이터를 담을 추가적인 배열 공간이 필요하기 때문에, 메모리 활용이 비효율적 어떠한 상황에서도 정확히 O(N * logN)을 보장하기 때문에 몹시 효율적 class Sort { int[] sorted = new int[10]; // 임시적인 정렬 배열; 반드시 전역 변수로 선언 public void .. onYouTube/Algorithm 2021. 4. 2. 18:09
기초 정렬 알고리즘 문제 풀이 handsukite.tistory.com/110 [Sorting] 2750. 수 정렬하기 #include int main(void){ // 선택 정렬 int arr[1001]; int num; int index = 0; scanf("%d", &num); for(int i = 0; i < num; i++) scanf("%d", &arr[i]); for(int i = 0; i < num; i++){ int min = 1001; for(i.. handsukite.tistory.com handsukite.tistory.com/111handsukite.tistory.com/112 [Sorting] 2752. 세 수 정렬 #include int main(void){ int arr[3]; int index = 0; .. onYouTube/Algorithm 2021. 4. 2. 17:16
퀵 정렬(Quick Sort) "퀵 정렬" : 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나누는 정렬 방법 시간 복잡도 : O(N * logN) 최악의 시간 복잡도 : O(N^2) 대표적인 '분할 정복' 방법을 채택한 알고리즘 재귀함수로 구현 "피벗(Pivot)" : 기준 값 보통 맨 앞 요소를 피벗으로 설정 class Sort { public void Quick_Sort(int[] arr, int start, int end) { if(start >= end) // 원소가 한 개인 경우, 그대로 두기 return; int pivot = start; // 피벗은 첫 번째 원소 int i = start + 1; int j = end; while(i j) { // 현재 엇갈린 상태이면, 피벗과 교체 int.. onYouTube/Algorithm 2021. 4. 2. 15:19
삽입 정렬(Insertion Sort) "삽입 정렬" : 각 숫자를 적절한 위치에 삽입하는 방법 시간 복잡도 : O(N^2) 앞에 있는 원소들이 이미 정렬이 되어 있다고 가정하고 필요할 때만 위치를 바꾸기 때문에, 효율적 데이터가 거의 정렬된 상태에 한해서는 가장 빠름 class Sort { public int[] Insertion_Sort(int[] arr) { for(int i = 0; i arr[j+1]) { int temp = arr[j]; arr[j]= arr[j+1]; arr[j+1] = temp; j--; } } } } onYouTube/Algorithm 2021. 4. 2. 02:37
