개발기록장

우선순위 큐 우선순위 큐는 일반적인 큐와 다르게 우선 순위가 높은 요소가 먼저 나가는 개념이다. 여기서 주의할 점은 우선순위 큐는 자료구조가 아닌 개념이다. 따라서 우선순위 큐를 구현하는 방법은 다양하게 존재할 수 있다. 그중 힙은 우선순위 큐를 구현하기 위한 가장 적합한 방법이다. 힙 (Heap) 힙은 자료구조이며, 이진 트리 형태이다. 우선순위가 높은 요소를 루트에 두기위해 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있다. 힙의 특징 우선순위가 가장 높은 것을 루투에 두고, 항상 루트가 먼저 나간다. 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙 두가지로 나뉜다. (오름차순이냐 내림차순이냐 정도의 차이) 파이썬에서는 heapq 혹은 PriorityQueue 모듈을 통해..

해시 테이블 해시 테이블은 key-value 시스템을 이용하여 데이터를 저장하는 자료구조다. 해시 테이블은 한정된 배열 공간에 key를 index로 변환하여 그 index에 각각의 value들을 저장한다. key를 index로 변환할 때는 해시함수가 사용된다. ** 해시함수: 입력받은 값을 특정 범위 내의 숫자로 변경하는 함수를 말한다. 간단하게 예를 들면 pizza, cake, taco는 key 이고, 이 메뉴들의 가격이 value라고 하면 각 key들을 hash function에 넣어 구한 값(=Hasing해서 나온 값)이 index가 되고, 이렇게 구한 인덱스에 value를 저장한다. 이 배열이 해시 테이블이다. 해시테이블에서는 index를 bucket이라고 부르며 각 요소에는 key와 value를..

deque를 이용한 Queue 구현 deque는 스택과 큐가 합쳐진 자료구조라고 생각하면 된다. deque는 list와 사용방법이 거의 비슷하지만, 첫번째 요소를 제거하는 popleft()함수를 지원하고 있어서 이를 이용하면 상수시간으로 첫번째 요소를 제거할 수 있다. 따라서 파이썬으로 queue를 구현할 때 deque를 사용하면 좋다. from collections import deque q = deque() # queue 생성 q.append(1) # EnQueue (=요소 추가) q.append(2) q.append(4) print(q.popleft()) # DeQueue(=첫번째 요소 삭제) >> 1 q.append(8) print(len(q)) >> 3

연결 리스트 연결리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조다. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다. 맨 첫번째 노드를 Head라고 한다. 각 노드에 알파벳으로 써놓은 부분이 데이터 영역(=노드의 값)이며 동그라미 부분이 포인터 영역으로 다음 노드를 가리키는 역할을 한다. 특징 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다. 탐색은 O(n)이 소요된다. 요소를 추가하거나 제거할 때는 O(1)이 소요된다. Singly Linked List, Doubly Linked List, Circular Linked List가 존재한다. 연결 리스트에서의 요소 삭제 1. 삭제할 요소를 선택 2. 삭제할 요소의 이전 요소가 가리키는 포인터를 삭제할 요소의 다음 요소에..