문제 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 풀이 방식 문제 자체는 쉬워서 풀이할것도 없다. C++과 같은 경우 vector을 사용해 algorithm.h 에 내장된 sort 함수를 사용해주면 된다. 다만 문제가 되는 부분은 이 부분이다. // case 1 for (int i = 0; i < n; i++) cout v[i]; sort(v.begin(), v.end()); for (int i = 0; i ..

문제 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 설명 아래와 같은 조건으로 나열하면 된다. 1. 길이가 짧은 것 부터 2. 길이가 같다면 사전 순으로 3. 중복은 제거한다. 풀이 방식 알고리즘 적으로 적어둘만 한건 없는 것 같다. 솔루션 #include #include #include using namespace std; bool compare(string a, string b) { if (a.length() != b.length()) return a.length() < b.length(..

병합 정렬(Merge Sort) [의미] 전체 원소를 하나의 단위로 분할한 후 분할한 원소들을 다시 병합하는 정렬 [특징] 분할 단계와 병합 단계로 나뉘어져 있으며, 분할 단계는 시간복잡도에 포함하지 않음. Stable한 정렬 (중복된 데이터의 순서가 바뀌지 않는 정렬) [Big O] Best - O(nlog₂n) Worst - O(nlog₂n) [장점] 데이터의 분포에 영향을 적게 받음. 크기가 큰 레코드를 정렬할 경우 연결 리스트(Linked List)를 사용한다면, 링크 인덱스만 변경됨으로 데이터의 이동이 엄청나게 적어지고 In-Place정렬로 구현할 수도 있다. [단점] 레코드를 배열(Array)로 구현하면 Not-In-Place 정렬이 되며 추가적인 별도의 메모리를 필요로 하게 된다. [구현] ..

정렬 알고리즘 [의미] 무작위로 섞여있는 데이터를 어떠한 기준에 맞추어 정리하는 알고리즘. [사용하는 경우] 각종 데이터의 목록을 정리하고 싶을 때 분포도의 중위값을 알아내고 싶을 때 데이터에서 중복 값을 파악하고 싶을 때 이진 탐색을 하려고 할 때 [공부하는 이유] 기본적으로 제공되는 시스템 정렬(sort 매서드)이 항상 좋은 퍼포먼스를 보장하지는 않음. 환경과 상황에 걸 맞는 정렬을 사용하는 것이 중요하기 때문. 버블 정렬(Bubble Sort) [의미] 인접한 두 개의 데이터에 크기를 비교한 후 대소관계에 따라 두 값의 교환여부를 판단하는 알고리즘. [특징] N번째 정렬 회차가 끝나면, 뒤에서 n번째 자리의 데이터가 확정됨. Stable한 정렬 (중복된 데이터의 순서가 바뀌지 않는 정렬) [Big ..