Twinparadox Factory

알고리즘 문제를 풀다 보면, 어떤 경우에는 데이터 처리에 앞서 정렬을 해야 하는 경우가 있다.그럴 때마다 정렬소스를 짜는 것이 비효율적일 뿐더러 정렬 이후 데이터 처리에 신경을 써줘야할 때문제의 시간복잡도를 고려해 퀵 정렬 등을 짜고 있는 건 생산적이지 못하다고 느꼈다.정렬에 대해 자세히 아는 건 좋지만, 그걸 실용적으로 활용하는 것도 중요하다는 이야기다. C언어를 주로 썼을 때는, qsort를 사용했다.(이부분에 대해서는 다른 포스팅에서 소개하겠다.) C++에서는 sort를 사용하면 빠른 시간 내에 정렬된 결과를 받을 수 있다.성능 측면에서는 다른 함수에 비해서는 준수한 수준이다. 이 성능에 대한 진 단순히 퀵 정렬만으로 구성한 정렬이 아니라 복합적으로 힙정렬, 삽입정렬도 섞여 있기 때문이다. 아래 사..

입력 받은 배열을 O(n)으로 히프 트리 구조로 생성할 수 있지만, 여기서는 일단 O(nlogn)으로 진행되는 히프트리 구성을 실시했다. (이 부분에 대해서는 차후 포스팅할 생각) 최대 히프트리를 구현했고, 최대 히프트리를 바탕으로 오름차순 정렬을 하는 코드다. 내림차순 정렬을 보고 싶다면, list 배열에 넣는 인덱스 순서만 바꿔주면 되고 공부 삼아 최소 히프트리를 구현하는 것도 나쁘지 않을 것이다. 숙련자가 보기에는 이 소스는 잘 짜여진 소스는 아니라는 것을 말해주고 싶다. 처음 자료구조를 배우던 시절 구조에 대해서만 깨우치고 만든 소스라서, 불필요한 메모리 할당도 있고 히프 트리 구성에서 시간 복잡도 손실을 보기는 하지만, 히프트리를 바탕으로 힙정렬(혹은 히프정렬)을 구현하는 것까지는 문제되지 않아..

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

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

C++로 알고리즘 문제를 풀거나 이런 저런 이유로 코딩을 하다 보면 vector를 사용하게 되고 이 vector 내에 들어가는 값들을 정렬하기 위해서 직접 정렬을 구현해주는 방법도 있지만 좀 더 최적화되어 빠른 속도로 정렬을 수행해주는 sort함수를 사용하게 된다. 요소의 상대적 위치가 바뀌지 않는 걸 원한다면, stable_sort를 사용하면 된다. 통상적으로 자료형이 하나(예를 들어 int 하나)만 들어가는 vector라면, 시작점과 끝만 정해주면 알아서 오름차순 정렬을 수행해버리기 때문에 문제가 되지 않지만, vector 배열에 들어가는 정보가 여러 가지 자료형이 섞여 있는 구조체이고 그 구조체 안의 변수를 기준으로 정렬을 수행해야 한다면, 갑자기 머리가 아파온다. 대부분 레퍼런스를 참고하지 않거나..