본문 바로가기

All Post269

#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.
이진 탐색 트리 (Binary Search Tree) - 탐색, 삽입, 삭제 이진 탐색 트리(Binary Search Tree) - 각 노드의 왼쪽 subtree의 key 값은 노드의 key 값보다 작거나 같아야 하고 - 각 노드의 오른쪽 subtree의 key 값은 노드의 key 값보다 커야 한다. - 모든 노드에서 만족해야 함. search 연산에서 장점이 있음 O(h) -> 높이를 적정하게 유지하는 것이 중요. class BST: def __init__(self): self.root = None self.size = 0 def __len__(self): return self.size def __iterator__(self): return self.root.__iter__() # yield def find_loc(self, key): # key 값 노드가 있다면 해당 노드 r.. 2022. 1. 2.
이진트리 - 정의와 순회 이진트리를 노드와 링크를 통해 직접 구현하도록 한다. key, left, right, parent class Node: def __init__(self, key): self.key = key self.parent = None self.left = None self.right = None def __str__(self): return str(self.key) 이진트리 순회(trabersal) 1. preorder (전위) 2. inorder (중위) 3. postorder (후위) preorder -> MLR inorder -> LMR postorder -> LRM preoder : F B A D C E G I H inorder : A B C D E F G H I postorder : A C E D B H.. 2022. 1. 1.
힙 자료구조 - insert 연산 1. 힙의 모양성질 만족 2. 모든 부모의 key가 자식의 key 보다 커야함 이러한 힙에서 만약 14가 들어오고자 하면, 새로 들어온 14 때문에 힙 성질을 만족하지 못한다. 따라서 이를 적절히 변경해줘야 함. 14를 위로 올려 보내면서 자기 자리를 찾도록 해야 한다. def insert(14): A.append(14) A.heapify(9) # up # A[k]를 root 방향으로 이동하면서 heapify def heapify(k): # A[k]를 heapify # 아직 루트에 도달하지 않았고, 부모의 key 값이 나보다 작을 때 while k > 0 and A[(k-1)//2] < A[k] : A[k], A[(k-1)//2 = A[(k-1)//2], A[k] k = (k-1)//2 참조 - http.. 2022. 1. 1.
힙 자료구조 - make heap 연산 https://hkim-data.tistory.com/187 힙 자료구조 힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자. 위와 같은 표현법을 사용하면 인덱스가 정해지게 된다. 즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다 hkim-data.tistory.com 이전 포스팅에 이어서 make heap 연산에 대해 알아보자 힙 성질을 만족하기 위해, heapify - down을 계속해서 진행하면 된다. 리스트의 맨 오른쪽 인덱스부터 A[0]까지 계속해서 반복 1. 리프노드면 내버려둠 2. 자식 노드가 있을 때 나보다 클 때 A [2*k+1]과 A [2*k+2] 값 중 큰 것이랑 변경 3. 변경 후 리프 노드가 아니면 또 아래랑 비교해줘야 함 def make_heap(A.. 2022. 1. 1.
힙 자료구조 힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자. 위와 같은 표현법을 사용하면 인덱스가 정해지게 된다. 즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다. H[k] - 왼쪽 자식 노드 : H[2*k+1] - 오른쪽 자식 노드 : H[2*k+2] - 부모 노드 : H[(k-1) //2] 힙 (heap) : 힙 성질(heap property)를 만족하는 이진트리 힙 성질 1. 모양이 힙의 형태 (왼쪽부터 채운 형태) 2. 모든 부모 노드 키값은 자식 노드 키값보다 커야 함 힙의 루트노드에서는 가장 큰 값이다. A[0] 제공연산: 1. insert : O(logn) 2. find-max : return A[0] - O(1) 3. delete-max : O(logn) 참조 - .. 2021. 12. 31.
트리 자료구조 (용어 설명 및 표현법) 순차적 자료구조 : 배열, 연결 리스트 트리는 부모와 자식의 형태로 나타내는 자료구조 - 연결 리스트는 자식이 최대 1까지 있는 특수한 형태의 트리 자식이 최대 2개까지 있는 경우 이진트리(binary tree) 경로(path) : ex 3에서 12로 갈 때 3 -> 2 -> 7 -> 8 -> 12 경로 길이 (path length) = 4 (경로상의 에지 개수) 이진트리를 코드상에서 저장 표현법 3 : Class 활용 참고 - https://www.youtube.com/watch?v=w-1w4ood7Bc&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=20 2021. 12. 31.
해시 테이블 - collision resolution method 해시 함수에 의해 특정 인덱스 값이 정해지게 되면 c - universal function이기 때문에 충돌이 발생할 수 밖에 없다. 충돌이 발생했다는 것은 내가 삽입하려고 하는 슬롯에 이미 다른 key value 데이터가 저장되어 있는 것. 그럼 다른 어느 곳에 저장해야 될까? 에 대한 것을 collision resolution method이다. 대표적인 방법 중 하나 Open addressing인데 그 방식은 3가지로 나눌 수 있다. 1. linear probing - 한칸씩 2. quadratic probing - 제곱칸씩 3. double hashing - 해시함수 두개 set 함수 : key 값이 해시테이블에 있으면 update하고 아니면 insert (upsert) set(key, value=N.. 2021. 12. 31.
#5 python의 메모리 할당과 관리 (Garbage Collection) https://hkim-data.tistory.com/183 #4 python의 메모리 할당과 관리 (Class와 self) https://hkim-data.tistory.com/182 #3 python의 메모리 할당과 관리 (Stack & Heap Memory) https://hkim-data.tistory.com/181 #2 python의 메모리 할당과 관리 (Everything is object in Python) 2021.12.29 -.. hkim-data.tistory.com 지난 포스팅에 이어 이번엔 python의 가비지 컬렉션이 어떻게 동작하는지 알아보도록 하겠다. python에서는 가비지 컬렉션을 레퍼런스 카운팅을 통해 Number of references가 0이 될 때 메모리 할당을 해제.. 2021. 12. 30.
#4 python의 메모리 할당과 관리 (Class와 self) https://hkim-data.tistory.com/182 #3 python의 메모리 할당과 관리 (Stack & Heap Memory) https://hkim-data.tistory.com/181 #2 python의 메모리 할당과 관리 (Everything is object in Python) 2021.12.29 - [Comuter Science] - #1 python 메모리 구조 #1 python 메모리 구조 최근 기술면접에서 메모.. hkim-data.tistory.com 지난 포스팅에 이어서 이번엔 class 수준에서 어떻게 메모리가 할당되고 삭제되는지 알아보자. 위와 같이 Car 클래스를 선언했다고 하자. Car 클래스에서는 생성자 init 메서드와 getWheels 메서드가 있다. main .. 2021. 12. 29.
#3 python의 메모리 할당과 관리 (Stack & Heap Memory) https://hkim-data.tistory.com/181 #2 python의 메모리 할당과 관리 (Everything is object in Python) 2021.12.29 - [Comuter Science] - #1 python 메모리 구조 #1 python 메모리 구조 최근 기술면접에서 메모리 영역에 대한 질문을 받았는데, 예전 학부 수업때 잘 공부했고 당연히 알고 있다고 생각했는데 당황 + hkim-data.tistory.com 이전 포스팅에 이어 이제 실제 Stack과 Heap 메모리에서 어떻게 동작하는지 알아보자. 백그라운드 메모리 구성은 모든 프로세스가 일부 메모리와 함께 운영 체제에 의해 할당된다. 마찬가지로 python 인터프리터는 실행을 위해 메모리를 할당받는데, 이는 파이썬의 버전.. 2021. 12. 29.
#2 python의 메모리 할당과 관리 (Everything is object in Python) 2021.12.29 - [Comuter Science] - #1 python 메모리 구조 #1 python 메모리 구조 최근 기술면접에서 메모리 영역에 대한 질문을 받았는데, 예전 학부 수업때 잘 공부했고 당연히 알고 있다고 생각했는데 당황 + 갑자기 머리 하얘짐 으로 대답을 제대로 못했다. 충격을 받고 다 hkim-data.tistory.com 이전 포스팅에 이어서 실제로 python에서 어떻게 메모리가 할당되고 해제되는지 알아보고자 한다. Everything is object in Python C에서는 x = 10을 실행하게 되면 x에 주소 값이 할당되고, 그 메모리에 10이라는 값이 들어간다. 그러나 python에서는 x = 10을 실행하게 되면 1. 10이라는 integer 객체가 메모리에 생성된.. 2021. 12. 29.

티스토리툴바