본문 바로가기

Computer Science34

[Python] 트라이 자료구조 구현(Trie) 트라이 자료구조는 검색에 최적화된 자료구조이다 자식 노드가 여러 개인 트리 형태로 구성된다고 이해하면 된다. https://leetcode.com/problems/implement-trie-prefix-tree/ Implement Trie (Prefix Tree) - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 위의 문제를 기준으로 구현했다. class TrieNode: def __init__(self): self.word = False self.childre.. 2022. 4. 30.
Python 힙 구현 힙 자료구조를 만족하려면 두 가지 조건(최소 힙 기준) 1. 부모 노드가 자식 노드보다 작다. 2. 트리의 모양이 완전 이진트리의 형태. 완전 이진트리는 마지막 레벨을 제외하고 모든 노드가 왼쪽에서 오른쪽으로 채워져 있는 트리 -> 리스트로 구현 class BinaryHeap: def __init__(self): self.items = [None] def __len__(self): return len(self.items) - 1 # 위로 올라가는거 def _percolate_up(self): index = len(self) parent = index // 2 while parent > 0: if self.items[parent] > self.items[index]: self.items[parent], s.. 2022. 4. 23.
자료구조, 자료형, 추상 자료형 단어가 서로 비슷해 보이지만 차이가 있다. 이를 정리해보자. 자료구조 데이터에 효율적으로 접근하고 조작하기 위한 조직, 관리, 저장 구조를 말함. 예 : 해시 테이블, B-Tree , 배열, 트리, 힙 자료형 컴파일러 또는 인터프리터에게 프로그래머가 데이터를 어떻게 사용하는지를 알려주는 데이터 속성 예 : 정수, 실수, 문자열, 원시 자료형 추상 자료형 Abstract Data Type(ADT)라 부름 자료형에 대한 수학적 모델들을 지칭함. 해당 유형의 자료에 대한 연산들을 명기한 것. OOP의 추상화와 비슷한 개념 - 선풍기는 전원버튼과 미풍, 약풍, 강풍이 있어야 함 + O(1)의 시간복잡도로 수행해야 한다. 라고 명기 하면 추상적 자료 구조가 된다. 예: 스택에는 push, pop, size, fu.. 2022. 3. 25.
#10 해시 테이블 구현 dict를 직접 구현 해 보았다. open addressing 으로 구현했는데 손 가는데로 짜서 remove에서 살짝 에러가 있는 것 같다. 추후에 수정해야겠다 class Dict: def __init__(self,size=8): self.hashtable = list([None for _ in range(size)]) self.size = size self.item = 0 def get_key(self,key): return self.hash_function(key) % self.size def hash_function(self,key): return hash(key) def get_loadfactor(self): return self.item / self.size def check_cluster(se.. 2022. 1. 9.
#09 이진 탐색 정렬된 리스트에서 특정 값을 탐색할 때 순차 탐색보다 빠르게 탐색할 수 있는 알고리즘 순차 탐색 : O(n) 이진 탐색 : O(logn) ''' 1. start가 end보다 크다면 stop 2. mid 값을 정함 3. mid 인덱스의 값과 target이 같으면 return 4. mid 인덱스의 값보다 target이 작으면 mid 왼쪽에 있으므로 end 값을 mid -1 5. mid 인덱스의 값보다 target이 크면 mid 오른쪽에 있으므로 start 값을 mid + 1 ''' def binary_search(arr, start, end, target): if start > end: return None mid = (start + end)//2 if arr[mid] == target: return mid.. 2022. 1. 8.
정렬 알고리즘 코드(python) import time import random import sys sys.setrecursionlimit(int(1e9)) def bubblesort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): # 매번 오른쪽부터 큰 값이 정렬됨 -> n-i-1 if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return def improved_bubblesort(arr): end_index = len(arr)-1 while end_index > 0 : swap = 0 for i in range(end_index): # 마지막으로 스왑 된 곳까지 정렬 되었다고 판단 가능하므로 좀 더 효율 if a.. 2022. 1. 8.
#08 파이썬 내장 정렬(Tim Sort) 파이썬의 내장 정렬은 Tim sort 알고리즘으로 구현되어있다. tim sort는 삽입 정렬과 병합 정렬을 합쳐서 구현한 알고리즘이다. 최악에 경우에 O(nlogn) 최선의 경우에 O(n)을 보장하는 알고리즘이다. 1. 리스트가 주어졌을때 이를 run 단위로 나눈다 (원소의 개수는 32 ~ 64개) 2. run 단위로 나눈 후에 run 단위로 insertion sort를 한다. -> 원소의 개수가 적기 때문에 효율적으로 동작함 O(n) 시간 3. 정렬된 단위별로 merge sort를 진행함. 4. 어떤 순서로 run들을 merge sort 하는지에 대해 stack을 이용하여 결정한다. 추가 메모리를 사용하기 때문에 in-place 알고리즘은 아님, 안정 정렬임 2022. 1. 8.
#08 계수 정렬(Counting Sort) 계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능. 최악의 경우에도 수행 시간O(N + K)를 보장 def count_sort(arr): counting = [0] * (max(arr)+1) sorted_arr = [] for i in arr: counting[i] +=1 for i in range(len(counting)): sorted_arr += [i]*counting[i] for i in range(len(arr)): arr[i] = sorted_arr[i] 수행 시간 비교 파이썬 내장 정렬은 정말 빠르다. 다음 포스팅에 python 구현되어있는 내장 sort인 tim sort에 대.. 2022. 1. 7.
#07 기수 정렬(Radix Sort) 기수 정렬은 각각의 자릿수를 기반으로 정렬해나가는 알고리즘이다. 안정 정렬에 속하고, 비교 정렬을 수행하지 않아서 조건이 맞는 상황에서 빠른 정렬 속도를 보장하는 알고리즘이다. 장점 : 문자열, 정수 정렬 가능 , 일부에서 nlogn 보다 빠르게 동작(비교 연산을 하지 않음) 단점 : 자릿수가 없는 것은 정렬할 수 없음. (부동 소숫점) 중간 결과를 저장할 bucket 공간이 필요함. 기수 정렬의 방법으로는 LSD와 MSD 두 방법이 있는데 MSD (Most-Significant-Digit)과 LSD (Least-Significant-Digit)을 비교 MSD는 가장 큰 자릿수부터 Counting sort 하는 것을 의미하고, LSD는 가장 낮은 자리수부터 Counting sort 하는 것을 의미함. (.. 2022. 1. 7.
#06 힙 정렬(Heap Sort) 2021.12.31 - [Comuter Science/Data Structure] - 힙 자료구조 힙 자료구조 힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자. 위와 같은 표현법을 사용하면 인덱스가 정해지게 된다. 즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다 hkim-data.tistory.com 힙 자료구조는 트리를 기반으로 설계된 자료구조이다. 힙 정렬은 어떤 max 값을 꺼내고 다시 정렬하는 데에 O(logn)의 시간 복잡도가 소요된다. 이를 활용해서 n개의 원소를 매번 logn을 통해 불러오므로 O(nlogn)의 시간이 소요되는 정렬 알고리즘이다. 1. 주어진 배열을 최대 힙으로 만든다(heapify) 2. n번만큼 반복하며 루트 노드와 맨 끝 노드를 바꾼 .. 2022. 1. 7.
#05 병합 정렬(Merge Sort) 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현 퀵 정렬과는 다르게 안정 정렬에 속함 시간 복잡도는 최악, 평균, 최선 모두 O(nlogn)이며 공간 복잡도는 O(2n)이다. 입력값을 제외하면 O(n) def merge_sort(arr): if len(arr) < 2: return arr mid = len(arr)//2 low_arr = merge_sort(arr[:mid]) high_arr = merge_sort(arr[mid:]) merge_arr = [] l, h = 0, 0 while l < len(low_arr) and h < len(high_arr): if low_arr[l] < high_arr[h]: merge_arr.append(low_arr[l]) l += 1 else: merge.. 2022. 1. 6.
#04 퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복을 통해 정렬을 수행하는 대표적인 정렬 알고리즘이다. 최선과 평균에서 시간 복잡도가 O(nlogn)으로 다른 정렬 알고리즘과 비교했을 때 가장 빠르다. 공간 복잡도도 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n)이다. - 하단에 pythonic 한 코드에서는 추가로 n의 공간을 사용하므로, O(2n)이다. 이미 오름차순, 내림차순으로 정렬되었을 때 O(n^2)이고, 또한 불안정 정렬이라는 단점이 존재한다. def quick_sort(arr, start, end): if start >= end: # 인덱스가 하나 return pivot = start left = start + 1 right = end while left arr[pivot]: # 피벗보다 작은 값이 나올때까지.. 2022. 1. 6.
#03 삽입 정렬(Insertion Sort) 두번째 원소부터 시작해서 매번 삽입할 위치를 앞 원소들과 비교하며 결정하는 알고리즘 최선의 경우 O(N) 이라는 엄청나게 효율적인 알고리즘 최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, O(n^2) 이다. 하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우, 한번씩 밖에 비교를 안하므로 O(n) 의 시간복잡도를 가지게 된다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다. 최선의 경우는 O(n) 의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2) 의 시간복잡도를 갖게 된다. def insertionsort(arr): for i in range(1.. 2022. 1. 5.
#02 - 선택 정렬(Selection Sort) 매번 루프마다 가장 작은 최솟값을 선택해서 맨 앞부터 하나씩 채우는 알고리즘 시간 복잡도 : 최선, 평균, 최악의 경우 시간 복잡도는O(n^2)으로 동일 공간 복잡도 : 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다. def selectionsort(arr): n = len(arr) for i in range(n-1): min_index = i for j in range(i+1,n): if arr[j] < arr[min_index]: min_index = j arr[i], arr[min_index] = arr[min_index], arr[i] return arr 확실히 교환작업에서 시간을 단축해서 bubble sort보단 빠른 것 같다. 그래도 여전히 비효율적이다 n^2 불안.. 2022. 1. 5.
#01 거품정렬 (bubble sort) arr = [6,8,3,1,5,4,9,0,2,7] def bubblesort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr def improved_bubblesort(arr): end_index = len(arr)-1 while end_index > 0 : swap = 0 for i in range(end_index): if arr[i] > arr[i+1] : arr[i], arr[i+1] = arr[i+1], arr[i] swap = i end_index = swap return arr - 서로 인접한 두 원소의 .. 2022. 1. 5.

티스토리툴바