1. 해쉬 테이블이란?


- 키(Key)에 데이터(Value)를 저장하는 데이터 구조이다.

- Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 매우 빨라진다.

- 파이썬에서는 해쉬를 별도 구현할 이유가 없다. - 딕셔너리 타입을 사용하면 된다.


- 해쉬는 임의값을 고정길이로 변환하는 것이다.

- 해쉬 테이블은 해쉬값 또는 해쉬주소와 슬롯을 갖고 있는 데이터 구조이다.

- 해싱 함수는 key값을 넣으면 해쉬주소가 나오는 함수다.



2. 해쉬테이블 체이닝 기법( Chaining )


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
# 체이닝 기법
 
hash_table = list([0 for i in range(10)])
 
def get_key(data):
    return hash(data)
 
def hash_func(key):
    return key % 8
 
def csave_data(data, value):
    index_key = get_key(data)
    hash_address = hash_func(index_key)
    
    if hash_table[hash_address] != 0:
        for i in range(len(hash_table[hash_address])):
            if hash_table[hash_address][i][0] == index_key:
                hash_table[hash_address][i][1] = value
                return
        hash_table[hash_address].append([index_key, value])
    else:
        hash_table[hash_address] = [[index_key, value]]
 
def cread_data(data):
    index_key = get_key(data)
    hash_address = hash_func(index_key)
    
    if hash_table[hash_address] != 0:
        for i in range(len(hash_table)):
            if hash_table[hash_address][i][0] == index_key:
                return hash_table[hash_address][i][1]
    else:
        None
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
csave_data('ab','123')
csave_data('ad','456')
hash_table
 
'''
output
[
    [
        [-8164117310928844936, '123'], 
        [6320205215618637368, '456']
    ],
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    0
]
'''
cs


체이닝 기법은 해쉬 테이블 저장공간 외의 공간을 활용하는 기법이다.


충돌이 일어나면 링크드 리스트라는 자료 구조를 사용해서

링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법이다.



3. 해쉬테이블 리니어 기법( Linear )


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
# 리니어 기법
 
hash_table = list([0 for i in range(10)])
 
def get_key(data):
    return hash(data)
 
def hash_func(key):
    return key % 8
 
def lsave_data(data, value):
    index_key = get_key(data)
    hash_address = hash_func(index_key)
    
    if hash_table[hash_address] != 0:
        for i in range(hash_address, len(hash_table)):
            if hash_table[i] == 0:
                hash_table[i] = [index_key, value]
                return
            elif hash_table[i][0] == index_key:
                hash_table[i][1] = value
                return
            
    else:
        hash_table[hash_address] = [index_key, value]
 
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
lsave_data('ab','123')
lsave_data('ad','456')
hash_table
 
'''
output
[
     [-8164117310928844936, '123'],
     [6320205215618637368, '456'],
     0,
     0,
     0,
     0,
     0,
     0,
     0,
     0
]
'''
cs


리니어 기법은 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법이다.

저장공간 활용도를 높이기 위한 기법이다.

저작자표시

'전체 > 자료구조' 카테고리의 다른 글

파이썬 시간복잡도 이해하기  (0) 2020.06.08
파이썬으로 큐 구현하기  (0) 2020.06.08
파이썬으로 스택 구현하기  (0) 2020.06.08


알고리즘 시간복잡도가 필요한 이유는

하나의 문제를 푸는데 알고리즘이 다양할 수 있다.

복잡도를 통해 효율적인 알고리즘을 구현할 수 있다.


- 시간복잡도 : 알고리즘 실행속도를 말한다.

- 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈를 말한다.


- 시간복잡도는 반복문이 여러개 생길경우 많이 발생한다.


시간복잡도는 빅오 표기법을 사용한다.


O(1) < O( 𝑙𝑜𝑔𝑛 ) < O(n) < O(n 𝑙𝑜𝑔𝑛 ) < O( 𝑛2 ) < O( 2𝑛 ) < O(n!)



1. O(n)의 시간복잡도를 가지는 1부터 n까지의 합을 구하는 알고리즘


1
2
3
4
5
6
7
8
9
10
11
12
# 1부터 n까지의 합을 구하는 알고리즘1
 
def sum_all(n):
    total = 0
    for num in range(1, n + 1):
        total += num
    return total
 
print(sum_all(100)) # 5050 
 
# 시간복잡도  O(n)
# 입력 n에 따라 덧셈을 n 번 해야 함
cs



2. O(1)의 시간복잡도를 가지는 1부터 n까지의 합을 구하는 알고리즘


1
2
3
4
5
6
7
8
9
# 1부터 n까지의 합을 구하는 알고리즘 2
 
def sum_all(n):
    return int(n * (n + 1) / 2)
 
print(sum_all(100)) # 5050
 
# 시간복잡도  O(1)
# 반복문이 없으므로 입력이 n이어도 O(1)
cs



같은 결과를 내는 메소드라도 시간복잡도가 적은 O(1)이 효율적인 알고리즘이라고 할 수 있다.

 

저작자표시

'전체 > 자료구조' 카테고리의 다른 글

파이썬으로 해쉬테이블 구현하기  (0) 2020.06.08
파이썬으로 큐 구현하기  (0) 2020.06.08
파이썬으로 스택 구현하기  (0) 2020.06.08


큐는 줄을 서는 행위와 유사하다.

가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조이다.


매표소에서 티켓을 구매할때 가장 먼저 줄을 선 사람이  먼저 티켓을 살수 있는 것이다.

FIFO (First In First Out) 정책을 사용한다.




1. 내장함수 큐를 사용하여 구현하기



1
2
3
4
5
6
7
8
9
10
11
12
# 내장 함수 queue를 사용하여 구현
import queue
 
q = queue.Queue()
 
q.put("a")
q.put("b")
q.put("c")
 
q.qsize()    # 3
q.get()      # 'a'
q.qsize()    # 2
cs



맨 처음에 들어간 데이터가 먼저 나온다.





2. LifoQueue()로 큐 만들기



1
2
3
4
5
6
7
8
9
10
11
# 내장 함수 queue를 사용하여 
# Last in First Out Queue 구현하기
 
import queue
 
q= queue.LifoQueue()
q.put("a")
q.put("b")
 
q.qsize()   #  2
q.get()     # 'b'
cs


마지막에 넣은 데이터가 가장 먼저 나온다.




3. PriorityQueue()로 큐 만들기



1
2
3
4
5
6
7
8
9
# 우선순위가 높은 큐가 먼저 나온다.
import queue
 
q = queue.PriorityQueue()
q.put((10, "a"))
q.put((5, "b"))
q.put((15, "c"))
q.qsize()    # 3
q.get()      # (5, 'b')
cs



우선순위가 높은 큐가 먼저 나온다.




4. enqueue, dequeue 구현하기



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 내장함수 사용하지 않고 
# enqueue, dequeue 구현하기
 
q_list = list()
 
def enqueue(data):
    q_list.append(data)
 
def dequeue():
    data = q_list[0]
    del q_list[0]
    return data
 
for i in range(10):
    enqueue(i)
 
print(q_list)     # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
dequeue()         # 0
print(q_list)     # [1, 2, 3, 4, 5, 6, 7, 8, 9]
enqueue(11)       # 11
print(q_list)     # [1, 2, 3, 4, 5, 6, 7, 8, 9, 11]
cs


저작자표시

'전체 > 자료구조' 카테고리의 다른 글

파이썬으로 해쉬테이블 구현하기  (0) 2020.06.08
파이썬 시간복잡도 이해하기  (0) 2020.06.08
파이썬으로 스택 구현하기  (0) 2020.06.08


스택은 배열을 활용해 

배열의 맨 뒤에 있는 데이터를 빼고 맨뒤에 데이터를 추가하면 되는 간단한 개념이다. 

LIFO 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책을 사용한다.


1.  내장 pop 함수 사용하기


1
2
3
4
5
6
7
8
# 스택 push pop 구현하기1
stack = list()
stack.append(1)
stack.append(2)
 
print(stack) # [1, 2]
stack.pop()  # 2
print(stack) # [1]
cs



2.  push와 pop 메소드 구현하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 스택 push pop 구현하기2
 
stack_list = list()
 
def push(data):
    stack_list.append(data)
 
def pop():
    data = stack_list[-1]
    del stack_list[-1]
    return data 
 
for index in range(10):
    push(index)
 
print(stack_list) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
pop()             # 9
print(stack_list) # [0, 1, 2, 3, 4, 5, 6, 7, 8]
cs


저작자표시

'전체 > 자료구조' 카테고리의 다른 글

파이썬으로 해쉬테이블 구현하기  (0) 2020.06.08
파이썬 시간복잡도 이해하기  (0) 2020.06.08
파이썬으로 큐 구현하기  (0) 2020.06.08

+ Recent posts

티스토리툴바