🗒️ sort (9)

1. 2022.06.28 [Python] 정렬(Sort) : 선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬

   정렬(Sort) 정렬의 기본 정렬의 개념 정렬(Sort) : 자료들을 일정한 순서대로 나열하는 것 순서대로 나열할 때는 작은 것부터 나열하는 방법(오름차순)과 큰 것부터 나열하는 방법(내림차순)이 있다. 오름차순 정렬(Ascending Sort) : 작은 것부터 큰 순으로 나열된 방법 내림차순 정렬(Descending Sort) : 큰 것부터 작은 순으로 나열된 방법 정렬의 대표적인 예 : 사전 정렬 알고리즘의 종류 오름차순 정렬이든 내림차순 정렬이든 결과의 형태만 다를 뿐, 같은 방식으로 처리된다. 정렬하는 방법에 대한 알고리즘은 수십 가지이다. 이해하고 구현하기 쉽지만 속도가 느린 알고리즘 이해와 구현이 어렵지만 속도가 빠른 알고리즘 특수한 상황에서만 효율적인 알고리즘 메모리를 적게 사용하는 알고리즘..
2. 2022.06.28 [Python] 1차원/2차원 배열의 중앙값 계산하기

   1차원/2차원 배열의 중앙값 계산하기 들어가며 이용하여 1차원 또는 2차원 배열의 중앙값을 계산해보자. 2차원 배열의 경우, 1차원 배열로 만든 후, 정렬하는 방법을 사용한다. 중앙값(Median) 데이터를 일렬로 정렬해서 나열한 후, 나열된 숫자의 가운데에 위치하는 값을 대푯값으로 하는 방법 중앙값을 구하려면 우선 데이터를 오름차순 또는 내림차순으로 정렬해야 한다. 데이터의 개수가 짝수 개인 경우, 중앙값을 (개수/2) 또는 (개수/2 - 1) 어느 것을 해도 된다. 프로그램 구현 ① : 1차원 배열의 중앙값 계산하기 선택 정렬(Selection Sort)을 이용하여 중앙값을 계산해본다. def selectionSort(ary) : n = len(ary) for i in range(0, n-1) : m..
3. 2021.11.14 [컴퓨터활용능력 1급 실기] 부분합 / 정렬 (액셀/스프레드시트)

   부분합 / 정렬 (액셀/스프레드시트) 개념 부분합 : 입력된 데이터를 특정 필드를 기준으로 그룹화해서 각 그룹에 대한 통계를 계산하는 기능 부분합을 계산하기 전에 먼저 할 일 부분합을 구하려는 항목을 기준으로 데이터를 정렬하여 데이터 그룹 만들기 정렬(Sort) 기능을 이용하여 특정 기준에 따라 순서대로 데이터를 나열할 수 있음. 정렬 기준이 1가지인 경우 [데이터] -> [정렬 및 필터] -> [오름차순 정렬] [데이터] -> [정렬 및 필터] -> [내림차순 정렬] 정렬 기준이 2가지 이상인 경우 반드시 [데이터] -> [정렬 및 필터] -> [정렬] 을 이용하여 정렬 수행 사용 방법 정렬 Excel [데이터] 탭 -> [정렬] 그룹 -> [정렬] 부분합 Excel [데이터] 탭 -> [개요](Exc..
4. 2021.06.07 선형 시간 선택(Linear Time Selection)

   선형 시간 선택(Linear Time Selection) 각 단계에서 문제를 2개 이상 분할하여 문제를 해결하는 알고리즘 ① 벡터 $V$가 주어지면, 여기서 i번째로 작은 원소를 찾으려고 함. ② 입력 벡터 $V$를 $V_{1}, V_{2}, V_{3}, ..., V_{n/5}$ 으로 분할함. 각각의 부분 벡터 $V_{i}$ 는 5개의 원소를 가지고 있음. 마지막 $V_{n/5}$ 는 5개 이하의 원소를 가질 수 있음. ③ 각각의 $V_{i}$ 를 정렬함. ④ 각각의 $V_{i}$ 에서 중앙값 $m_{i}$ 를 구하고, 이를 모아서 집합 M을 생성함. ⑤ 집합 M에서 중앙값 q를 찾음. ⑥ q를 피벗으로 삼아 전체 벡터 V를 L과 R의 두 벡터로 분할함. ⑦ 이러한 방식으로 분할하면 부분 벡터 L은 q보..
5. 2021.06.02 [C++] 퀵 정렬(Quick Sort)

   퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘 을 이용하여 구현됨. 병합 정렬과 퀵 정렬의 비교 병합 정렬(Merge Sort) 대용량의 데이터 정렬 퀵 정렬(Quick Sort) 평균 실행 시간을 줄이는 것 기본 아이디어는 병합 정렬과 같음. 원본 입력 배열을 작은 크기의 부분 배열로 나눔. 각 부분 배열을 정렬함. 그 결과를 합쳐서 전체 정렬 배열을 생성함. 핵심 병합(Combine)이 아니라 분할(Split) 입력 배열이 주어지고, 입력 배열 중 피벗(Pivot) 원소 P를 선택했을 경우, 퀵 정렬을 위한 분할 연산 은 다음의 2단계로 이루어짐. ① 입력 배열을 2개의 부분 배열 R과 L로 나눔. L 입력 배열에서 P 보다 작거나 같은 원소를 포함하..
6. 2021.06.02 [C++] 병합 정렬(Merge Sort)

   병합 정렬(Merge Sort) 병합 정렬은 분할 정복(Divide and Conquer) 알고리즘 을 이용하여 구현됨. 병합 알고리즘은 다음과 같은 과정으로 정렬을 수행함. ① 많은 원소로 구성된 전체 집합을 작은 크기의 부분 집합 으로 나눔. ② 각각의 부분 집합을 정렬함. ③ 정렬된 부분 집합을 오름차순 또는 내림차순 순서를 유지함. ④ 각각의 부분 집합을 합침. 그림) 병합 정렬을 사용하여 정수 배열을 정렬하는 예 전체 배열을 여러 개의 부분 배열로 나누는 작업을 반복함. 각 부분 배열이 하나의 원소를 가질 때 멈춤. (1단계 ~ 4단계) 이후에는 다시 배열을 합치는 작업을 반복함. 합쳐진 배열의 원소 순서가 오름차순을 유지하도록 조정함. 코드 템플릿을 사용하여 정렬할 데이터 타입에 의존적이지 않..
7. 2021.04.03 [코틀린] 컬렉션의 순서와 정렬 예제

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 fun main() { val unsortedList = listOf(3, 2, 7, 5) // reversed: 뒤집힌 순서로 컬렉션 반환 println("reversed: " + unsortedList.reversed()) // sorted: 요소를 정렬한 후 정렬된 컬렉션 반환 println("sorted: " + unsortedList.sorted()) // sortedDescending: 내림차순 정렬 println("sortedDescending: " + unsortedList.sortedDescending()) // sortedBy: 특정 비교식에 의해 정렬된 컬렉션 반환 println("sortedBy: " + unsor..
8. 2020.11.02 버블 정렬(Bubble Sort)

   *버블 정렬(Bubble Sort) 12345678910111213141516171819202122232425#include #define SIZE 5 int main() { int i, k; int list[SIZE] = {16, 7, 9, 1, 3}; // 배열의 요소 정렬 for (k = 0; k
9. 2020.06.19 [BOJ2693][C++] N번째 큰 수

   문제배열 A가 주어졌을 때, N번째 큰 값을 출력하는 프로그램을 작성하시오.배열 A의 크기는 항상 10이고, 자연수만 가지고 있다. N은 항상 3이다. 입력첫째 줄에 테스트 케이스의 개수 T(1 North America > Greater New York Region > 2009 Greater New York Programming Contest A번· 문제를 번역한 사람: baekjoon· 잘못된 데이터를 찾은 사람: occidere 코드 12345678910111213141516171819202122232425262728#include #include #include using namespace std; #define CNT 10#define NTH 3 // N번째로 큰 수 int main() { int..