I'll never know if I never commit

중간값 퀵소트 (중간값 퀵소트에 대한 내용은 https://blog.naver.com/occidere/220870294816 를 참고했음을 밝힌다. 피벗값을 맨 앞, 맨 뒤로 설정하는 것에 대한 대안이 바로 '중간값 퀵소트' "Median QuickSort" 이다. 중간값 퀵소트의 원리는 일단 다음과 같다. 1. front, mid, rear 세 부분을 먼저 소트 해준다. 2. 만약 요소가 4개 이상으로 남아있다면, 기존의 퀵소트와 같은 방식으로 파티션을 해준다. -> 이 후, 피벗값의 자리를 기준으로 피벗값 앞, 피벗값 뒤를 다시 퀵소트 알고리즘을 호출해준다. 헷갈리는 내용이 많으니 아래 그림과 정리를 보면서 이해해보자. 1) pivot 값을 rear - 1 로 옮겨주는 이유는, 파티션 루프를 통해서 ..

일반 퀵소트 1. 파티션 함수를 통해 '피벗값'을 정한다. - 여기서 파티션 함수의 수행은 이러하다 1) 피벗값을 중심으로 왼쪽에는 피벗보다 작은 값을, 오른쪽에는 피벗보다 큰 값을 정렬한다. 2) 이를위해 left와 right이 배열을 따라 내려오면서, arr[left] > pivot 인경우와 arr[right] right 이 되는 경우, 즉 right과 left가 서로 교차하는 경우 루프를 멈추어준다. 4) 멈춘 곳에서 right과 우리가 정한 pivot의 자리를 바꾸어준다. 왜냐하면, pivot을 맨 첫번째 요소로 선택한다 했을때, pivot은 자신보다 작은 값과 바꾸어 져야하는데 pivot보다 작은 값을 마지막으로 가리키고 있는 것은 right이기 때문이다. 즉,pivot값 이렇게 위치해있으므로 ..

머지소트 머지소트의 원리는 '분할정복'이다. 1) 배열을 더이상 쪼갤 수 없을 때까지 쪼갠다 2) 쪼개진 배열을 병합, 정렬한다. 가장처음엔 1개로 이루어진 배열 두개를 정렬하여 길이가 2인 배열을만들고, 이를 또 길이가 2인 배열 두개를 병합/정렬하여 길이가 4인 배열을 만든다..-> 배열이 모두 병합/정렬될 때까지 한다. 머지소트는 재귀의 깊이가 O(log2N)이고, 각 재귀 당 비교 및 스왑연산이 평균적으로 n번수행된다고 보면, 시간복잡도는 O(Nlog2N) 이 되겠다. 머지소트의 최대 단점이라하면, in place 알고리즘이 아니라는 것이다. 즉, 머지소트는 외부의 다른 배열을 만들고, 그 배열에서 정렬한 후, 정렬된 값을 다시 원래의 배열로 옮겨줘야한다. public class Sort { st..

#include using namespace std; int solve(int n) { int sum = 0; int min = 0; if (n == 4 || n == 7) return -1; while (1) { while (sum n) { sum -= 5; min--;} //만약 넘었다면 5kg을 빼준다. while (sum > N; cout 자루의 무게가 N과 같다면 ->종료 2)자루의 무게가 N보다 크다면 -> 자루의 무게가 N보다 작거나 같아질 때 까지 자루에서 5kg를 뺀다. 3)자루의 무게가 N보다 작거나 같을 때 까지 3kg를 추가한다. -> 자루의 뭬가 N과 같다면 -> 종료 -> 자루의 무게가 N보다 커지게 되었다면 앞에서부터 다시시작