👨‍💻 ModernAlchemist 허브의 개발 일지

안녕하세요 주인장 H입니다. 지금까지 선택, 버블, 삽입, 퀵, 병합, 힙 정렬의 개념을 공부해보았고, 가장 빼운 정렬은 O(N * log N)이 나오는 퀵, 병합, 힙 정렬 이였습니다. 하지만 이보다 더욱 빠른 정렬을 진행해야 한다면 어떻게 해야할까요 다음의 3 이하의 데이터 자연수들을 오름차순으로 정리하세요 1 3 2 3 1 2 3 2 1 3 10개의 데이터가 모두 3안에 있는걸 알 수 있는데요. 이처럼 범위조건이 있는 경우에 한해 굉장히 빠른 알고리즘 입니다. 속도는 O(N)입니다. 계수정렬은 크기를 기준으로 갯수를 세면 어떨까? 란 발상에서 시작합니다. 즉 세개의 배열을 만들고 1이면 arr[0]++ 3이면 arr[2]++ 이런식으로 숫자를 세주면 됩니다. 그러면 숫자의 갯수가 세질테고 1을 ar..

안녕하세요 주인장 H입니다. 오늘은 기존에 배운 정렬보다 좀더 빠르고 쉽게 정렬을 진행하려 합니다. sort함수는 기본적으로 quicksort와 유사하게 진행 되지만 차이점으로 O(log N * N)가 보장된다는 장점이 있죠 간단하게 예시 코드를 보겠습니다. #include #include using namespace std; class Student { public: string name; int score; Student(string name, int score) { this->name = name; this->score = score; } //정렬 기준은 '점수가 작은 순서' bool operator score < student.sco..

안녕하세요 주인장 H입니다. https://www.acmicpc.net/problem/2752 2752번: 세수정렬 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. www.acmicpc.net 동규는 세수를 하다가 정렬이 하고싶어졌다. 숫자 세 개를 생각한 뒤에, 이를 오름차순으로 정렬하고 싶어 졌다. 숫자 세 개가 주어졌을 때, 가장 작은 수, 그 다음 수, 가장 큰 수를 출력하는 프로그램을 작성하시오. 입력 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. 출력 제일 작은 수, 그 다음 수, 제일 큰 수를 차례대로 출력한다. 예제 입력 1 3 1 2 예제 출력 1 ..

안녕하세요 주인장 H입니다. https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하..

안녕하세요 주인장 H입니다. https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 1 복..

안녕하세요 주인장 H입니다. 오늘은 퀵정렬에 대해 알아보겠습니다. 지금까지 배운 정렬은 시간복잡도 O(N^2)를 가진 알고리즘 이였습니다. 처리할 데이터가 많다면 사용하기에 부담이 되겠지요. 그렇기에 대표적인 빠른 알고리즘이 바로 퀵정렬입니다. 퀵정렬은 대표적인 분할 정복 알고리즘으로서 평균속도가 O(N*log N)입니다. 1~10까지의 무질서한 숫자를 오름차순으로 정리한다고 할때, 퀵 정렬은 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬합니다. 특정한 값(피벗pivot)을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눕니다. 예를들어 (1) 10 5 8 7 6 4 3 2 9 라는 숫자가 있다고 가정합니다. 이 경우 1보다 큰 숫자를 왼쪽에서, 1보다 큰 숫자를..

안녕하세요 주인장 H입니다. 오늘은 버블정렬에 대해 알아보겠습니다. 버블 정렬은 1~10까지의 무질서한 숫자를 오름차순으로 정렬한다라고 할때, 자신보다 큰 수가 왼쪽에 있다면 자리를 서로 바꾸면 어떨까?란 아이디어에서 시작합니다. 버블 정렬은 정렬 알고리즘 중에서 가장 쉽지만 가장 비효율적인 알고리즘 입니다. 이 과정에서 각 싸이클마다 가장 큰 값이 맨 뒤로 보내지게 됩니다. 컴퓨터 내부적인 연산이 가장 비효율적으로 일어나게 되어 실제 수행시간이 가장 느린 안 좋은 알고리즘입니다. 시간복잡도는 선택정렬, 삽입정렬과 동일한 O(N^2)입니다. #include int main(void) { int i, j, temp; int arr[10] = { 1,3,2,5,7,6,10,9,8,4 }; for (i = 0..

안녕하세요. 주인장 H입니다. 오늘은 삽입 정렬에 대해 알아보겠습니다. 오름차순으로 무질서한 1~10 을 정렬한다고 했을때, 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 풉니다. 다른 정렬과 비교해 본다면 삽입 정렬은 필요할 때만 위치를 바꾸게 됩니다. 삽입 정렬은 기본적으로 정렬이 되어있다고 가정 했을 때 굉장히 빠른 속도를 자랑합니다. 소스 코드 상 반복문이 두 번 들어가 있다는 점에서 시간 복잡도는 O(N^2)입니다. #include int main(void) { int arr[10] = { 1,3,2,5,7,6,10,9,8,4 }; int i, j, tmp; for (i = 0; i = 0 && arr[j] > arr[j + 1]) { tm..

안녕하세요. 주인장 H입니다. 오늘은 선택정렬에 대해서 알아볼건데요. 1~10 까지 무질서한 숫자를 오름차순으로 정렬한다. 라고 한다면 선택정렬은 가장 작은 것을 선택해서 제일 앞으로 보내면 어떨까? 라는 고민에서 시작했습니다. 가장 기초적인 정렬이라고 할 수 있습니다. 선택정렬은 대략 N* (N+1)/2 번의 연산을 수행하는데요. 빅 오 표기법으로 하게된다면 O(N^2)가 됩니다. 즉, 선택 정렬의 시간 복잡도는 O(N^2). // 1 ~ 10 까지 정렬 하기 #include int main(void) { int arr[10] = { 1,3,2,5,7,6,10,9,8,4 }; int i, j, index, temp; for (i = 0; i < 10; i++) { int min = 11; for (j ..