망하면 망하는 대로 세계여행! 망하면 망하는 대로 세계여행!

힙정렬 (Heap Sort) 1. 기본동작 1) 모든 노드를 순회하면서, 현재 노드를 기준으로 위쪽으로 올라가며 Heapify 한다. 2) 루트 값을 가장 뒤쪽으로 보내고 Heapify 하며 크기를 줄여간다. 2. 시간복잡도 : O(N * log N) 3. 구현 - BOJ 의 11650번 좌표정렬하기를 힙정렬을 직접 구현하여 풀었습니다. (www.acmicpc.net/problem/11650) - 아래 heapSort 코드는 SWEA(swexpertacademy.com/main/visualcode/main.do#/home/mainlayout) 에서 Priority Queue의 레퍼런스 코드를 참고하여 구현하였습니다. #include struct Node { int x, y; } heap[100001]; ..

void rotate_cw(int M, int array[4][4], int count) { int rotatedArray[4][4]; while (count--) { for (int row = 0; row < M; ++row) { for (int col = 0; col < M; ++col) { rotatedArray[row][col] = array[M - 1 - col][row]; } } for (int row = 0; row < M; ++row) { for (int col = 0; col < M; ++col) { array[row][col] = rotatedArray[row][col]; } } } } void rotate_ccw(int M, int array[4][4], int count) { int..

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식이다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 장점 : 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다 단점 : 정렬된 리스트에만 사용할 수 있다 시간복잡도 : O(logN) int binarySearch(int arr[], int searchData, int start, int end){ if (start > end)return -1; int mid = (start + end) / 2; if (arr[mid] == searchData) retu..

- 부분집합으로 분할(Divide)하고 분할된 각 부분집합을 병합(Merge)하면서 정렬하는 분할정복(Divde&Conquer) 기법의 정렬 알고리즘 * 최선, 평균, 최악 : - 상당히 효율적인 정렬 알고리즘임을 알 수 있다. - 단 추가 메모리 공간이 필요하기 때문에 배열의 크기가 큰 경우는 비효율적이다. void mergeSort(int arr[], int buffer[], int start, int end) { if(start < end) { int middle = (start + end) / 2; mergeSort(arr, buffer, start, middle); mergeSort(arr, buffer, middle + 1, end); // divde int i = start; int j = ..

- 피봇(pivot)을 기준으로 왼쪽에 작은 값 / 오른쪽에 큰 값으로 분류한 후, 이 두 부분 집합에 대해 각각 퀵소트를 동일하게 반복하는 분할 정복 (Divide and Conquer) 기법의 정렬 알고리즘 - 재귀호출 이용 * 최선, 평균 : - 상당히 효율적인 정렬 알고리즘임을 알 수 있다. * 최악 : - 부분집합이 한 쪽으로만 계속 몰리는 경우 효율성이 떨어진다. void quickSort(int arr[], int start, int end) { if (start < end) { int left = start; int right = end; int pivot = end; while(left < right) { while(arr[left] = arr[pivot] && left < right) ..