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 : 병합할 때 buff에 접급하기 위한 변수
i : list의 원소 중 buff에 저장이 안된 원소들이 존재하는 시작 인덱스를 저장하는 변수
k : 최종적으로 list에 병합하여 저장할 때 사용하는 변수
'''
p = j = 0
i = k = left
# list[left] ~ list[middle] -> buff[0] ~ buff[mmiddle-left] 저장
while i <= middle :
buff[p] = list[i]
p += 1
i += 1
# buff[0] ~ buff[middle - left] 와 list[middle + 1] ~ list[right]병합
while i <= right and j < p :
# 현재 buff[j] 에 저장되어있는 값이 더 작은 경우
if buff[j] <= list[i] :
list[k] = buff[j]
j += 1
# 현재 list[i] 에 저장되어있는 값이 더 작은 경우
else :
list[k] = list[i]
i += 1
#현재 list[0] ~list[k]까지 정렬되어 저장되어있다.
k += 1
# buff에서 list로 저장되지 않는 남은 원소의 값 복사
while j < p :
list[k] = buff[j]
k += 1
j += 1
n = len(list)
# 병합 결과를 임시 저장하는 배열 선언
buff = [None] * n
_merge_sort(list, 0, n-1)
del buff
# 이 코드를 main으로 실행할 경우에만 실행된다.
if __name__ == '__main__' :
nums = [5, 4, 3, 2, 1]
merge_sort(nums)
for i in nums:
print(i, end=' ')2. 힙 정렬(heap sort)
'힙에서 최댓값은 루트에 위치한다'는 특성을 이용하여 정렬하는 알고리즘
1. Heap
- '부모의 key 값 >= 자식의 key 값' 라는 조건을 만족하는 완전 이진 트리
- 완전 이진 트리
- 부모가 가질 수 있는 자식 노드의 수는 최대 2개
- 자식 노드를 추가할 경우 항상 왼족부터 추가하여 모양을 유지한다.
- heap을 배열에 저장
- 위쪽에서 부터, 왼쪽에서부터 순서대로 인덱스 값을 1씩 증가시키며 저장
- 인덱스가 i 인 원소의 경우
- 부모 인덱스 : (i-1) // 2
- 왼쪽 자식 인덱스 : i * 2 + 1
- 오른쪽 자식 인덱스 : i * 2 + 2
2. 힙을 배열로 저장하여 구현하기
def heap_sort(list) :
# list[left] ~ list[right] -> 힙 만들기
def down_heap(list, left, right) :
# 현재 루트 값
root = list[left]
# 현재 루트의 인덱스
parent = left
# 자식 노드를 가지지 않은 노드는 부모 노드가 될 수 없다.
while parent < (right + 1) // 2 :
child_left = parent * 2 + 1
child_right = child_left + 1
# 왼쪽 자식과 오른쪽 자식을 비교해서 큰 쪽 선택
child = child_right if child_right <= right and list[child_right] > list[child_left] else child_left
# 현재 root 값이 자식들의 값보다 크면
if root >= list[child]:
break
# 작으면 자식의 값과 root 값을 바꾼다.
list[parent] = list[child]
parent = child
list[parent] = root
n = len(list)
# 1단계 - 입력받은 리스트를 힙으로 만들기
# (n-1)//2 = 최대 깊이 및 현재 가장 아래에 있으며 오른쪽에 있는 노드의 인덱스
for i in range((n-1)//2, -1, -1) :
down_heap(list, i, n-1)
# 2단계 - 최댓값인 list[0] 와 리스트의 끝 값 교환 후
# list[0] ~ list[i-1] 까지만 힙으로 만들기
# list[i] ~ list[n-1] 까지는 정렬되어 있다.
for i in range(n-1, 0, -1) :
list[0], list[i] = list[i], list[0]
down_heap(list, 0, i-1)
# 이 코드를 main으로 실행할 경우에만 실행된다.
if __name__ == '__main__' :
nums = [5, 4, 3, 2, 1]
heap_sort(nums)
for i in nums:
print(i, end=' ')3. 힙 라이브러리 사용하여 구현하기
import heapq
def heap_sort(list) :
heap = []
# 1단계 리스트를 heap에 저장 -> heapq.heappush() 사용
for i in list :
heapq.heappush(heap, i)
# 2단계 - 힙에 저장된 값을 하나씩 꺼내며 list에 저장
for i in range(len(list)):
list[i] = heapq.heappop(heap)
# 이 코드를 main으로 실행할 경우에만 실행된다.
if __name__ == '__main__' :
nums = [5, 4, 3, 2, 1]
heap_sort(nums)
for i in nums:
print(i, end=' ')3. 정렬 내용 정리
정렬 동작 설명 참고하기 좋은 사이트
https://roytravel.tistory.com/328
[자료구조] 기본 정렬 알고리즘 총 정리
1. 버블 정렬 (Bubble Sort) 버블정렬은 서로 인접해 있는 요소 간의 대소 비교를 통해 정렬한다. 버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 단순한 만큼 비효율적이다. 시간 복잡도
roytravel.tistory.com
| 정렬 종류 | 장점 | 단점 |
| 선택 정렬 | 구현이 간단하다 | 시간이 오래 걸린다 |
| 버블 정렬 | 구현이 간단하다 | 시간이 오래 걸린다 |
| 삽입 정렬 | 성능이 좋아서 다른 정렬법 일부로 사용된다 | 데이터의 상태에 따라 성능 차이가 심하다 |
| 병합 정렬 | 항상 O(nlogn)으로 빠른 편이다 | 추가적인 메모리 공간이 필요하다 |
| 퀵 정렬 | 실행 시간이 O(nlogn)으로 빠른 편이다 + in-place sorting 방식으로 구현할 경우, O(logn)의 공간 복잡도를 가질 수 있다. |
pivot에 의해 성능 차이가 크다 |
| 힙 정렬 | 항상 O(nlogn)으로 빠른 편이다 | 실제 다른 O(nlogn) 정렬법보다 느리다 |
| 도수 정렬 | O(n) 으로 빠르다 | 추가적인 메모리 공간이 필요하다 |
빠른 경우 ~ O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) ~ 느린 경우
| 정렬 종류 | Worst | Average | Best |
| 선택 정렬 | O(n^2) | O(n^2) | O(n^2) |
| 버블 정렬 | O(n^2) | O(n^2) | O(n^2) |
| 삽입 정렬 | O(n^2) | O(n^2) | O(n) |
| 병합 정렬 | O(nlogn) | O(nlogn) | O(nlogn) |
| 퀵 정렬 | O(n^2) | O(nlogn) | O(nlogn) |
| 힙 정렬 | O(nlogn) | O(nlogn) | O(nlogn) |
| 도수 정렬 | O(n) | O(n) | O(n) |
4. github 사용법 정리
1. 원격 저장소에 저장된 내용 로컬에 불러오기
git clone 저장소URL.git※ 이미 clone을 한 이후에는 git checkout main && git pull 명령으로 원격 저장소와 로컬을 동기화 할 수 있다.
※ git pull : 원격 저장소 브랜치에서 데이터를 가져와 로컬 브랜치와 merge 시켜주는 명령어
※ 원격 저장소(Remote Repository) : 원격 서버에서 관리되며 여러 사람이 함께 공유하기 위한 저장소
※ 로컬 저장소(Local Repository) : 내 PC에 저장되는 개인 저장소
2. 나만의 브랜치 생성하기
git checkout -b 브랜치명※ 브랜치(branch) ? 독립적으로 어떤 작업을 진행하기 위한 개념
필요에 의해 만들어지는 각각의 브랜치는 다른 브랜치의 영향을 받지 않기 때문에, 여러 작업을 동시에 진행할 수 있다.
※ git branch : 현재 브랜치 목록 보기( 현재 브랜치에 * 표시)
※ git checkout : 브랜치 이동 (-b 표시는 브랜치 만들고 그 브랜치로 이동하라는 옵션)
3. 파일 stage에 올리기
git add 파일명※ Staging Area : Git 디렉토리에 존재, 단순한 파일로 곧 commit할 파일에 대한 정보를 저장한다.
※ add 명령어 : 디렉토리에 있는 파일을 추적하고 관리할 수 있다.
※ 변경된 전체 파일 add 하기 : git add . 또는 git add --all
4. commit
git commit -m "commit message"※ commit : 데이터가 로컬 데이터베이스에 안전하게 저장됐다는 것 즉, 파일을 추가하거나 변경 내용을 저장소에 저장하는 작업
5. push하기
git push -u origin 브랜치명※ origin : 원격저장소 명
※ push : 파일을 추가하거나 변경 내용을 원격 저장소에 업로드 하는 작업
6. pull request 만들기
※ main ← my_branch : 내 브랜치와 main 브랜치 merge하기
compare 쪽이 본인 브랜치가 되도록!!
※ Reviewer 지정 가능
git 기본 개념 참고 사이트
https://backlog.com/git-tutorial/kr/reference/
누구나 쉽게 이해할 수 있는 Git 입문~버전 관리를 완벽하게 이용해보자~ | Backlog
누구나 쉽게 알 수 있는 Git에 입문하신 것을 환영합니다. Git을 사용해 버전 관리를 할 수 있도록 함께 공부해봅시다!
backlog.com
https://git-scm.com/book/ko/v2/Git의-기초-Git-저장소-만들기
Git - Git 저장소 만들기
2.1 Git의 기초 - Git 저장소 만들기 Git을 사용하는 방법을 알고 싶은데 한 챕터밖에 읽을 시간이 없다면 이번 챕터를 읽어야 한다. Git에서 자주 사용하는 명령어는 모두 2장에 등장한다. 2장을 다
git-scm.com
3일에 걸쳐서 다양한 정렬을 python으로 기본 구현을 해보고 원리를 다시한번 정리하는 시간을 가졌다.
이미 다른 언어로 한번 공부했던 정렬들이었지만 다시 보니 많이 헷갈려서 좀 오래걸렸다. 그래도 가끔 정리한 내용을 읽어보고 리마인드를 해야할 것 같았다.
그리고 오늘은 git에 대해 공부하는 시간을 가졌다.
늘 두루뭉실하게 git의 개념을 알고서 대충 내 코드를 정리할 용도로만 사용해보았는데 협업시 사용해야할 내용들을 직접해보고 공부하니 재밌었다. 그리고 미니 프로젝트할 때 사용법을 알았다면 서로의 코드에서 오타와 같은 문제가 없어 시간 절약을 할 수 있었을 텐데.. 생각이 들면서 협업을 위해 꼭 공부해야겠다.ㅠㅜ
'KraftonJungle2기 > Today I Learned' 카테고리의 다른 글
| [TIL] Algorithm - 이분탐색(Binary Search) + 직접 주소 테이블이란? (1) | 2023.04.13 |
|---|---|
| [TIL] 백준 풀이 정리 (0) | 2023.04.12 |
| [TIL] 백준 코드 풀이 & Computer System (0) | 2023.04.11 |
| [TIL] Algorithm - 정렬2 (0) | 2023.04.09 |
| [TIL] Algorithm - 정렬 (0) | 2023.04.08 |
