Twinparadox Factory

시간 제한 : 1초메모리 제한 : 128MB 입력첫째 줄에는 반의 학생들의 수 N (3 b.three) return true; else if (a.three == b.three) { if (a.two > b.two) return true; else return false; } else return false; } } int main(void) { int n, tmp; cin >> n; vector arr(n, { 0,0,0,0,0 }); for (int i = 0; i < 4; i++) arr[i].idx = i; for (int i = 1; i tmp; if (tmp == 1) arr[j].one++; else if (tmp == 2) arr[j].two++; else arr[j].three++; ar..

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

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

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