Vamos ser Programador com Devfon

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

class hashTable:     def __init__(self):         self.size = 10         self.table = [[] for _ in range(self.size)]       def hashfunc(self, key, size):         return key % size       def insert(self, key, value):         position = self.hashfunc(key, self.size)         key_exists = False         bucket = self.table[position]         # 동일 key 값 사용 여부 검사         for i, kv in enumerate(bucket):             k, v = kv             if key == k:                 key_exists = True                 break         # key 값 존재하는 경우 value replace         if key_exists:             bucket[i] = ((key, value))         # 존재하지 않는 경우 key-value 쌍 추가         else:             bucket.append((key, value))       def search(self, key):         position = self.hashfunc(key, self.size)         bucket = self.table[position]         for i, kv in enumerate(bucket):             k, v = kv             if key == k:                 return v       def delete(self, key):         position = self.hashfunc(key, self.size)         key_exists = False         bucket = self.table[position]         for i, kv in enumerate(bucket):             k, v = kv             if key == k:                 key_exists = True                 break         if key_exists:             del bucket[i]             print('Key {} deleted'.format(key))         else:             print('Key {} not found'.format(key))

cs

underscore

• index가 필요없는 for문을 작성할 경우에 사용 가능

for _ in range(10):
    print("hello")

enumerate

• 순서가 있는 자료형(리스트, 튜플, 문자열)을 입력으로 받아 index 값을 포함하는 enumerate 객체를 리턴

for i, name in enumerate(['body', 'foo', 'bar']):
    print(i, name)

0 body
1 foo
2 bar

• enumerate를 for문과 함께 사용하면 자료형의 현재 순서와 그 값을 쉽게 알 수 있음
• for문처럼 반복되는 구간에서 객체가 현재 어느 위치에 있는지 알려주는 index 값이 필요할 때 enumerate 함수를 사용하면 매우 유용

Tuple의 packing과 unpacking

1. Packing: Tuple에 여러 개의 값을 넣는 것

>>> a = 5
>>> b = 'test'
>>> c = a, b
>>> print(c) 
(5, 'test')

2. Unpacking: 패킹된 Tuple에서 여러 개의 값을 꺼내오는 것

>>> a = (63, 'building')
>>> b, c = a
>>> b
63
>>> c
'building'

Hash Table(해쉬 테이블)

Introduction

• 테이블에 저장되는 데이터는 Key와 Value가 한 쌍을 이룸
• Key가 존재하는 Value는 저장할 수 없으며, 모든 key는 중복되지 않음
• 좋은 해쉬 함수는 '충돌을 덜 일으키는 해쉬 함수'
• 일반적인 해쉬 함수(remainder method)의 개선안
  1. 자릿수 폴딩(Folding Method): 자릿수를 균등한 조각으로 나누어 각각의 값을 더한 후, 그 값의 remainder를 key값으로 설정
     • ex) 436-555-4601이라는 값을 두 자리로 쪼깨어 더함
     • 43 + 65 + 55 + 46 + 01 = 210
     • 210 % 11 = 1으로 1의 key값을 가지게 됨
     • 각각의 조각을 reverse하여 더하는 folding method도 존재
       • ex) 43 + 56 + 55 + 64 + 01 = 219
  2. 중간 제곱법(Mid-Square Method): Value를 제곱한 후 가운데 값의 remainder를 key값으로 설정
     • ex) 44 ^ 2 = 1,936
     • 93 % 11 = 5로 5의 key값을 가지게 됨
  3. Ordinal Value의 활용: 문자열을 구성하는 각각의 문자의 ASCII 값을 모두 더해 나온 결과의 remainder를 key 값으로 설정하는 방법
     • ex) 'cat' = 99 + 97 + 116 = 312
     • 312 % 11 = 4로 4의 key값을 지니게 됨
     • 그러나 이는 anagram의 단어들이 모두 같은 값을 지니게 된다는 단점이 있음
       • 해결 방안: weighting factor의 추가
       • 'cat' = 99*1 + 97*2 + 116*3
• 충돌 문제의 해결안

• Open Addressing: 해쉬 테이블에서 다음 open된 slot을 찾는 방법

  1. 선형 조사법(Linear Probing): hash function에 의해 저장되어야 하는 slot의 다음 slot들을 차례로 확인하며 빈 slot을 찾아가는 방법
     • ex) 77, 44, 55는 모두 0번 index에 들어가야 하는 value들
     • 그러나 77이 0번 index를 차지하고 있기 때문에 44는 1번 index에, 55는 0, 1번 index가 꽉찬 것을 확인하고 비어있는 2번 index에 저장하는 방법
     • 선형 조사법의 단점은 Clustering이 생긴다는 것
       • 즉, slot들을 골고루 사용하는 것이 아닌 특정 지역의 slot들만 과도하게 사용되는 경향이 생김
  2. 이차 조사법(Quadratic Probing): hash function에 의해 저장되어야 하는 slot 위치에 + 1, + 4, + 9 등을 더해 slot들이 고르게 분배되도록 하는 방법
     • ex) 77, 44, 55의 value들을 저장해야 함
     • 77은 0번 index에 44는 0 + 1으로 1번 index에 그리고 55는 0 + 4로 4번 index에 저장시키게 됨

• Close Addressing(Chaining): 각각의 slot에 item들이 여러 개 저장될 수 있도록 구현하는 방법

• http://blog.chapagain.com.np/hash-table-implementation-in-python-data-structures-algorithms/ 

해쉬 테이블 구현에 필요한 기본 연산

• HashTable(): 새로운 HashTable을 생성
• put(key, val): key와 value을 쌍으로 HashTable에 추가함. Key 값이 이미 존재하면 old value를 new value로 변경
• get(key): key가 주어지면 그에 맞는 value값을 반환
• del: Key 값을 이용하여 Key-Value 쌍을 삭제
• len(): Key-Value 쌍의 크기 반환
• in: HashTable에 Key 값이 있는지의 여부를 반환

해쉬 테이블의 로직

class HashTable:
	def __init__(self):
		self.size = 11
		self.slots = [None] * self.size
		self.data = [None] * self.size

• Key 값들을 담는 slots라는 list 생성
• slots라는 list와 평행하게 존재하며, value를 담을 data list 생성
• HashTable의 크기는 소수로 설정하는 것이 충돌 문제 해결에 효과적

def put(self, key, value):
	hashval = self.hashfunction(key, len(self.slots))

	if self.slots[hashvalue] == None:
		self.slot[hashvalue] = key
		self.data[hashvalue] = data

	else:
		# original key값이 같을 경우 replace
		if self.slots[hashvalue] == key:
			self.data[hashvalue] = data
		else:
			nextslot = self.rehash(hashvalue, len(self.slots))
			# slot이 차있고, original key값과 rehash 값이 다르면 계속 rehash
			while self.slots[nextslot] != None and \
							self.slots[nextslot] != key:
				nextslot = self.rehash(nextslot, len(self.slots))
		
			# slot이 비어있으면 slot에 key와 data 입력
			if self.slots[nextslot] == None:
				self.slots[nextslot] = key
				self.data[nextslot] = data

			# rehash 값과 original key 값이 같을 경우 replace
			# 즉, rehash 통해 이미 자리한 경우
			else:
				self.data[nextslot] = data

def hashfunction(self, key, size):
	return key % size

# Linear Probing 사용
def rehash(self, oldhash, size):
	return (oldhash+1) % size

• nextslot의 rehash를 탈출하는 조건은 2가지로 분류
  1. rehash를 통해 얻은 slot이 비어있는 경우: 빈 자리에 key와 data를 삽입
  2. rehash를 통해 얻은 slot의 key값과 입력 값의 key 값이 같은 경우: value를 replace
• rehash function으로는 Linear Probing 사용

def get(self, key):
	startslot = self.hashfunction(key, len(self.slot))

	data = None
	stop = False
	found = False
	position = startslot

	while self.slots[position] != None and
					not found and not stop:
		# 값을 찾은 경우 while문 탈출
		if self.slots[position] == key:
			found = True
			data = self.data[position]
		else:
			position = self.rehash(position, len(self.slots))
			# 최초의 slot으로 돌아오지 않도록 제어
			if poisition == startslot:
				stop = True

	return data

def __getitem__(self, key):
	return self.get(key)

def __setitem__(self, key, data):
	self.put(key, data)

• position의 rehash를 탈출하는 조건은 3가지로 분류
  1. rehash를 통해 얻은 position 값이 입력 값의 key 값과 일치하는 경우: 검색에 성공한 case
  2. rehash를 통해 얻는 position 값이 hashfucntion으로 얻은 값과 일치하는 경우: 원값으로 돌아올 때 까지 탐색에 실패한 case
  3. rehash를 통해 얻은 position 값의 slot이 비어있는 경우: Linear Search를 하다가 값이 존재하지 않는 case
• [] 연산의 사용을 위해 __getitem__과 __setitem__ method를 overloading

전체 코드

Priority Queue(우선순위 큐)

Introduction

• 우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
• 우선순위 큐를 구현하는 방법
  1. 배열을 기반으로 구현: 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 당기는 연산을 수반해야 함 + 원소의 삽입 위치를 찾기 위해 배열의 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있음
  2. 연결 리스트를 기반으로 구현: 원소의 삽입 위치를 찾기 위해 첫 번째 노드에서부터 마지막 노드까지에 저장된 데이터들과 우선순위의 비교를 진행해야 할 수도 있음
  3. 힙을 이용하여 구현
• 우선순위 큐의 logarithmic한 성능을 보장하기 위해 항상 이진 트리의 균형을 맞추어야 함
• 완전 이진 트리(Complete Binary Tree)의 구조를 이용하여 트리의 균형을 맞춤
• 힙을 기반으로 한 우선순위 큐는 트리의 높이에 해당하는 수만큼 비교연산(삽입 및 삭제를 위한)을 진행하게 됨
  • 힙 기반 데이터 저장의 시간 복잡도: O(logN)
  • 힙 기반 데이터 삭제의 시간 복잡도: O(logN)

우선순위 큐 구현에 필요한 기본 연산

• BinaryHeap(): 새로운 Binary Heap을 생성
• insert(item): heap에 새로운 원소 추가
• findMin(): heap에서 가장 작은 값을 가진 원소의 값 반환
• delMin(): heap에서 가장 작은 값을 가진 원소의 값 반환 후 삭제
• isEmpty(): heap의 empty 여부를 boolean 값으로 반환
• size(): heap의 원소 개수 반환
• buildHeap(list): 원소들을 지닌 list로 heap을 새로이 생성

우선순위 큐의 로직

# 클래스와 생성자
class BinaryHeap:
	def __init__(self):
			self.heapList = [0]
			self.currentSize = 0

• 배열의 0번 index는 사용하지 않음
• 따라서 힙에 저장된 노드의 전체 개수와 마지막 노드의 index가 일치

def percUp(self, i):
	# parent 원소가 0보다 큰 index에 위치해 있을 때 까지 반복
	while i // 2 > 0:
		# 추가된 원소가 Parent 원소보다 우선순위가 높을 경우 두 값을 swap
		if self.heapList[i] < self.heapList[i // 2]:
			tmp = self.heapList[i // 2]
			self.heapList[i // 2] = self.heapList[i]
			self.heapList[i] = tmp
		i = i // 2

def insert(self, item):
	self.heapList.append(k)
	self.currentSize = self.currentSize + 1
	self.percUp(self.currentSize)

• 가장 쉽고 효율적인 원소 추가 방법은 list의 가장 끝에 원소를 새로이 추가해주는 것
• 새로이 추가된 원소와 그 Parent의 값을 비교하며, 추가된 원소의 우선순위가 더 높을 경우 두 값을 swap하는 방식을 반복해서 수행
• 우선순위가 높은 신규 원소의 값을 위의 level로 올리는 과정에서 heap의 구조적 특징을 다시 회복

def percDown(self, i):
	# Child 원소가 Heap의 사이즈보다 작거나 같을 때 까지 반복
	while (i * 2) <= self.currentSize:
		# 우선순위가 더 작은 child 노드의 값 선정
		mc = self.minChild(i)
		# child 노드보다 우선순위가 낮을 경우, 두 값을 swap
		if self.heapList[i] > self.heapList[mc]:
			tmp = self.heapList[i]
			self.heapList[i] = self.heapList[mc]
			self.heapList[mc] = tmp
		# 다음 비교를 위해 자식 노드의 index로 변경
		i = mc

def minChild(self, i):
	# Left child node만 있는 경우(완전 이진 트리이므로)
	if i * 2 + 1 > self.currentSize:
		return i * 2

	# 두 개의 child node가 모두 있는 경우
	else:
		if self.heapList[i*2] < self.heapList[i*2+1]:
			return i * 2
		else:
			return i * 2 + 1

def delMin(self):
	retval = self.heapList[1]
	self.heapList[1] = self.heapList[self.currentSize]
	self.currentSize = self.currentSize - 1
	self.heapList.pop() # 이미 루트 자리로 이동하였으므로, 제거
	self.percDown(1)
	return retval

• 루트 노드의 원소가 가장 우선순위가 높은 원소이기 때문에 우선순위가 높은 원소를 찾는 것은 매우 쉬움
• 어려운 부분은 루트 노드를 삭제한 후 다시금 heap의 구조를 정상적으로 회복시키는 것
• 가장 끝에 있는 원소를 루트 노드의 자리로 이동
  • 루트 노드로 이동한 원소와 해당 노드의 자식 노드들의 우선순위를 비교해가며 swap 해가는 방식을 통해 다시 heap의 특성을 갖출 수 있음

def buildHeap(self, alist):
	i = len(alist) // 2
	self.currentSize = len(alist)
	self.heapList = [0] + alist[:]
	while(i > 0):
		self.percDown(i)
		i = i - 1

• heap이 완전 이진 트리로 구성되어 있기 때문에 i는 항상 최하단의 바로 윗 레벨에서 시작하게 됨
• i를 줄여나가며 percDown 연산을 수행하기 때문에 결국 모든 원소의 값이 자신의 우선순위에 맞는 자리를 찾아가게 됨

전체 코드

[Reference]
Problem Solving with Algorithms and Data Structure
윤성우의 열혈 자료구조