시나브로

퀵 정렬은 평균적으로 O(nlogn)의 시간복잡도를 가지고 있다. 퀵 정렬은 기준의 되는 피봇을 설정하고 그것을 기준으로 값들을 swap하면서 sort 하는 것이다. #include #include using namespace std; int list[20] = { 0 }; void swap(int i, int j) { int temp = list[i]; list[i] = list[j]; list[j] = temp; } void quick_sort(int left, int right) { if (left > right)return; int pivot = right; int i = left; int j = right; while (i < j) { while (list[i] < list[pivot]) i++..

처음에는 짠돌이를 생각하다가 "like Scrooge(스크루지 - 짠돌이의 대명사)"라고 말하면 짠돌이를 잘 표현했다고 생각했다. 하지만, 원어민이 말하길 like scrooge는 매우 올드한 표현이라고 한다. 그렇기에 like scrooge 말고 fluger 또는 stingy 라고 표현하는게 맞다고 한다. fluger의 사전적 정의는 검소한이다. 짠돌이 같다는 표현을 좋게 말하면 검소한이다. 그러니 좋게 말하고 싶을 때, fluger이라고 하자!! stingy의 사전적 정의는 인색한이다. fluger와 대조되게 stingy는 안좋은 의미의 짠돌이이다. 그러니 말할 때, 유의해서 말하자!

만약 해싱을 공부하고자 하면 이 문제를 필수적으로 풀어보길 바란다. 해싱의 기본개념도 알 수 있고 간단한 구현도 가능하다. 구현의 경우, 문제를 그대로 구현하면 된다. 여기서 31은 영어 최대 숫자인 26보다 큰 소수이기 때문에 설정하였다. (이 숫자는 소수를 사용하는 것이 좋을 것 같다.) 또한, 1234567891도 소수이다. #include int main(void) { freopen("inp.inp", "r", stdin); freopen("out.out", "w", stdout); char buffer = 0; int number = 0; scanf("%d", &number); scanf("%c", &buffer); long long sum = 0; int box = 0; long long li..

힙을 사용하면 금방 성공할 거 같았는데 진짜 많은 오류에 직면한 문제이다. 처음에는 N개의 노드를 가진 최소힙을 만들어서 구현하였지만, 자꾸 틀렸습니다라고 해서 도데체 무슨 오류인지 몰라서 고민하다가 책을 참조해보니 부모노드가 pointer/2가 아니라 (pointer-1)/2라는 것을 알게 되었다. 그래도 계속 틀렷다고 해서 모든 값을 가진 최대힙을 구현해서 n만큼 pop울 해줬다. 아직까지도 왜 처음 시도였던 n개의 최소힙이 성공이 안 됫는지 모른다. 부모 노드는 (pointer-1)/2이다!! #include int list[2250010] = { 0 }; int pp = 0; void swap(int i, int j) { int temp = list[i]; list[i] = list[j]; lis..