AI교육과정 - Python.5

단비·2023년 1월 18일

python

AI교육과정

목록 보기

57/69

스택(stack)
- 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 구조
- LIFO(Last Input First Out)
- 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
1. 스택의 구조
  - 스택은 LIFO(후입 선출) 또는 FILO(선입 후출) 데이터 관리 방식
  - 스택의 활용: 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
  - 기능
    - push(): 데이터를 스택에 쌓기
    - pop(): 데이터를 스택에서 꺼내기
2. 스택의 장단점
  - 구조가 단순해서 이해와 구현이 쉬움
  - 데이터 저장/읽기 속도가 빠름
  - 데이터 최대 개수를 미리 정해야 함(파이썬의 경우 재귀함수는 1000번까지만 호출이 가능)
  - 저장 공간의 낭비가 발생할 수 있음(미리 최대 개수만큼 저장공간을 미리 확보하기 때문)
  ▶︎ 스택은 단순하고 빠른 성능을 위해 사용하므로 보통 배열 구조를 활용하여 구현하는 것이 일반적
```
# 파이썬 리스트 기능에서 제공하는 메소드로 스택 사용하기
data_stack = list() # []

data_stack.append(2) # [2]
data_stack.append(10) # [2,10]
data_stack.append(5) # [2,10,5]
temp = data_stack.pop() # 5
print(data_stack) # [2,10]
```

링크드리스트(Linked List)

떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 구조
데이터의 삽입과 삭제가 매우 빠름
C언어에서는 중요한 자료구조지만, 파이썬에서는 리스트 타입이 링크드 리스트 역할도 모두 지원
링크드 리스트를 구현할 때 클래스를 주로 활용

링크드 리스트의 용어

노드(node): 데이터 저장 단위(데이터, 포인터)로 구성
포인터(pointer): 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
data pointer(next)

data pointer(next)

data pointer(next)

# 링크드 리스트 구현하기
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

node1 = Node(10) # <__main__.Node object at 0x7f91930600d0>
node2 = Node(20) # <__main__.Node object at 0x7f9193060b20>
node1.next = node2 # node1의 포인터 값에 node2 주소값 삽입
head = node1 # <__main__.Node object at 0x7f91930600d0>

링크드 리스트로 데이터 추가하기

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

  def add(self, data):
    node = head # 지역변수 node에 전역변수 head 삽입
    while node.next: # 노드 포인터에 연결된 다음 노드값이 있을 때
      node = node.next # 노드 포인터에 다음 노드값 연결
    node.next = Node(data) # 노드 포인터에 연결된 다음 노드값이 없을 때 노드값 생성

node1 = Node(10) # node 10으로 데이터 생성
head = node1 # head에 node1 담기
for index in range(2,11): # 2부터 10까지
  node1.add(index * 10) # node 생성

링크드 리스트 출력하기

node = head # node에 head 삽입
while node.next: # node.next가 있으면
  print(node.data) # 해당 노드 출력
  node = node.next # 이후 다음 노드를 node에 삽입
print(node.data) # node.next가 없을 경우 해당 node 출력

객체 지향 프로그램으로 링크드리스트 구현

class NodeMgmt:
	  def __init__(self, data):
		    self.head = Node(data)

  def add(self,data):
	    if self.head == None: # 해당 생성자에 첫번째 노드가 없다면(노드가 하나도 없다면)
	      self.head = Node(data) # 첫번째 노드 생성
	    else:
		      node = self.head # 해당 생성자의 첫번째 노드를 node 로 지정
		      while node.next:
			        node = node.next
		      node.next = Node(data) # 맨마지막에 노드 생성
	
  def delete(self, data):
	    if self.head.data == data: # 해당 생성자의 첫번째 노드의 데이터와 지우려는 데이터가 동일하다면
		      temp = self.head # temp에 해당 생성자의 첫번째 노드를 저장
		      self.head = self.head.next # 해당 생성자의 첫번째 노드에 현재 첫번째노드 다음 노드를 저장
		      del temp # 첫번째 노드 삭제
	    else:
		      node = self.head
		      while node.next:
			        if node.next.data == data: # 다음 노드 데이터가 지우려는 데이터와 동일하다면
				          temp = node.next # temp에 다음 노드를 저장
				          node.next = node.next.next # 다음 노드를 다다음 노드로 저장
				          del temp # 이전에 저장한 다음 노드 삭제
				          return
			        else:
				          node = node.next

더블 링크드 리스트(Doubly Linked List)

양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
pointer(prev) data pointer(next)

pointer(prev) data pointer(next)

class Node:
  def __init__(self, data, prev=None, next=None):
	    self.prev = prev
	    self.data = data
	    self.next = next

class NodeMgmt:
  def __init__(self,data): # 노드를 처음 생성할 때
	    self.head = Node(data) # 첫번째 노드이자 (prev)
	    self.tail = self.head # 마지막 노드로 설정(next)
  
  def insert(self,data):
	    if self.head == None: # 생성자의 첫번째 노드가 없다면
		      self.head = Node(data) # 생성한 노드를 첫번째 노드이자 (prev)
		      self.tail = self.head # 마지막 노드로 설정(next)
	    else:
		      node = self.head
		      while node.next:
			        node = node.next
		      new = Node(data) # 새로운 노드를 new에 저장
		      node.next = new # 현재 노드의 다음 노드를 새로운 노드로 지정(양방향)
		      new.prev = node # 새로운 노드의 이전 노드를 현재 노드로 지정(양방향)
		      self.tail = new # 새로운 노드를 현재 생성자의 마지막 노드로 지정
	
  def node_print(self):
	    node = self.head
	    while node :
		      print(node.data)
		      node = node.next

  def insert_before(self, data, after_data):
	    if self.head == None:
		      self.head = Node(data)
		      return True
	    else:
		      node = self.tail # node를 현재 생성자의 마지막 노드로 지정
		      while node.data != after_data: # node의 데이터와 지정한 after데이터와 동일하지 않다면
			        node = node.prev # node를 현재 노드의 이전 노드로 지정
			        if node == None:
				          return False
		      new = Node(data)
		      before_new = node.prev # 현재 노드의 이전노드를 저장
		      before_new.next = new # 현재 노드의 이전 노드 다음에 새로운 노드 저장
		      new.prev = before_new # 새로운 노드 이전 노드에 현재 노드의 이전노드 저장
		      new.next = node # 새로운 노드 다음 노드에 현재 노드 저장
		      node.prev = new # 현재 노드 이전 노드에 새로운 노드 저장
      
  def search_from_head(self,data):
	    if self.head == None:
		      return False
	    node = self.head
	    while node:
		      if node.data == data:
			        return node.data
		      else:
			        node = node.next
	    return False

해쉬 테이블(Hash Table)

키(key)에 데이터(value)를 저장하는 데이터 구조
파이썬에서는 딕셔너리(dick)타입이 해쉬 테이블의 예
key를 통해서 데이터를 바로 찾을 수 있으므로 검색 속도가 빠름
보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용

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

간단한 해쉬 예제

슬롯 만들기

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

해쉬 함수 만들기
- 해쉬 함수는 다양하게 생성할 수 있으며, 가장 간단한 방법으로 division법(나누기를 통한 나머지 값을 사용하는 기법)을 사용해봄
```
def hash_func(key):
  return key % 10
```

해쉬 테이블에 저장하기

데이터에 따라 필요 시 key 생성 방법 정의가 필요함
ord(): 문자의 아스키코드를 반환

def storage_data(data, value):
  key = ord(data[0]) # key에 data 첫글자를 아스키코드로 변환한 값을 넣음
  hash_address = hash_func(key) # key / 10 의 나머지값을 hash_address에 저장
#  hash_table(list)의 hash_address 번째의 값을 value로 지정
  hash_table[hash_address] = value

data1 = 'apple'
data1[0] # a
print(ord(data1[0])) # 97
print(hash_func(ord(data1[0]))) # 7
# hash_table(list)의: a의 아스키코드 / 10의 나머지값이 인덱스값
# 해당 인덱스의 값을 '010-1111-1111'로 지정
storage_data('apple', '010-1111-1111')

해쉬 함수를 사용해서 해싱함수를 수정하기

def get_key(data):
  return hash(data) # data값으로 hash코드 생성

def hash_function(key):
  return key % 10 # 해쉬코드 / 10 후 나머지값 리턴

def save_data(data, value):
  hash_address = hash_function(get_key(data)) # 해쉬코드/10 나머지값
  hash_table[hash_address] = value # hash_table의 인덱스(나머지값)값 수정

def read_data(data):
  hash_address = hash_function(get_key(data)) # 해쉬코드/10 나머지값
  return hash_table[hash_address] # hash_table의 인덱스(나머지값)값 리턴

해쉬 테이블의 장단점
- 장점
  - 데이터 저장 및 읽기 속도가 빠름(검색 속도가 빠름)
  - 해쉬는 키에 대한 데이터가 있는지 확인 쉬움
- 단점
  - 저장공간이 많이 필요함
  - 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요함

충돌(Collision) 해결 알고리즘

Linear Probling 기법

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

def get_key(data):
  return hash(data)

def hash_function(key):
  return key % 8

def save_data(data, value):
  index_key = get_key(data)
  hash_address = hash_function(index_key) # data의 해쉬코드값 / 8 후 나머지값

  if hash_table[hash_address] != 0: # 테이블의 인덱스(나머지값)에 값이 있다면
    for index in range(hash_address, len(hash_table)): # address부터 table 끝까지
      if hash_table[index] == 0: # 해당 인덱스의 값이 없다면
        hash_table[index] = [index_key, value] # 해당 인덱스에 data,value 리스트 저장
        return
      elif hash_table[index][0] == index_key: # 해당 인덱스의 키값이 생성자의 키값과 동일하다면
        hash_table[index][1] = value # 해당 인덱스값에 생성자의 키값 저장
        return
  else:
    hash_table[hash_address] = [index_key, value] # 테이블의 인덱스(나머지값)에 값이 없다면 리스트로 저장

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)): # address부터 table 끝까지
      if hash_table[index] == 0: # 해당 인덱스의 값이 없다면
        return None
      elif hash_table[index][0] == index_key: # 해당 인덱스의 키값이 생성자의 키값과 동일하다면
        return hash_table[index][1] # 해당 인덱스값 리턴
  else: # 해당 생성자의 인덱스에 값이 없을 경우
    return None

Chaining 기법

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

def save_data(data,value):
  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:
        hash_table[hash_address][index][1] = value
        return
    hash_table[hash_address].append([index_key, value])
  else:
    hash_table[hash_address] = [[index_key, value]]

해쉬 함수와 키 생성 함수

SHA(Secure Hash Alogorithm, 안전한 해쉬 알고리즘)와 같은 유명한 해쉬 알고리즘을 많이 사용
어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로 해쉬 함수로 유용하게 활용할 수 있음

SHA-1

임의의 길이의 입력데이터 최대 160비트(16진수 40자리)의 출력데이터(해시값)로 바꿈
파이썬의 hash() 함수는 환경에 따라 값이 매번 달라질 수 있음

import hashlib

data = 'test'.encode() # test 문자열을 바이트 단위로 변환
print(data) # b'test'
hash_object = hashlib.sha1() # <sha1 HASH object @ 0x7f97f2e1b950>
hash_object.update(data) # sha-1 객체로 data를 읽어옴
hex_dig = hash_object.hexdigest() # 16진수로 고정된 해쉬 값을 발생
print(hex_dig) # a94a8fe5ccb19ba61c4c0873d391e987982fbbd3
# 966482230667555116936258103322711973649032657875
print(int(hex_dig, 16)) # 16진수로 고정된 해쉬값을 10진수로 고정된 해쉬값으로 변환

SHA-256

SHA 알고리즘의 한 종류로 256비트로 구성되어 64자리 문자열을 반환
SHA-2 계열 중 하나이며, 블록체인에서 가장 많이 채택하여 사용

import hashlib

data = 'test'.encode() # test 문자열을 바이트 단위로 변환
print(data) # b'test'
hash_object = hashlib.sha256() # <sha256 HASH object @ 0x7f97f2dfd6f0>
hash_object.update(data) # sha-256 객체로 data를 읽어옴
hex_dig = hash_object.hexdigest()
print(hex_dig)
print(int(hex_dig, 16))

단비

tistory로 이전! https://sweet-rain-kim.tistory.com/

이전 포스트

AI교육과정 - Python.4

다음 포스트

AI교육과정 - Python.5

AI교육과정

AI교육과정 - Python.4

AI교육과정 - Python.6

0개의 댓글