sleep sort, 슬립 정렬이라고 2년 전이였나? 3년 전에 꽤 핫했던 친구가 있습니다. 사실 왜 Hot했는지는 이해가 가지 않습니다. 아이디어 정도만 보시고 넘어가셔도 무난할 듯 싶어요. 대략적인 구조를 보면, worker 역할을 하는 객체에게 몇 단위시간 동안 sleep 할 건지 그러한 정보를 넘겨주고, 해당 객체가 몇 단위 시간 동안 깨어나면 출력하는 식으로 프로그램을 짜는 듯 싶습니다. 더 쉽게 말하면, 길이가 n인 데이터가 있을 때, worker_i는 arr[i] 단위시간 만큼 잠이 듭니다. t만큼 시간이 지났을 때, t만큼 잠들어야 하는 worker들이 모두 깨어나면서 t를 출력하는 것입니다. 단위 시간이 매우 작다면, 꽤 효율적일 겁니다. 코드는 생각보다 짧은데요. 많이 찾아볼 수 있는 ..
자료알고/알고리즘 검색 결과
비교 기반 정렬은, 키 2개를 가지고 비교를 하는 것들을 말합니다. 예를 들어서, 우리가 sort 함수를 호출할 때 이런 식으로 compare 함수를 재작성을 합니다. 그러면 이것은 key a와, b를 비교한 것입니다. 대다수의 정렬은 이 키 값 2개를 비교해서 순서를 ordering 한다고 보시면 됩니다. 물론 예외가 몇 개 있는데요. 카운트, 버킷, 기수 정렬 등이 예외입니다. 크기가 n인 배열이 있습니다. 물론, 이 n개의 수는 서로 다른 수라고 합시다. 보통 그렇게들 많이 주어지니까요. 그러면, 서로 다른 수 n개를 순서 고려해서 배열하는 가짓수는 n!입니다. 즉, 길이가 n인 순열이 n!개가 나온다는 것입니다. 예를 들어서 n = 4라고 해 봅시다. 그러면 1번째 칸에는 4개 중 하나만 들어가면..
오늘은 간단하게, 최대 공약수와 최소 공배수를 구하는 알고리즘을 알아보도록 하겠습니다. 먼저 a와 b의 최대 공약수란, a와 b를 동시에 나누어 떨어지게 하는 최댓값을 의미해요. 예를 들어서 a가 6이고 b가 3이라면 3이 gcd가 됩니다. 그렇다면 가장 간단한 알고리즘을 생각해 볼 수 있습니다. a와 b의 최솟값을 r이라고 해 봅시다. r부터 1까지 계속 a와 b를 나누어 보면서, 만약에 두 수를 동시에 나누는 수가 있다면 break를 걸어버리는 겁니다. 사실, 이러한 방법은 꽤 효과적일 수 있습니다. 그런데 a = 20억, b = 10억 7 정도가 된다고 하면, 수행 시간이 상당히 길어질 겁니다. 왜냐하면 b는 소수이기 때문입니다. b를 나누는 수는 1과 10억 7밖에 없는데, 20억을 나누는 수는 ..
약수를 구하는 것은, 정수론 문제를 풀 때 기본이 되는 연산 중 하나입니다. 우리는 약수를 구하는 알고리즘을 다음과 같은 구현을 생각할 수 있을 겁니다. 이것은 간단합니다. n의 약수를 구할 때, 나누는 수를 1부터 n까지 모두 검사해 봅니다. 만약에 n을 나누는 수 r로 나눴을 때, 나머지가 0이라면, r로 나누어 떨어지는 겁니다. 이것은 올바른 결과를 냅니다. 하지만, 오래 걸립니다. 예를 들어서, n의 값이 10^12만 되어도 아래와 같은 연산을 10^12번 해야 할 겁니다. 10^12번. 상당히 끔찍하지 않나요? 1초에 단순 연산을 10^9회 정도 한다고 한다면, 1000초, 약 20초, 어마무시한 시간이 걸려버립니다. 이 끔찍한 시간을 줄일 수 있는 방법이 없을까요? Lemma 하나 들고 옵시다..
오늘은 기수 정렬에 대해서 알아보도록 하겠습니다. 이것은 키 2개를 가지고 비교하는 정렬이 아닌데요. 이 특성은 저번에 배운, counting sort의 '2개의 키 값을 비교'하는 '비교 기반 정렬이 아니다' 라는 성질을 가지고 있습니다. 이들과, merge sort는 키 2개를 직접 비교하는 비교 기반 정렬이냐, 아니냐의 차이가 있어요. 아래 두 개의 글을 잘 보셔도 눈치를 채실 수 있을 듯 싶습니다. [관련글] 빈도를 저장하는 counting sort. 알아봅시다. 정렬된 두 배열을 합치는 합병 정렬 알아보아요. 그러면, 이것은 어떻게 동작할까요? 저는 1가지 용어만 정의하겠습니다. b진법으로 잡고 정렬한다. 버킷의 갯수가 b개이다. 우리는 양의 정수를 표현할 때, x진법으로 표현할 수 있습니다. ..
최근댓글