728x90 코딩테스트/이코테23 [CH6 정렬] 위에서 아래로 아고,,, 이코테 너무 오랜만에 오네,,, 맨날 코테 공부를 하긴 했는데 스터디하느라 바빠서ㅠㅠ 그래서 프로그래머스 1개 풀자마자 달려왔으니까 너무 속상해하지마 이코테~~(아님) 문제 설명 하나의 수열에는 다양한 수가 존재한다 이러한 수는 크기에 상관없이 나열되어 있다 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다 수열을 내림차순으로 정렬하는 프로그램을 만드시오 입력 조건 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다 (1>n; for(int i=0;i>temp; v.push_back(temp); } sort(v.begin(), v.end(), compare); for(int i=0;i 2022. 1. 7. [CH6 정렬] 기준에 따라 데이터를 정렬 (6) 정렬 알고리즘 비교하기 지금까지 다룬 알고리즘을 비교하면 이와 같다 정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 O(N^2) O(N) 아이디어가 매우 간단하다 삽입 정렬 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때는 가장 빠르다 퀵 정렬 O(NlogN) O(N) 대부분의 경우에 가장 적합하며, 충분히 빠르다 계수 정렬 O(N+K) O(N+K) 데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠르게 동작한다 추가적으로 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있다! 그러니까 코테에선 왠만하면 라이브러리 정렬 함수 사용하자~ 파이썬의 정렬 라이브러리 알고리즘은 오랫동안 연구된 분야이고, 특히 정렬.. 2022. 1. 3. [CH6 정렬] 기준에 따라 데이터를 정렬 (5) 계수 정렬 계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다 이는 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다 모든 데이터가 양의 정수인 상황을 가정했을때, 데이터의 개수가 N개고 데이터 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장한다 계수 정렬은 매우 빠르게 동작할 뿐만 아니라 원리도 간단하다 계수 정렬은 크기 범위가 제한되어 정수 형태로 표현 가능할 때만 사용할 수 있으므로 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용가능하다 계수 정렬을 이용할 때는 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 하기 때문에, .. 2022. 1. 3. [CH6 정렬] 기준에 따라 데이터를 정렬 (4) 퀵 정렬 퀵 정렬은 지금까지 배운 정렬 알고리즘 중 가장 많이 사용되는 알고리즘이다! 이 책에서 다루지는 않지만 퀵 정렬만큼 빠른 알고리즘으로 "병합 정렬 알고리즘"이 있다 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다 이 때 기준이 되는 수를 피벗(Pivot)이라고 표현한다 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러가지 방식으로 퀵 정렬을 구분하는데, 책에서는 가장 대표적인 분할 방식인 호어 분할(Hoare Partition) 방식을 기준으로 퀵 정렬을 설명한다 퀵 정렬의 단계별 설명 호어 분할 방식에서는 아래의 규칙에 따라 피벗을 설정한다 리스.. 2021. 12. 31. [CH6 정렬] 기준에 따라 데이터를 정렬 (3) 삽입 정렬 선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다 따라서 이번에는 삽입 정렬(Insertion Sort)에 대해 알아보자! 삽입 정렬은 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 것이다 이는 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 그렇지 않다! 삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부른다 더불어 삽입 정렬은 특정한 데이터가 적절한 위지에 들어가기 이전에, 그 앞의 데이터들은.. 2021. 12. 30. [CH6 정렬] 기준에 따라 데이터를 정렬 (2) 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 것을 반복한다 이 방법은 가장 원시적인 방법으로 매번 '가장 작은 것을 선택한다'는 의미에서 '선택 정렬'이라고 불린다 정렬 알고리즘에서는 흔히 데이터의 개수를 N이라고 표현한다 다음 예제를 통해 N=10인 경우를 살펴보자 이 때 회색 카드는 '현재 정렬되지 않은 데이터 중에서 가장 작은 데이터'를 의미하고, 하늘색 카는 '이미 정렬된 카드'를 의미한다 선택 정렬의 단계별 설명 위의 카드를 선택 정렬 알고리즘을 통해 정렬해보자! STEP 0) 초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다 (0) 따라서 선택한 0과 맨 앞에 있는 데이터 7의 자리를 바꾼다 S.. 2021. 12. 29. 이전 1 2 3 4 다음 728x90
