목록알고리즘/알고리즘 Basic (7)

소프트웨어에 대한 모든 것

[파이썬] LRU Cache 구현 (Least Recently Used Cache)

LRU Cache란? 가장 오랫동안 사용되지 않은 (참조되지 않은) 페이지(데이터)를 교체하는 기법 캐시의 크기는 한정적이기 때문에 자주 사용되는 데이터는 캐시에 남기고, 자주 사용되지 않는 캐시는 삭제해서 제한된 리소스내에서 데이터를 빠르게 접근할 수 있게 합니다. 구현 방법 1) OrderedDict 활용 파이썬에서 OrderedDict 클래스를 제공합니다. OrderedDict는 사전(해시) 자료구조인데 데이터를 삽입한 순서를 보장합니다. 이러한 OrderedDict 클래스의 특징을 이용해 LRU Cache를 구현할 수 있습니다. from collections import OrderedDict class LRUCache: def __init__(self, capacity): # 최대 캐시 크기 se..
알고리즘/알고리즘 Basic 2022. 3. 29. 13:21
[파이썬] Floyd's Cycle Detection 알고리즘

링크드 리스트에서 사이클(순환)을 찾는 알고리즘 중에 Floyd's Cycle Detection Algorithm (플로이드 순환 찾기 알고리즘)이 있습니다. 두 포인터를 이용해서 첫 번째 포인터는 one step 이동(slow pointer) 두 번째 포인터는 two step 이동하면서(fast pointer) 두 포인터가 만나게 된다면 리스트는 순환 사이클이 존재하는 것입니다. Floyd's Cycle Detection 알고리즘 예제 코드 class ListNode: def __init__(self, val): self.val = val self.next = None def has_cycle(head): slow = head fast = head while fast and fast.next: # mo..
알고리즘/알고리즘 Basic 2022. 3. 3. 09:38
[파이썬] 배열을 바이너리 서치 트리로 변환 ( array to height balanced Binary Search Tree)

주어진 (정렬된) 배열에 대해서 높인 균형 이진탐색 트리로 변환하는 코드입니다. 재귀적으로 방법으로 간단히 해결할 수 있습니다. class TreeNode(): def __init__(self, val): self.val = val self.left = None self.right = None def array_to_bst(nums): if not nums: return None # 중앙 인덱스 mid_idx = len(nums)//2 # 중앙값으로 노드 생성 node = TreeNode(nums[mid_idx]) # left subtree 구성 # values < nums[mid_idx] node.left = array_to_bst(nums[:mid_idx]) # right subtree 구성 # va..
알고리즘/알고리즘 Basic 2022. 2. 27. 12:27
[파이썬] 바이너리 서치 트리 이해 및 구현

바이너리 서치 트리에(Binary Search Tree) 대해서 알아보겠습니다. 기본적인 내용은 다들 알고 계시지만 insert(), search(), delete()를 직접 구현한 분들은 많지 않을 것 같습니다. 학부 때 자료구조나 알고리즘 수업 시간에 구현을 했었을 수도 있지만 막상 당장 지금 구현하라고 하면 키보드에서 손이 멈칫 멈칫 할 것입니다. 바이너리 서치 트리(이하 BST) 구조 노드의 왼쪽 서브트리는 노드의 key 값 보다 작은 값을 갖는 노드로 구성 노드의 오른쪽 서브트리는 노드의 key 값 보다 큰 값을 갖는 노드로 구성 왼쪽과 오른쪽 서브트리도 각각 binary search tree로 구성되어야 함 BST 시간 복잡도 BST는 일반적으로 삽입, 탐색, 삭제는 O(logn)의 시간 복잡..
알고리즘/알고리즘 Basic 2021. 12. 19. 18:15
[파이썬] 덱 vs 리스트 속도 차이? (deque vs list speed 차이)

덱과 리스트? 여러분은 어떤 차이를 두고 두 자료구조를 적절하게 사용하시나요? 둘 다 사용상에는 큰 차이가 없어 보입니다. 그렇지만, 이 자료구조를 어떤 상황에서 어떻게 사용하느냐에 따라서 굉장히 큰 속도 차이가 발생합니다. 덱과 리스트의 시간 복잡도를 비교한 테이블입니다. Deque List Time Complexity deque에는 appendleft() 함수와 popleft() 함수가 있습니다. 평균적인 시간복잡도는 O(1)입니다. List는 insert() 함수가 있는데 O(n)의 시간 복잡도입니다. 왜 이런 시간 차이가 발생할까요??? Deque 덱은 어떤 형식으로 자료의 형태를 유지할까요? 이름은 뭔가 큐와 비슷해보입니다. FIFO 형식을 유지할 것 같습니다. Deque은 A Double-en..
알고리즘/알고리즘 Basic 2021. 11. 29. 06:14
이진 트리 레벨 순회 (Binary Tree Level Order Traversal)

이진 트리 레벨 순회는 이진 트리의 낮은 레벨의 노드부터 순차적으로 방문합니다. 트리를 너비우선탐색(BFS(Breadth first search)) 하는 것 입니다. 위 그림에서, Level1 - 1 Level2 - 2, 3 Level3 - 4, 5, 6, 7 즉, 1->2->3->4->5->6->7 이렇게 방문합니다. 1 2 4 5 3 6 7 구현 (큐 자료구조) 큐 자료구조를 사용해서 재귀적 방법의 시간 복잡도를 O(n)으로 줄일 수 있습니다. 시간 복잡도 : O(n) 공간 복잡도 : O(n) 소스 코드 from collections import deque class Node: def __init__(self, val): self.val = val self.left = None self.right =..
알고리즘/알고리즘 Basic 2021. 11. 20. 08:20
[파이썬] 바이너리 서치 (이진 탐색)

바이너리 서치에 대해서 알아간다. 탐색 범위를 절반씩 줄여가면서 찾아간다. 바이너리 서치의 대상은 정렬되어 있어야 한다. 시간 복잡도 : O(logn) 코드를 보면 확실하다 바이너리 서치 구현 def binary_search(nums, target): left = 0 right = len(nums) while left < right: pivot = (left + right) // 2 if nums[pivot] == target: return pivot elif nums[pivot] < target: left = pivot + 1 else: right = pivot return -1 # 이진 탐색 대상은 정렬되어 있어야 함 nums = [1, 3, 5, 7, 9, 10, 15, 20, 25] target ..
알고리즘/알고리즘 Basic 2021. 11. 10. 06:08
Prev 1 Next