sort5 [Problem Solving] BOJ 1431 : 시리얼 번호 문제 링크 : https://www.acmicpc.net/problem/1431 다음과 같은 기준으로 문자열 리스트를 정렬하는 문제이다.1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다.2. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다. 우선 serealList = sorted(serealList, key=len)으로 짧은 문자열을 앞쪽으로 오게 한다.그 다음 compare 함수를 기준으로 Bubble Sort를 수행한다. compare(A, B) 함수는 다음과 같이 동작한다.1. 문자열의 길이가 .. 2025. 2. 7. [Computer Algorithms] Heap Sort (힙 정렬) Heap 힙의 대한 설명은 다음 글을 참고하자.https://junstory314.tistory.com/entry/Data-Structures-Heap-%ED%9E%99 [Data Structures] Heap (힙)Priority Queue (우선순위 큐) 우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료 구조이다. 우선 순위 큐는 배열이나 연결 리스트로 구현할 수 있지만 데이터의junstory314.tistory.com Heap Sort 힙 자료구조를 활용한 정렬이다.1. 정렬하고자 하는 배열을 힙 구조로 변경한다. -> 시간 복잡도 : O(N)2. 우선순위가 가장 높은 힙의 루트를 힙의 맨 끝으로 보내며, 이를 힙에서 제외한다. -> 시간 복잡도 : O(logN.. 2024. 7. 18. [Computer Algorithms] Sorting in Linear Time : Counting Sort and Radix Sort (계수 정렬과 기수 정렬) Counting Sort (계수 정렬) counting 배열에 정렬하고자 하는 배열의 있는 원소들의 개수를 저장한다. counting 배열의 누적합을 구하면, 누적합의 i번째 값은 i가 정렬된 배열에서 끝나는 인덱스에 1을 더한 값을 의미한다. 따라서 counting[v[i]] - 1이 v[i]가 정렬되었을 때 위치해야 할 인덱스가 된다.#include #include using namespace std;int N;vector v;void input(){ cin >> N; for (int i = 0; i > num; v.push_back(num); }}void countingSort(){ int max_val = *max_element(v.begin(), v.end.. 2024. 7. 13. [Computer Algorithms] Sorting Using Divide and Conquer : Merge Sort and Quick Sort (합병 정렬과 퀵 정렬) Divide and Conquer (분할 정복)큰 문제를 작은 문제 단위로 분할하여 해결해나가는 방식, 이 방식을 통해 구현한 정렬 알고리즘은 대표적으로 Merge Sort와 Quick Sort가 있다. Merge Sort (합병 정렬)배열을 반으로 쪼갠 후, 다시 합병시키면서 정렬해 나가는 방식이다. 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수 있다.#include #include using namespace std;int N;vector v;vector sorted;void input(){ cin >> N; v.resize(N); sorted.resize(N); for (int i = 0; i > v[i.. 2024. 7. 8. [Computer Algorithms] Basic Sorting Algorithms : Bubble Sort, Selection Sort, and Insertion Sort (거품 정렬, 선택 정렬, 삽입 정렬) 1. Bubble Sort (거품 정렬)서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 매 회전마다 회전 구간에서의 최댓값이 최우측으로 간다.void bubbleSort(){ for (int i = 0; i v[j]) { int temp = v[j - 1]; v[j - 1] = v[j]; v[j] = temp; } } }}Best case : O(N^2) (이미 정렬 되어 있어도 버블이 이동하며 대소 비교는 계속 함)Average Case : O(N^2)Worst case : O(N^2) - 장점1. 구현이 매우 .. 2024. 7. 2. 이전 1 다음
