소프트웨어에 대한 모든 것

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

링크드 리스트에서 사이클(순환)을 찾는 알고리즘 중에 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..

주어진 (정렬된) 배열에 대해서 높인 균형 이진탐색 트리로 변환하는 코드입니다. 재귀적으로 방법으로 간단히 해결할 수 있습니다. 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..

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

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

이진 트리 레벨 순회는 이진 트리의 낮은 레벨의 노드부터 순차적으로 방문합니다. 트리를 너비우선탐색(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 =..

바이너리 서치에 대해서 알아간다. 탐색 범위를 절반씩 줄여가면서 찾아간다. 바이너리 서치의 대상은 정렬되어 있어야 한다. 시간 복잡도 : 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 ..