정렬 검색 결과

해당 글 14건
힙 정렬 (heap sort) : 최악의 경우에도 O(nlogn)이다.

오늘은 힙 정렬, Heap sort에 대해서 배워보도록 하겠습니다. 어렵지 않으니, 천천히 따라오시기만 하면 됩니다. 저번에, 우선순위 큐라는 자료구조를 배우셨을 거에요. 이 구조를 이용해서 정렬한 것입니다. 이게 끝입니다. 어렵지 않죠? 제가 우선순위 큐를 설명했을 때, 깜빡 잊은 것이 하나 있어요. 이것은, 이진 포화 트리를 만족한다는 것입니다. 그렇기 때문에, 트리의 깊이는 log(들어간 원소의 갯수)에 비례합니다. 그러면, 이것을 어떻게 구축할지가 문제입니다. Root를 0번 인덱스라고 합시다. 그리고 0번의 자식은 1, 2번이라 합시다. 그리고 1번의 자식은 3, 4번이라 합시다. 즉, 어떠한 노드 k가 있다면, 그들의 child는 2k+1과 2k+2가 됩니다. 그러면, 우선 순위 큐에 들어가는..
자료알고/알고리즘 2019. 12. 19. 21:17
셀 정렬 : 갭을 줄여가면서 해결한다.

삽입 정렬의 복잡도는 O(n^2)입니다. 물론 평균 복잡도 또한 O(n^2)입니다. 물론, memcpy 등으로 실행 시간을 빠르게 할 수 있는 여지는 있지만, 거기까지일 뿐입니다. 다만, insertion sort의 장점도 있는데요. 거의 정렬된 데이터에 대해서는 상당히 빠르게 동작한다는 장점이 있어요. 하지만, 한 번에 한 요소씩. 비교 1번 할 때 마다, 1요소씩만 move 하기 때문에 효율적이지 않은데요. 이를 보완하기 위해서 gap이라는 변수를 둡니다. 그러면 먼저 init 함수를 봅시다. 먼저, si 라는 벡터가 있습니다. 여기에 무슨 값들이 들어있는지 봅시다. 1, 4, 13, 40, 121, 361, 1093, 3280, ... 네. 이런 값들이 들어 있는데요. gap으로 쓸 겁니다. 예를 ..
자료알고/알고리즘 2019. 10. 14. 01:24
팬 케이크 정렬 : 위에서부터 k개를 뒤집는다.

팬케이크 정렬은 유튜브에서 영상으로 한 번 쯤은 보셨을 겁니다. 이것을 최소한으로 뒤집는 횟수를 구하는 것은 경시 대회 이상에서 나올 만한 문제입니다. 우리는 단지, 어떻게 잘 뒤집어서 정렬을 잘 시키면 됩니다. 팬 케이크 더미에서는 위에서 k개만 뒤집을 수 있습니다. 단, k는 총 갯수보다 작을 거에요. 갯수를 n개라고 한다면 2n-3번 이하 뒤집어야 합니다. 이 때에는 어떻게 해야 할까요? 사실, 잘 모르겠습니다. 일단, 1회전이 끝날 때 마다, 2회의 단위 연산을 수행해야 한다는 것은 알겠습니다. 그러면 한 회전마다 어떤 일이 일어나면 좋을까요? 팬 케이크가 이런 식으로 쌓여 있다고 생각해 봅시다. '위에서 k개를 뒤집는다'는 연산 특성상, k가 n이 아니라면, 맨 아랫쪽에 있는 것은 움직이지 않습..
자료알고/알고리즘 2019. 9. 17. 13:29
mysql order by : 결과 값을 어떤 기준으로 정렬할까?

오늘은 mysql에서 결과값을 정렬하는 방법에 대해 알아봅시다. order by를 쓰면, 레코드를 특정한 기준으로 정렬을 하게 합니다. 쓰는 방법은 아래와 같습니다. ... order by col_name(1) g(1), col_name(2) g(2), ... , col_name(n) g(n) 이 때, 1차 정렬 기준은 col_name(1) 값을 기준으로 g(1)이라는 기준으로, 2차로 col_name(2) 값을 기준으로 g(2)라는 기준으로, ... 요런 식으로 sorting을 하게 됩니다. 컬럼 기준을 주지 않을 수도 있는데요. 이 때에는 오름차순으로 정렬이 됩니다. 예제를 몇 개 봅시다. 먼저 city 함수에 있는 데이터들을 모두 출력해 보겠습니다. 아. 너무 많군요. 자. 일단 저는 Populat..
코딩/Sql 2019. 8. 30. 18:00
next_permutation : 3단계 최적화를 하면서 분석해 보자.

코딩 테스트에서 next_permutation의 사용 빈도는 상당히 높을 겁니다. 특히 역량 테스트라고 불리는 것에서는요. 구현이 들어가면 대략 50% 정도는 조합, 순열 등에서 나오는데요. 그 때, 이전 순열이라던지 다음 순열을 구하기 위해서 쓰는 함수가 저 함수입니다. 이전 순열은 데이터를 조금 변형을 하면 구할 수 있고요. 그러면 이 함수가 어떻게 구현이 되어 있을까요? 만약에 레퍼런스 없이 구현하라고 하면 어떻게 해야 할까요? 단계별로 이해해 봅시다. 사실 이 함수의 복잡도는 O(n)입니다. 왜 그렇게 나올 수가 있는 것인지, 상대적으로 비효율적인 구현 방법으로 먼저 구현해 보고 이야기 하도록 하겠습니다. O(n^2)의 핵심 접근은, 결정 함수입니다. 이게 무슨 어려운 것이냐라고 생각하실 수도 있..
레퍼런스/분석 2019. 8. 19. 17:59