힙(Heap) 대표 문제 풀이 : 더 맵게 힙(Heap) 최대/최소 원소를 O(1) 시간으로 빠르게 찾을 수 있음 종류 : 최대 힙(max heap), 최소 힙(min heap) 연산 : 힙 구성(heapify, O(n log n)), 삽입(insert, O(log n)), 삭제(remove, O(log n)) 힙의 구현과 응용 최대 힙을 기준으로 root node에 최댓값이 위치 완전 이진트리로 구성돼 있으며, 배열을 이용해서 구현 가능 응용 : 정렬(Heapsort), 우선순위 큐 (priority queue) Python에서의 힙 적용 연산 : heapify(list), heappop(list), heappush(list, value) import heapq # 리스트 L로부터 min heap 구성..
해시(Hash) 대표 문제 풀이 : 완주하지 못한 선수 해시(Hash) 만약 이름 대신 번호가 주어졌다면? => 선형 배열 이름을 키(key)로 하여 해시 함수(Hash function)를 통해 해시 테이블(hash table)에 매핑 풀이 (1) 사전(Dictionary)의 원소들을 해시를 이용해 O(1) 시간에 접근 가능 사전을 활용하여 "이름 : 이름 수"로 저장하여 마지막 남은 사람의 이름 반환 코드 get(x, 0) : x라는 키가 존재하면 해당 값을, 존재하지 않으면 0을 반환 최종 시간 복잡도 : O(n) def solution(participant, completion): d = {} # O(n) for x in participant: d[x] = d.get(x, 0) + 1 # O(n) ..
큐(Queue) 자료를 보관할 수 있는 선형 구조 선입선출(FIFO) 구조로 enqueue 연산과 dequeue 연산 존재 size, isEmpty, enqueue는 스택의 메소드와 같고, dequeue와 peek만 다름 배열을 이용하여 구현 Python 리스트와 메서드 이용 class Queue: def __init__(self): self.data = [] # 큐의 원소의 수 def size(self): return len(self.data) # 큐가 비어 있는지 판단 def isEmpty(self): return self.size() == 0 # 데이터 원소 추가 def enqueue(self, item): self.data.append(item) # 가장 앞 데이터 원소 제거/반환 def dequ..
연결 리스트(Linked Lists) (1) 추상적 자료구조(Abstract Data Structures) 내부 구현은 숨겨져 있는 상태로 사용하는 자료구조 데이터 : 정수, 문자열, 레코드 등 연산 : 삽입, 삭제, 순회, 정렬, 탐색 등 기본적 연결리스트 앞에 있는 노드가 뒤에 있는 노드를 가리키도록 되어있는 자료구조 형태 노드 : Data(문자열, 레코드, 또 다른 연결 리스트 등), Link (next)가 담김 Head : 연결 리스트의 가장 앞의 노드를 가리키는 포인터 Tail : 연결 리스트의 가장 마지막 노드를 가리키는 포인터 자료구조 정의 노드 클래스 class Node: def __init__(self, item): self.data = item self.next = None 연결리스트 ..
