시행착오 기술 블로그

해쉬 구조

Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조

• Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
• 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄
• 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
• 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨

알아둘 용어

• 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
• 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address): Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
• 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음

자료 구조 해쉬 테이블의 장단점과 주요 용도

• 장점
  • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
• 단점
  • 일반적으로 저장공간이 좀더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현시 (중복 확인이 쉽기 때문)

충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 사용하기)

1. Chaining 기법

• 개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

2. Linear Probing 기법

• 폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
  • 저장공간 활용도를 높이기 위한 기법

참고: 해쉬 함수와 키 생성 함수

• 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있음
• 유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)
  • 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능

시간 복잡도

• 일반적인 경우(Collision이 없는 경우)는 O(1)
• 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)

해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1) 이라고 말할 수 있음

검색에서 해쉬 테이블의 사용 예

• 16개의 배열에 데이터를 저장하고, 검색할 때 O(n)
• 16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)

파이썬으로 해시 테이블 구현하기

1. 해시테이블 생성 (list comprehension 문법: https://www.fun-coding.org/PL&OOP5-2.html)

# 슬롯을 모아놓은 해시 테이블
hash_table = list([0 for i in range(10)])
hash_table # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

2. 해시함수 생성 : key값을 입력받아 고정된 길이의 해시주소를 반환

# Division 법 (나누기를 통한 나머지 값을 사용하는 기법)

def hash_func(key): 
    return key % 5

3. 해시테이블 내 해시주소에 해당 데이터 저장

def storage_data(data, value):
    key = ord(data[0]) ## ord(): 문자의 ASCII(아스키)코드 리턴
    hash_address = hash_func(key)
    hash_table[hash_address] = value

4. 해시테이블 내에서 데이터 검색 (검색속도 매우 빠름)

def get_data(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]

충돌(Collision) 방지 알고리즘 -    1.  Chaining 기법 (Open Hashing 기법)

• 충돌이 일어나면, 링크드 리스트 자료 구조를 사용해서 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

1. 해시 테이블 생성

hash_table = list([0 for i in range(8)])

2. key 값 반환

def get_key(data):
    return hash(data)

3. 동일한 길이의 해시주소를 반환해주는 해시함수 생성

def hash_function(key):
    return key % 8

4. 충돌 발생시 linkedList 자료형으로 해시테이블 밖에 데이터를 저장하는 함수 생성

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    # hash_address에 데이터가 들어가 있는 경우 
    if hash_table[hash_address] != 0:
        # 링크드리스트 순회하며
        for index in range(len(hash_table[hash_address])):
            # 기존에 해당 키가 존재하면 값 덮어쓰고
            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] = value
                return
        # 신규 키면 저장한다. 단,
        # key-value 형태로 저장해야 추후에 동일한 해시주소를 갖는 데이터 끼리 구분할 수 있다.
        hash_table[hash_address].append([index_key, value])
        
    # 주소에 비어있는 경우 바로 저장
    else:
        hash_table[hash_address] = [[index_key, value]]

5. 데이터 검색하는 함수 생성

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        # 링크드리스트 전체를 반복하며 값이 존재하는지 확인한다
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                return hash_table[hash_address][index][1]
        return None
    else:
        return None

6. 확인

Dd와 Data는 동일한 key를 갖기에 hashAddress 또한 동일하다

이때 링크드 리스트를 이용해 key-value 형태로 save_data()한다.

또한 검색할 때 역시 링크드 리스트 내 key를 이용해 read_data()한다.

print (hash('Dave') % 8) # 0
print (hash('Dd') % 8) # 2
print (hash('Data') % 8) # 2

save_data('Dd', '1201023010')
save_data('Data', '3301023010')

read_data('Dd') 
# '1201023010'


hash_table
# [0,
#  0,
#  [[1341610532875195530, '1201023010'], [-9031202661634252870, '3301023010']],
#  0,
#  0,
#  0,
#  0,
#  0]

충돌(Collision) 방지 알고리즘 -    2. Linear Probing 기법 (Close Hashing 기법)

• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
  • 저장공간 활용도를 높이기 위한 기법

4. 충돌 발생시 해시 테이블 내 빈공간을 찾아 데이터를 저장하는 함수 생성

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    # hash_address에 데이터가 들어가 있는 경우 
    if hash_table[hash_address] != 0:
        # 비어있는 해시테이블 공간을 찾기 위해 순회하며
        for index in range(hash_address, len(hash_table)):
            # 빈공간 찾은 경우 저장
            if hash_table[index] == 0:
                hash_table[index] = [index_key, value]
                return
            # 기존에 해당 키가 존재하면 값 덮어쓰고
            elif hash_table[index][0] == index_key:
                hash_table[index][1] = value
                return
    # 주소에 비어있는 경우 바로 저장
    else:
        hash_table[hash_address] = [index_key, value]

5. 데이터 검색하는 함수 생성

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    # 해시테이블 내 해당 주소에 저장된 데이터가 있다면
    if hash_table[hash_address] != 0:
        # 그 주소부터 테이블 끝까지 순회하며
        for index in range(hash_address, len(hash_table)):
            # 빈공간이 나온다면 이 해시테이블에는 해당 값이 없다는 의미
            if hash_table[index] == 0:
                return None
            # 해당 데이터 찾은 경우 value를 반환한다
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
            
    # 해시테이블 내 해당 주소에 아무것도 없는 경우 none 을 리턴
    else:
        return None

배열 

• 같은 종류의 데이터를 효율적으로 관리하기 위해 사용
• 같은 종류의 데이터를 순차적으로 저장
• 장점:
  • 빠른 접근 가능
    • 첫 데이터의 위치에서 상대적인 위치로 데이터 접근(인덱스 번호로 접근)
• 단점:
  • 데이터 추가/삭제의 어려움
    • 미리 최대 길이를 지정해야 함

큐 

• 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
  • 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일
  • FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대

• Enqueue: 큐에 데이터를 넣는 기능
• Dequeue: 큐에서 데이터를 꺼내는 기능

리스트로 queue 자료구조 만들기

queue_list = list()

def enqueue(data):
	queue_list.append(data)

def dequeue():
	data = queue_list[0]
    del queue_list[0]
    return data



for index in range(10):
	enqueue(index)

len(queue_list) # 10

dequeue() # 0
dequeue() # 1
dequeue() # 2
dequeue() # 3
dequeue() # 4
...
dequeue() # 8
dequeue() # 9

Queue 자료구조는 어디에 많이 쓰일까?

멀티태스킹을 위한 프로세스 스케줄링 방식을 구현하기 위해 많이 사용된다. (운영체제)

Queue()로 큐 만들기 (가장 일반적인 큐, FIFO(First-In, First-Out))

import queue
data_queue = queue.Queue()

data_queue.put("funcoding")
data_queue.put(1)

data_queue.qsize() # 2
data_queue.get() # 'funcoding'

data_queue.qsize() # 1
data_queue.get() # 1

LifoQueue()로 큐 만들기 (LIFO(Last-In, First-Out))

import queue
data_queue = queue.LifoQueue()

data_queue.put("funcoding")
data_queue.put(1)

data_queue.qsize() # 2
data_queue.get() # 1
data_queue.get() # funcoding

PriorityQueue()로 큐 만들기

import queue
data_queue = queue.PriorityQueue()

data_queue.put((10, "korea"))
data_queue.put((5, 1))
data_queue.put((15, "china"))

data_queue.qsize() # 3

data_queue.get() # (5, 1)
data_queue.get() # (10, 'korea')
data_queue.get() # (15, "china")

덱 Deqeu()

양끝에서 넣고 빼는게 가능한 자료구조

from collections import deque
import sys

d = deque()

# 데이터 삽입
for i in range(1, 10):
    d.append(i)
print(d)

# 왼쪽에 삽입
d.appendleft(0)
print(d)

# 오른쪽에 삽입
d.append(10)
print(d)

# 왼쪽 pop
print(d[0])
d.popleft()

# 오른쪽 pop
print(d[len(d) - 1])
d.pop()

print(d)

스택

• 장점
  • 구조가 단순해서, 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.
• 단점 (일반적인 스택 구현시)
  • 데이터 최대 갯수를 미리 정해야 한다.
    • 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능함
  • 저장 공간의 낭비가 발생할 수 있음
    • 미리 최대 갯수만큼 저장 공간을 확보해야 함

스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적임. 이 경우, 위에서 열거한 단점이 있을 수 있음

• 데이터를 제한적으로 접근할 수 있는 구조
  • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
  • 큐: FIFO 정책
  • 스택: LIFO 정책

• 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름
  • LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
  • FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책
• 대표적인 스택의 활용
  • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• 주요 기능
  • push(): 데이터를 스택에 넣기
  • pop(): 데이터를 스택에서 꺼내기

파이썬으로 자료구조, 알고리즘 배우기

자료구조 학습 필요성

알고리즘 풀이를 위해 자료구조를 알 필요가 있다.

파이썬 문법에 익숙해지고 난 다음 시작하자.

입출력, 문자열, 리스트 등

* 파이썬 기초 문제풀이

https://www.fun-coding.org/daveblog.html 참고

자료구조란,

대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미한다.

데이터 특성에 따라 데이터를 구조화, 코드 상에서 효율적으로 데이터를 처리하기 위함.

ex) 우편번호, 학번 등

자료구조의 종류

배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등

알고리즘이란,

어떤 문제를 풀기 위한 절차와 방법

어떤 문제에 특정 입력을 넣으면, 원하는 출력을 얻을 수 있도록 만드는 프로그래밍

알고리즘의 성능

시간 복잡도, 공간복잡도를 기준으로 알고리즘의 성능을 평가한다.

개발 환경 설정 (아나콘다 없이)

1. 파이썬 컴파일러 설치 https://www.python.org/downloads/

2. 주피터노트북 설치

cmd 상에서 

> pip install --upgrade pip

> pip install jupyter

파이썬에 익숙해지기

파이썬 기초(문제풀이) 1 학습하기

"입력과 출력" 

print("Hello World") # 출력


print("%.4f" %3.141592)  #소수점 아래 4자리까지


first = input() # string으로 받아옴.
second = input()
print(type(first))
print(int(first) + int(second))


print("hello "*4)  # 반복 출력 (반복문 없이)


2**3 # 거듭제곱​

https://www.fun-coding.org/python-question1-answer.html

파이썬 기초(문제풀이) 2 학습하기

"조건문과 문자열"

digit1 = 10
digit2 = 2.2
string1 = "hello"
print(type(digit1))  # <class 'int'>
print(type(digit2))  # <class 'float'>
print(type(string1)) # <class 'str'>


code = '000660\n000000102\t12312312' # \t: 탭, \n: 줄바꿈
print(code)
# 000660
# 000000102	12312312


#조건문
digit = 100

if digit < 20:
    print('20보다 작습니다.') 
elif digit < 50:
    print('50보다 작습니다.')
else:
    print('50 이상의 수입니다.') # 이것에 해당

파이썬은 배열이 곧 리스트 [ ] list( )

# 인덱스를 이용해 값에 접근이 가능.
user_id = "2022001"
print(user_id[0:4]) # 2022 출력.  0~3 인덱스

문자열 다루는 다양한 함수1 strip()

### strip() 함수
#### 1. strip() : 양끝 공백문자 제거
#### 2. lstrip(): 왼쪽 공백문자 제거
#### 3. rstrip(): 오른쪽 공백문자 제거

#### 1. strip('.') : 양끝 '.' 문자 제거
#### 2. lstrip('.'): 왼쪽 '.' 문자 제거
#### 3. rstrip('.'): 오른쪽 '.' 문자 제거

myString = "a man goes into the room..."
print(myString) # a man goes into the room...

myString = "a man.goes into the room..."
print(myString.strip(".")) # a man.goes into the room

문자열 다루는 다양한 함수2 count(), find(), split()

count() 함수
str.count('a')
a의 갯수 반환

find() 함수
str.find('a')
0 또는 1 반환

split() 함수¶
str.split(",")
문자열을 잘라서 배열로 반환

https://www.fun-coding.org/python-question2-answer.html

파이썬 기초(문제풀이) 3 학습하기

"반복문과 리스트"

for 변수 in 반복할객체

(여기서 in 뒤에는 리스트, 튜플, 문자열, iterator, generator 등 순회가능한 데이터타입)

# range(1, 10)은 1~9까지 값
for num in range(1, 10):
    print(9,"x",num," = ", 9 * num)
    
# 문자열을 split한 배열
str = "[hello],[world],[i'm],[yujin]"
for s in str.split(','):
    print(s.strip("[]")) # 양끝 [ ] 문자 삭제

enumerate 반복문 동작시 인덱스 자동할당 (tuple 형태)

num_list = [0, -11, 31, 22, -44, -55]
for num in enumerate(num_list): # 인덱스 자동할당 (tuple 형태)
    print(num)
    

num_list = [0, -11, 31, 22, -44, -55]
for num in enumerate(num_list, start=101): # 인덱스 초기번호 설정 가능
    print(num)
    
    
num_list = [0, -11, 31, 22, -44, -55]
num_list2 = list()

for index, num in enumerate(num_list): # 인덱스 튜플 내 값만 가져오기 가능
    print(num)

https://www.fun-coding.org/python-question3-answer.html

파이썬 기초(문제풀이) 3 학습하기

"파이썬 데이터 구조" 튜플 / 딕셔너리 / 집합

1. 튜플 ( ) <- 소괄호를 사용

한번 선언하면 바꿀 수 없는 데이터구조

tupleData = ("a","b","c","d","e")
print(tupleData)

tupleData[0] = "A" # 여기서 에러가 남
print(tupleData)

튜플의 값을 바꿔야 한다면?  일단 다른 데이터구조(리스트)로 전환한 후, 값을 변경한다. 그리고 다시 튜플로 전환한다.

tupleData = ('a','b','c')
print(tupleData) # ('a', 'b', 'c')
print(type(tupleData)) # type(listData)

listData = list(tupleData)
print(type(listData)) # type(listData)

listData[0] = 'A'
tupleData = tuple(listData)
print(tupleData) # ('A', 'b', 'c')
print(type(tupleData)) # <class 'tuple'>

2. 딕셔너리 { } <- 괄호를 사용

딕셔너리 key-value 쌍으로 이루어져 있다.

dictData = {1:'a',2:'b',3:'c'}

keys()로 key값 접근 가능

values()로 value값 접근 가능

keys = [data for data in dictData.keys()] # list comprehension
values = [data for data in dictData.values()] # list comprehension

딕셔너리는 key 값으로 value에 접근 가능.

3. 집합

중복되는 값이 없는 데이터 구조

add(), update(), remove(), discard(), pop(), clear(), in, len() 함수 사용 가능

s1 = set({1, 2, 3})
s2 = set([1, 2, 3])
s3 = {1, 2, 3}

https://www.fun-coding.org/python-question4-answer.html