본문 바로가기

정렬

Algorithm&Data Structure 2022. 12. 22. [Algorithm] 백준 정렬 파트 (2108,18870) 백준 알고리즘 단계별로 풀어보기 중 정렬 단계를 모두 풀어봤다. 그중 2108번과 18870에서 어려움을 겪어 기록을 남기게 되었다. 개요 정렬은 이전 기록에서 다룬 적이 있다. [Algorithm] 정렬 방법, 구현(선택, 버블, 삽입, 병렬, 퀵, 계수) 정렬에 대해 공부를 해서 이에 대한 기록을 하려고 한다. 본 글의 정렬은 오름차순을 기본으로 한다. 내림차순은 파이썬에 내장된 reverse 메서드를 사용하면 쉽게 구현할 수 있다. 1. 선택 정렬 선 choi-records.tistory.com 때문에 백준 알고리즘 정렬 단계에서 대부분의 문제들을 무난하게 풀어냈다. 정렬 단계 시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 ..
[Algorithm] 정렬 방법, 구현(선택, 버블, 삽입, 병렬, 퀵, 계수)
Algorithm&Data Structure 2022. 11. 25. [Algorithm] 정렬 방법, 구현(선택, 버블, 삽입, 병렬, 퀵, 계수) 정렬에 대해 공부를 해서 이에 대한 기록을 하려고 한다. 본 글의 정렬은 오름차순을 기본으로 한다. 내림차순은 파이썬에 내장된 reverse 메서드를 사용하면 쉽게 구현할 수 있다. 선택 정렬 선택 정렬은 가장 작은 수나 큰 수를 선택해 우선적으로 정렬시키는 방법이다. 위의 그림처럼 가장 큰 수를 계속해서 찾아가는 식의 방법이다. 코드는 매번 작은 수를 찾아서 왼쪽에 배치하는 방법을 사용했다. def SelectionSort(A): for i in range(1,len(A)): minIdx=i for j in range(i,len(A)): if A[j]A[j+1]: A[j],A[j+1]=A[j+1],A[j] return A 시간 복잡도 선택 정렬과 마찬가지로 이중 for문을 사용하기 때문에 O(N**2)..

티스토리툴바