Study/알고리즘

해싱 (hashing) 데이터의 키 값을 간단한 함수를 사용해 변환한 값을 리스트의 인덱스로 사용하여 데이터를 리스트에 저장하는 절차로 공간 낭비를 줄이면서 키 값을 이용한 데이터 검색의 시간 복잡도를 가능하다면 O(1)로 유지하기 위해 사용. 해시 함수 (hash function) : 해싱에 사용되는 함수 해시 값 (hash value) : 해시 함수가 계산한 값 (=해시 주소) 해시 테이블 (hash table) : 데이터가 해시 값에 따라 저장된 구조 해시 함수를 통해 큰 키 공간을 작은 주소 공간으로 변환. python에서는 hash() 함수를 통해 해싱을 진행할 수 있다. 해시 테이블 (hash table) 해시 테이블 ht는 m개의 버킷(bucket) ht[0], ht[1], ht[2], ....

힙 (Heap) 힙은 완전 이진 트리로서 부모 노드 키값의 우선순위가 자식 노드 키 값의 우선순위보다 높은 자료 구조. 힙은 완전 이진 트리의 형태와 노드의 키 값에 대한 힙의 조건을 반드시 유지해야 한다. 완전 이진 트리 : 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리. 힘의 종류 MAX 힙 : 키 값이 큰 항목이 우선순위가 높은 것으로 간주하므로 루트 노드의 키가 가장 큼 MIN 힙 : 키 값이 작은 항목이 우선순위가 높은 것으로 간주하므로 루트 노드의 키가 가장 작음 힙과 우선순위 큐 힙 자료구조는 파이썬에서 우선순위 큐를 구현하기 위해 사용된다. 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 활용 예시 물..

큐(Queue) 한 쪽 끝 위치(Rear)에서 새로운 항목을 삽입(Enqueue)하고, 다른 한 쪽 끝 위치(Front)에서 기존 항목을 삭제 및 반환(Dequeue)하는 논리적 선형 구조 시간 순으로 먼저 삽입된 항목이 먼저 삭제되는 선입선출(FIFO : First-In, First-Out) 구조 Rear(뒤)에서만 삽입이 이루어지고 Front(앞)에서만 삭제가 이루어지는 특수한 리스트. python에서의 큐 python 리스트에서의 구현 enqueue : O(1) (append()) dequeue : O(N) (삭제 후 자리이동) 단순 연결 리스트로 구현 enqueue : O(N) dequeue : O(1) (pop()) 환형 연결 리스트 : enqueue dequeue 모두 O(1) 큐에 적용 가능..

스택(Stack) 한 쪽 끝(Top)에서만 새로운 항목을 삽입(Push)하거나 기존 항목을 삭제 및 반환(Pop)하는 논리적 선형 구조. 시간 순으로 먼저 삽입된 항목이 나중에 삭제되는 후입선출(LIFO : Last-In, First-Out) 구조. Top에서만 삽입, 삭제가 이루어지는 특수한 리스트.(List) python에서의 스택 python 리스트(동적 배열)에 의한 구현 -> push pop 연산 모두 O(1) 단순 연결 리스트에 의한 구현 -> push pop 연산 모두 O(1) 스택에 적용 가능한 주요 연산 Stack() : 빈 스택 생성 push(item) : 기존 Top 다음 위치에 item 삽입 pop() : Top 위치에 존재하는 item 삭제 및 반환 peek() : Top 위치에 ..