본문 바로가기

Algorithm120

12. String Match(KPM, Rabin-Karp, Palindrome) 0. 시작하기전에 - 한동안 알고리즘 공부를 하며 깨달은게 있다. - 알고리즘을 얼마나 외우고 있느냐는 코딩테스트에서는 중요하지 않다는 점이다. - 결국 이론적인 이해도와 지식에 대한 소화시간을 충분히 갖고, 이를 기반으로 응용적인 사고가 가능하냐는 부분이 가장 중요하다. - 그러므로 코드를 외우려 노력하지말고, 그 안의 규칙성과 논리를 이해하기 위해 더 시간을 투자하기를 바란다. 1. String Match - 문자열을 탐색하는 방법론이다. - 대표적으로 KMP 알고리즘과 Rolling Hash를 사용하여 구현한 Rabin Karp 알고리즘이 있다. - 일반적으로 String Match 알고리즘은 O(n)의 시간복잡도를 갖는다. a) 시간복잡도 - 문자열 탐색은 다음과 같은 과정을 거친다. string.. 2021. 10. 20.
11. Array(배열) - Radix Sort 0. 시작하기 전에 - Radix Sort는 Counting Sort를 기반하기 때문에, Counting Sort를 알아야 한다. - 다음 포스팅에서 Counting Sort에 대해 익히기를 바란다. https://devraphy.tistory.com/438 10. Array(배열) - Counting Sort 0. 시작하기 전에 - 지금까지 배운 알고리즘은 O(n^2) 또는 O(n log n)의 시간복잡도를 갖는다. ▶ O(n^2): bubble, insertion ▶ O(n log n): merge, quick - Counting Sort는 O(n + alpha)의 시간복잡도를.. devraphy.tistory.com 1. Radix Sort(기수 정렬) a) Radix Sort를 사용하는 이유 - .. 2021. 10. 8.
10. Array(배열) - Counting Sort 0. 시작하기 전에 - 지금까지 배운 알고리즘은 O(n^2) 또는 O(n log n)의 시간복잡도를 갖는다. ▶ O(n^2): bubble, insertion ▶ O(n log n): merge, quick - Counting Sort는 O(n + k)의 시간복잡도를 가진다. - Counting Sort를 이해하며 k의 의미가 무엇인지 알아보자. 1. Counting Sort(계수정렬) - Counting Sort는 주어진 array의 요소를 counting하여 정렬하는 알고리즘이다. a) Counting Sort의 정렬과정 2. 코드 구현 - 위에서 진행한 과정을 코드로 그대로 구현하면 Counting Sort 알고리즘이 완성된다. - 다음 코드를 확인해보자. from typing import List.. 2021. 10. 5.
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.

티스토리툴바