본문 바로가기

728x90

Algorithm21

[TIL] Algorithm - 정렬3 + git 사용법 정리 1. 병합 정렬(merge sort) 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘 # 병합 정렬 구현 def merge_sort(list) : # 재귀적으로 실행할 함수 def _merge_sort(list, left, right) : if left < right : middle = (left + right) // 2 _merge_sort(list, left, middle) # 배열의 앞부분 정렬 _merge_sort(list, middle+1, right) # 배열의 뒷부분 정렬 ''' 앞에서 이미 정렬된 배열 2개를 병합하기 위한 변수들 p : 현재 buff가 채워져 있는 정도를 저장하는 변수 / 즉, buff[p-1]까지 채워져있다. j : 병합할 .. 2023. 4. 10.

[TIL] Algorithm - 정렬2 1. 시간 복잡도 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간 Big-O(빅-오) 표기법 : 최악의 경우를 계산하는 방식 Big-O description $$ O\left ( 1 \right ) $$ 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸린다. $$ O\left ( log_{2}n \right ) $$ 입력데이터의 크기가 커질수록 처리시간이 로그만큼 짧아진다. $$ O\left ( n \right ) $$ 입력데이터의 크기에 비례하여 시간이 증가한다. $$ O\left ( n log_{2}n \right ) $$ 데이터가 많아질수록 로그배 배만큼 시간이 증가한다. $$ O\left ( n^{2} \right ) $$ 데이터가 많아질수록 급수적으로 시간이 증가한다. $$ O\left.. 2023. 4. 9.

[TIL] Algorithm - 정렬 ⏰ 2023.04.08 ⏰ 1. Sorting key 를 항목 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업 데이터를 교환, 선택, 삽입하면서 정렬을 완료한다. ★ 정렬 알고리즘의 안전성 ★ 값이 같은 원소의 순서는 정렬한 후에도 유지되면 안정적인 정렬 알고리즘이다. 안정적인 정렬 알고리즘 버블 정렬, 삽입 정렬, 병합 정렬, 도수 정렬(계수 정렬) 안정적이지 않는 정렬 알고리즘 선택 정렬, 퀵 정렬, 힙 정렬, 2. 버블 정렬(bubble sort) 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘 ( = 단순 교환 정렬 ) 시간복잡도 O(n^2) 1. 기본 구현 # 기본 버블 정렬 def bubble_sort(list) : n = len(list).. 2023. 4. 8.

이전 1 2 다음

728x90

티스토리툴바