📌 퀵정렬 퀵정렬은 가장 널리 쓰이는 정렬 알고리즘으로 말 그대로 빠른 정렬이 가능하다. 퀵 정렬도 병합정렬과 마찬가지로 분할정복기법을 이용한 알고리즘이다. 퀵 정렬의 핵심 아이디어는 특정 원소를 기준으로 작은 데이터와 큰 데이터를 분류한다는 것이다. 이렇게 되면 특정 원소를 기준으로 순서가 결정되며 분류된 작은 데이터와 큰 데이터 안에서 각각 기준 원소를 다시 정해 재귀적으로 쪼개나가면서 정렬해나간다. 병합정렬과 마찬가지로 단위를 쪼개나가는 아이디어이므로 분할정복기법이라고 할 수 있다. 이때 생각해봐야 할 것은 기준이 되는 원소(pivot)를 어떻게 정하느냐 인데, 1) 첫번째 원소를 기준으로 하거나 2) 랜덤으로 원소를 선택한다 첫번째 원소를 기준으로 할 경우 이미 정렬된 리스트의 경우 피봇의 한쪽에..
🧨 문제 출처 문제 출처 : 백준 2752번 문제 난이도 : 브론즈 4 문제 링크 : www.acmicpc.net/problem/2752 2752번: 세수정렬 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 세 개의 수를 입력해 오름차순 정렬하는 문제다. 사실상 N개의 수를 입력해 오름차순 정렬하는 것과 별반 다르지 않은 문제인데 왜 브론즈 4인지는 의문이다. 다른 방법으로 더 간단하게 구현하는 방법이 많을 거다. 사실 3개의 수라면 복잡하게 정렬 알고리즘을 따지지 않고 2번 또는 3번만 비교해도 대중소를 가려낼 수 있긴 하다. 정렬 알고리즘 공부하면서 구현한거라 그냥 병합..
🧨 문제 출처 문제 출처 : 백준 2750번 문제 난이도 : 브론즈 1 문제 링크 : www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 시간복잡도 O(n^2) 을 가지는 삽입, 버블 정렬을 이용하면 시간초과가 날지 궁금해서 삽입, 버블로 구현해 제출하니 다행히 시간초과 오류가 나진 않았다. 다른 c++ 코드는 0ms 도 많던데 아마 퀵이나 병합정렬을 이용하면 간단하게 줄어들 거 같다. #include #include using na..
