Algorithm/알고리즘 공부노트24 9. Array(배열) - Heap Sort(2) 0. 시작하기 전에 - 이전 포스팅에서 Heap 자료구조에 대해 간단하게 알아보았다. - 이제 Heap을 이용해 어떻게 정렬을 하는지 알아보자. 1. Heap 구현 a) 파이썬에서 Heap을 구현하는 방법 - 파이썬에서 Heap을 구현려면 2가지만 배우면 된다. ▶ heapq 라이브러리 ▶ heapify 함수 import heapq case = [9, 7, 5, 3, 1] heapq.heapify(case) print(case) #[1,3,5,9,7] 반환 b) heapq 라이브러리는 Min Heap만 만들 수 있다. - heapify 함수를 이용하면 Min Heap을 만들 수 있다. - 하지만, heapq 라이브러리에는 Max Heap을 만들어 주는 함수는 따로 존재하지 않는다. - 그러므로 약간의 노.. 2021. 9. 9. 8. Array(배열) - Heap Sort(1) 1. Heap Sort를 배우기 전에 - Heap Sort라는 이름에서 알 수 있듯이, Heap 자료구조를 이용해 배열을 정렬하는 알고리즘이다. - Heap Sort를 이해하기 위해서는 2가지 개념을 우선적으로 알아야한다. ▶ Tree 자료구조 https://devraphy.tistory.com/45 Data Structure - 트리(Tree) & 이진탐색트리(Binary Search Tree) 1. 트리(Tree) - 트리는 node와 branch를 이용하여 구성된 데이터구조로 사이클이 없다. - 트리는 이진트리(Binary Tree)형태의 구조를 이용하여 탐색(검색) 알고리즘 구현에 많이 사용된다. * 이진트리 - devraphy.tistory.com ▶ Heap 자료구조 https://devrap.. 2021. 9. 9. 7. Array(배열) - Quick Sort(퀵 정렬) 1. Quick Sort란? - Quick Select와 마찬가지로 정렬이 되어있지 않은 배열을 대상으로 사용하는 알고리즘이다. - Quick Select와 동일하게 Partitioning을 이용하여 배열을 정렬한다. a) Quick Sort 정렬과정 b) Quick Sort의 시간복잡도 c) Quick Sort의 안정성(Stability) - Quick Sort는 불안정한(unstable) 정렬 알고리즘이다. 2. 코드구현 from typing import List import random def quick_sort(case:List[int], begin_idx:int, last_idx:int) -> List[int]: length = last_idx - begin_idx + 1 if length 2021. 9. 6. 6. Array(배열) - Quick Select 1. Quick Select란? - 정렬되지 않은 배열에서 N번째로 크거나 작은 수를 찾을 때 사용되는 알고리즘 - N번째 수를 찾기 위해서는 다음과 같은 방법을 사용할 수 있다. 1) 전체 요소를 오름차순으로 정렬한 후, N번째 수를 찾는 방법 - O(N log N)의 시간복잡도 2) Heap 정렬 - O(n log k)의 시간복잡도 - 1)의 방법보다 빠르다. 3) Quick Select - O(n)의 시간복잡도 - 가장 빠른 방법이다. - 이 중에서 가장 빠른 Quick Select에 대해서 알아보자. 2. Quick Select 개념 - Quick Select는 Partitioning(파티셔닝)을 이용한 알고리즘이다. ▶ Partitioning 이란? - Pivot 이라는 하나의 숫자를 기준으로 .. 2021. 9. 2. 5. Array(배열) - Merge Sort(병합정렬) 1. Merge Sort란? - 하나의 배열을 반씩 쪼개어, 배열의 요소를 각각의 배열로 만든다. - 독립적으로 쪼개진 배열을 비교해가며 병합하여 하나의 정렬된 배열을 만드는 알고리즘이다. a) 예제를 통한 병합정렬의 이해 b) 배열간의 요소를 비교하고 병합하는 과정 c) 병합정렬의 시간복잡도 2. 병합정렬 코드구현 # Merge Sort # 1) Merge Sort의 개념 # - 하나의 배열을 반씩 쪼개어 요소의 총 개수만큼 독립된 배열을 만든다. # - 반씩 쪼개진 배열을 Left, Right로 구분한다. # - Left에 있는 배열끼리, Right에 있는 배열끼리의 요소를 비교하여 병합한다. # - 비교 후 병합하는 과정을 반복하여 최종적으로 하나의 정렬된 배열을 만든다. # - 이 과정을 재귀적으.. 2021. 8. 31. 버블정렬, 삽입정렬, 선택정렬 완전분석 0. 개요 - 본격적으로 알고리즘 공부를 시작하면서, 가장 기초인 정렬 알고리즘을 배웠다. - 수학공식 외우듯, 개념을 이해하고 외워야겠다는 태도로 접근했는데 쉽지 않았다. - 개념은 이해가 가지만, 코드로 구현했을 때 왜 이렇게 작성하는지 이해가 가지 않는 부분이 있었다. - 그래서 내가 완벽히 이해하기 위해 분석한 내용을 공유한다. - 아래 글의 사진이 잘 안보이는 분들을 위해 PDF 파일을 제공합니다. 1. Bubble Sort a) 정렬과정 b) 코드 기반 개념 이해 c) 완성 코드 from typing import List def bubble_sort(case: List[int]) -> List[int]: for idx in range(len(case) - 1): for i in range(le.. 2021. 8. 30. 4. Array(배열) - Selection Sort(선택정렬) 1. Selection Sort란? - 가장 왼쪽의 수(index 0)을 기준으로 최소값을 찾아 swap하여 정렬하는 알고리즘 - 한번 탐색을 할 때마다, 기준 index값이 1씩 증가한다. a) 예제를 통한 선택정렬의 이해 2. 선택정렬의 시간복잡도 - 선택정렬은 버블정렬과 삽입정렬과 동일한 O(n^2)의 시간복잡도를 갖는다. 3. Selection Sort의 안정성 - 선택정렬은 불안정(unstable)한 알고리즘이다. 4. Selection Sort 직접 구현해보기 - 선택정렬의 개념을 배웠으니, 직접 코드로 구현해보자. from typing import List def selection_sort(case: List[int]) -> List[int]: for idx in range(1, len(ca.. 2021. 8. 24. 3. Array(배열) - Insertion Sort(삽입정렬) 1. Insertion Sort란? - 삽입 정렬은 버블정렬과 동일하게 O(n^2)의 시간복잡도를 갖는 정렬 알고리즘이다. - 조건에 맞는 적절한 곳에 배열의 요소를 삽입하여 정렬하는 방법이다. a) 예제를 통한 삽입정렬의 이해 b) 삽입정렬의 시간복잡도 → O(n^2) c) 삽입정렬의 안정성(Stability) - 삽입 정렬은 안정적인 알고리즘이다. - 아래의 코드구현 예시를 통해 살펴보자. d) 삽입정렬 구현하기 from typing import List def insertion_sort(case: List[int]) -> List[int]: for idx in range(1, len(case)): current = case[idx] # 기준 값과 비교될 요소 flag = idx - 1 # 기준 값의.. 2021. 8. 24. 파이썬 - 알고리즘 Tips(8/23 업데이트) - 본 포스팅은 알고리즘 문제를 풀면서 배우게 된 Tip을 정리한 포스팅입니다. - 일종의 오답노트이며, 최근순으로 정리됩니다. 9. 함수의 매개변수 타입을 지정하는 방법 - 만약 어떤 함수를 작성할 때, 매개변수를 지정하고 싶다면 어떻게 할까? - 아래의 예시 코드를 우선 살펴보자. from typing import List def bubble_sort(List[int]) -> List[int]: #함수내용작성 - 위의 코드는 다음과 같은 방식으로 구조를 갖는다. def 함수명(매개변수명: 자료형) -> 반환자료형: #함수내용작성부 - 매개변수 다음 콜론을 적는다. - 콜론 다음에 매개변수의 자료형을 적는다. - 화살표 기호 다음에 작성되는 자료형은 해당 매개변수를 return 할 때 적용할 자료형을 .. 2021. 8. 23. 이전 1 2 3 다음
