Twinparadox Factory

항상 고민하던 게 있다.비교 정렬의 하한이 nlogn이며 이보다 더 좋은 정렬 알고리즘은 없다는 이야기를 들었다.도대체 왜 그런 것인지, 어째서 그런 것인지에 대해서 잘 모르고 넘어갔다.주어진 문제에 대해서 시간 복잡도의 하한이라는 것은어떤 문제도 이 하한보다 빠르게 구할 수 없다는 것을 의미하는데,이 하한이 알고리즘에 대한 시간 복잡도가 아니라이 문제의 고유 특성으로 인해서 과거부터 지금까지, 혹은 미래에 만들어진어떤 효율적인 알고리즘이더라도 적어도 하한의 시간복잡도 만큼 걸린다는 것을 의미한다. n개의 숫자가 저장된 배열이 있다고 하자.여기서 최솟값을 찾는 문제의 하한은 최소한 n-1회의 비교가 필요하므로 n-1이다.이런 식으로 n개의 수를 비교 정렬할 때 필요한 최소 비교 횟수가 어떻게 되는지 생각..

기수 정렬은 흔히 알고 있는 비교 정렬들과는 조금 다른 정렬로 볼 수 있다.숫자를 부분적으로 비교하는 정렬이기 때문에,제한적인 범위 내(제한적인 크기 혹은 자릿수)에 있는 숫자들에 대해서 자릿수별 정렬을 시행하는 알고리즘으로,제한적인 상황 내에서는 어떤 비교 정렬 알고리즘에 비해서 속도가 월등하다는 장점을 가지고 있다.단점은 직전에 말했듯, 제한적인 상황에 유효하다는 것이다. 089, 035, 131, 907, 910이라는 숫자가 들어왔다고 하자.이들 입력에 대해서 각각의 자릿수(1의 자리, 10의 자리, 100의 자리)를 기준으로 정렬을 시행한다.이 때, 작은 단위의 자릿수부터 큰 단위의 자릿수로 정렬한다. 내림차순 정렬을 시행한다고 하자. input089070131907910 1의 자리 0899071..

외부정렬(External Sort)은 입력 크기가 매우 커 읽고 쓰기가 오래 걸리는 보조 기억 장치에저장할 수밖에 없는 상태에서 수행되는 정렬이다.통상적으로 주기억장치에서 다룰 수 있는 크기의 데이터를 다루던기존의 정렬은 내부정렬(Internal Sort)로 분류한다. 예를 들어, 주기억 장치 용량이 1GB라면, 데이터의 크기가 극단적으로 128GB라고 하자.이런 경우에는 주기억 장치에 데이터를 모두 올릴 수는 없는 상황이라어떤 내부 정렬 알고리즘으로도 직접 정렬할 수는 없어 보조기억장치(HDD,SDD)를 이용해야 한다. 그렇다면 이제 입력을 분할해 주기억 장치가 수용 가능한 만큼의 데이터에 대해내부 정렬을 수행하고 다시 이를 저장하는 방법을 반복하여,점진적으로 크기를 늘려나가는 방식을 고려해야 한다.내..

Algorithm] 합병 정렬(Merge Sort) 합병 정렬은 대표적인 분할정복 방법(Divide and Conquer)을 사용한다.더 이상 부분 문제로 만들 수 없는 수준까지 분할한 뒤,이를 다시 취합하는 과정에서(정복) 정렬이 이루어지는 정렬 알고리즘이다. 일단 백문이불여일견이니 이것이 작동하는 과정을 그림으로 한 번 살펴보자. 파란색은 정렬이 완료되지 않은 부분문제, 즉 분할 대상이고주황색은 정렬이 완료된 부분문제로 정복 및 정복 대상이다.과정을 보면 알 수 있듯, 다시 한 번 말하지만 합병 정렬은 정복 과정에서 정렬이 이루어진다. 의사 코드를 한 번 살펴보자. MergeSort(arr,start,end)입력 : arr[start] ~ arr[end]출력 : 정렬된 arr[start] ~ arr[..