pjaehyun의 개발일지

해시 구조

• Hash Table: 키(Key) 값(Value)구조로 저장하는 데이터구조
• Key를 통해 데이터를 받아올 수 있으므로, 속도가 빨라진다.
• 파이썬 딕셔너리(Dictionary)타입이 해시 테이블의 예
• 보통 배열로 미리 해시 테이블 사이즈만큼 생성 후에 사용한다.
• 파이썬에서는 해시를 별도 구현할 이유가 없다.(딕셔너리타입이 존재)

시간 복잡도

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

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

용어

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

해시 테이블의 장단점과 용도

해시 테이블의 장점

• 데이터 저장/읽기 속도가 빠르다.(검색 속도가 빠름)
• 해시는 키에 대한 데이터가 있는지(중복) 확인이 쉽다.

해시 테이블의 단점

• 일반적으로 저장공간이 좀 더 많이 필요하다.
• 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.

용도

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• Cache 구현(중복 확인이 쉽기 때문이다.)

리스트 변수를 이용하여 해시 테이블 구현

hash_table = list([0 for i in range(10)]) # 0부터 9까지의 리스트를 0으로 초기화

# Key를 생성하는 함수
def get_key(data):
    return hash(data)

# Key를 이용하여 Hash address를 생성하는 함수
def hash_function(key):
    return key % 10

# data, value를 해시 테이블에 저장하는 함수
def save_data(data, value):
    hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value

# 데이터값으로 Value값을 가져오는 함수
def read_data(data):
    hash_address = hash_function(get_key(data))
    return hash_table[hash_address]

실행 결과

Load Packages

import numpy as np
from PIL import Image
import matplotlib.pyplot as plt
%matplotlib inline

이미지 파일 열기

• opencv로도 열 수 있지만 shape의 순서가 바뀔 때도 있어 PIL로 여는 것을 선호

path = 'images/dog.jpeg'

image_pil = Image.open(path)
image = np.array(image_pil)
image.shape # (334, 500, 3)

테스트용으로 images폴더 안에 dog.jpeg파일을 넣어두었다.

Pillow 라이브러리를 이용하여 해당 경로에있는 사진을 불러오고 시각화를위해 np.array화 시켜준다.

image.shape은 이미지마다 크기가 달르니 지금은 크게 신경쓰지않아도된다.

가장 뒤에있는 3이라는 숫자는 해당 이미지가 컬러이미지라는것을 뜻함 gray sacle의 이미지는 1로 나온다.

Matplotlib 사용

이미지 나타내기

이미지 흑백으로 변경

path = 'images/dog.jpeg'

image_pil = Image.open(path).conver('L')
image_bw = np.array(image_pil)
image_bw.shape # (334, 500)

아까는 shape의 가장뒤에 3이 있었지만 convert('L')을 통해 뒤에 shape의 3이 사라진다.

이미지 색상 변경 cmap이용

다른 이미지와 합치기

# 두번째 이미지를 불러옴
cat_path = 'images/cat.jpeg'
cat_pil = Image.open(cat_path)
cat_image = np.array(cat_pil)
cat_image.shape # (334, 500, 3)

# 만약 두 사진의 크기가 다르다면 같게 설정해준다.
import cv2
dog_image = cv2.resize(image, (500, 334)) #shape을 반대로 넣어야하니 주의
dog_image.shape # (334, 500)

설정이 끝나면 이미지를 불러올 수 있다. 

alpha(투명도)를 넣어주지않으면 cat_image가 dog_image를 덮어 cat_image만 나오게된다.

Load Packages

import numpy as np
import matplotlib.pyplot as plt

@matplotlib inline # jupyter notebook에서 실행한 결과물을 브라우저에서 바로 볼 수 있게해준다.

Matplotlib 사용

Basic Attributes

• alpha : 투명도
• kind : 그래프 종류 'line', 'bar', 'barh', 'kde'
• logy : Y축에 대해 Log scaling
• use_index : 객체의 색인을 눈금 이름으로 사용할지 여부
• rot : 눈금 이름 돌리기 (rotating) 0 ~ 360
• xticks, yticks : x, y축으로 사용할 값
• xlim, ylim : X, Y축의 한계
• grid : 축의 그리드를 표현할지 여부
• subplots : 각 column에 독립된 subplot 그리기
• sharex, sharey : subplots=True 이면 같은 X,Y축을 공유하고 눈금과 한계를 연결
• figsize : 생성될 그래프의 크기를 tuple로 지정
• title : 그래프의 제목 지정
• legend : subplot의 범례 지정
• sort_columns : column을 알파벳 순서로 그린다

선 그래프 그리기

그래프를 만들기위해 랜덤값을 가진 배열을 생성해주고 plt.plot()을 이용하여 만들어진 data를 대입시켜준다.

그렇게되면 x축은 data의 갯수 y축은 데이터의 값으로 이루어진 그래프가 나온다.

그래프 여러개 그리기

• plt.subplot()의 파라미터는 행, 열, 순서를 넣어주면된다. ex) plt.subplot(2,2,1) 2행2열의 첫번째자리

그래프 선 옵션

• 그래프를 그릴 때 표시되는 색이나 마커 패턴을 바꾼다.
- 색상:b(파란색), g(초록색), r(빨간색), c(청록색), y(노란색), k(검은색), w(흰색) - 마커: o(원), v(역삼각형), ^(삼각형), s(네모), +(플러스), .(점)

그래프 사이즈 조절

• plt.figure안에 figsize를 이용하여 가로, 세로 길이 조절 가능(inch 단위)

• 여러개 그래프 사이즈 조절

그래프 겹치기

그래프 Label, Legend 달기

• Legend를 달기 위해서는 plot에 label을 넣어주어야 한다.
• plt.title(): 그래프의 이름
• plt.xlabel(): x축의 이름
• plt.ylabel(): y축의 이름

이중 연결 리스트의 구조

● 미리 모든 노드가 이전 노드와 다음 노드에 대한 정보를 모두 저장하고 있는 리스트이다.

● 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능하다.

Node 클래스 구현

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

기본적인 연결리스트의 객체선언부이고 Node의 data는 실제 우리가 담고자하는 데이터를 할당하게되고 next는 다음 노드의 주소값을 prev는 이전 노드의 주소값을 가진다.

Node Management 클래스 구현

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

단순 연결 리스트와 비슷하지만 이중 연결리스트는 양방향으로 검색이 가능하기 때문에 tail을 선언하여 가장 뒤에있는 노드의 정보를 저장한다.

Insert 함수 구현

# 차례대로 데이터를 삽입
def insert(self, data):
    if self.head == None:
        self.head = Node(data)
        self.tail = self.head
    else:
        node = self.head
        while node.next:
            node = node.next
        new = Node(data)
        node.next = new
        new.prev = node
        self.tail = new

순차적으로 데이터를 집어넣은 경우에는 새로운 노드가 삽입될 때 기존에 있는 노드의 next는 새로운 노드의 주소값을 가리켜야 되고 새로운 노드의 prev는 기존 노드의 주소값을 가져야 한다.

여기서 새로운 노드는 항상 마지막에 존재하기 때문에 tail에 새로운 노드를 넣어준다.

Insert_before 함수 구현

# 특정 데이터앞에 데이터를 삽입
def insert_before(self,data, before_data):
    if self.head == None:
        self.head = Node(data)
        return True
    else:
        node = self.tail
        while node.data != before_data:
            node = node.prev
            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
        return True
            
# 특정 데이터뒤에 데이터를 삽입
def insert_after(self, data, after_data):
    if self.head == None:
        self.head = Node(data)
        return True
    else:
        node = self.head
        while node.data != after_data:
            node = node.next
            if node == None:
                return False
        new = Node(data)
        after_new = node.next
        after_new.prev = new
        new.next = after_new
            new.prev = node
            node.next = new
            return True      

Insert_before와 Insert_after는 특정 노드 앞에 데이터를 삽입하냐 아니면 특정 노드 뒤에 데이터를 삽입하냐의 차이라 코드상 큰 차이는 없다.

새로운 노드가 삽입되면 삽입되는 노드 기준으로 앞에 노드의 next 뒤에 노드의 prev가 새로운 노드를 가리켜야하고 새로운 노드의 prev와 next도 마찬가지로 해당되는 노드들을 가리켜야한다.

Delete 함수 구현

def delete(self, data):
    node = self.head
    while node.data != data:
        node = node.next
    node.prev.next = node.next
    node.next.prev = node.prev
    return True

반복문을 이용해서 삭제하고 싶은 데이터를 찾아 반복문을 탈출하면 삭제하고싶은 노드의 prev와 next를 서로 연결시켜준다.

Search 함수 구현

def search_from_head(self, data):
    if self.head == None:
        return False
    
    node = self.head
    while node:
        if node.data == data:
            return node
        else:
            node = node.next
    return False

def search_from_tail(self, data):
    if self.head == None:
        return False
    
    node = self.tail
    while node:
        if node.data == data:
            return node
        else:
            node = node.prev
    return False

이중 연결 리스트에서는 head(처음)부터 검색을 할 수 도있고 tail(끝)부터 검색이 가능하다.

Print 함수 구현

def desc(self):
    node = self.head
    while node:
        print(node.data)
        node = node.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)
        self.tail = self.head
    
    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new
            
    def insert_before(self,data, before_data):
        if self.head == None:
            self.head = Node(data)
            return True
        else:
            node = self.tail
            while node.data != before_data:
                node = node.prev
                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
            return True
        
    def insert_after(self, data, after_data):
        if self.head == None:
            self.head = Node(data)
            return True
        else:
            node = self.head
            while node.data != after_data:
                node = node.next
                if node == None:
                    return False
            new = Node(data)
            after_new = node.next
            after_new.prev = new
            new.next = after_new
            new.prev = node
            node.next = new
            return True      
            
    def delete(self, data):
        node = self.head
        while node.data != data:
            node = node.next
        node.prev.next = node.next
        node.next.prev = node.prev
        return True
        
    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

    def search_from_head(self, data):
        if self.head == None:
            return False
        
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next
        return False
    
    def search_from_tail(self, data):
        if self.head == None:
            return False
        
        node = self.tail
        while node:
            if node.data == data:
                return node
            else:
                node = node.prev
        return False

링크드 리스트란?

● 자료들을 연속적으로 나열하지않고 임의의 기억공간에 존재하는 데이터를 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.

링크드 리스트 구조

● 링크드 리스트는 연결 리스트라고도 한다.

● 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조

● 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터구조

● 링크드 리스트 기본 구조와 용어

  - 노드(Node): 데이터 저장 단위(데이터값, 포인터)로 구성되어있다.

  - 포인터(Pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간이다.

● 링크드 리스트의 형태

링크드 리스트의 장단점

링크드 리스트 장점

● 미리 데이터 공간은 할당하지 않아도 된다.

  - 배열은 미리 데이터 공간을 할당 해야한다.

링크드 리스트 단점

● 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음

● 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.

● 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요하다.

Node 클래스 구현

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

기본적인 연결리스트의 객체선언부이고 Node의 data는 실제 우리가 담고자하는 데이터를 할당하게되고 next는 다음 노드의 주소값을 가진다.

Node Management 클래스 구현

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

최초로 링크드리스트가 선언되면 링크드리스트의 정보를 가지는 Management를 만들어준다. 이후 삽입 삭제 검색 출력 함수등이 Management클래스에 속하게된다.

데이터 추가(add) 함수 구현

def add(self, data):
        if self.head == None:	# head에 데이터가 존재하지 않으면 바로 추가해주는 예외처리
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)

기본적으로 add함수는 연속적으로 데이터를 저장하기 때문에 while문을 이용하여 node의 가장 마지막 위치를 찾는다.

node.next가 존재하지 않으면 반복문을 빠져나온다. 반복문을 빠져나옴과 동시에 node.next에 새로 생성되는 Node의 주소값을 넣어줌으로 기존 링크드리스트와 연결시켜준다.

Insert 함수 구현

def insert(self, data, is_data):
        if self.head == None:
            self.head = Node(data)
            return True
        else:
            node = self.head
            while node.data != is_data:
                node = node.next
                if node == None:
                    return False
            new = Node(data)
            new.next = node.next
            node.next = new
            return True

Insert함수는 기본적으로 search의 기능을 가지고있다. 데이터를 중간에 삽입하기위해선 앞이든 뒤든 데이터를 알고있어야 삽입이 가능하기 때문에 반복문을 이용하여 입력받은 is_data가 링크드리스트내에 존재하는지 확인을 하고 존재 한다면 반복문을 빠져나와 데이터를 삽입하게 된다.

그림과 같이 데이터를 삽입하게 되면 기존 노드는 새로운노드의 주소값을 가져야하고 새로운노드는 기존 node가 가지고있던 주소값을 가져야 한다.

Delete 함수 구현

def delete(self, data):
        if self.head == None:
            print('노드가 없습니다.')

        if self.head.data == data:
            temp = self.head
            self.head = self.head.next
            del temp
        else:
            node = self.node
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                else:
                    node = node.next

삭제할 데이터를 찾으면 빈 공간에 찾은 데이터를 넣어준다.

node.next에 node.next.next의 주소값을 담아주고 node.next가 담겨있던 temp를 지워줌으로 데이터를 삭제한다.

Search 함수 구현

def search(self, data):
        if self.head == '':
            print('노드가 없습니다.')
        if self.head.data == data:
            return self.head.data
        else:
            node = self.head
            while node.next:
                if node.next.data == data:
                    return node.next.data
                else:
                    node = node.next

링크드 리스트의 head가 검색데이터라면 head를 리턴해주고 검색함수를 끝내고 head가 아니라면

반복문을 이용하여 순차적으로 현재 노드의 데이터와 검색할 데이터가 일치하는지 찾아서 결과를 리턴해준다.

Print 함수 구현

def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

반복문을 이용하여 링크드 리스트의 헤드부터 순차적으로 데이터를 출력해준다.

전체 코드

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
        
class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        
    def add(self, data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
            
    def insert(self, data, is_data):
        if self.head == None:
            self.head = Node(data)
            return True
        else:
            node = self.head
            while node.data != is_data:
                node = node.next
                if node == None:
                    return False
            new = Node(data)
            new.next = node.next
            node.next = new
            return True
            
    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next
            
    def delete(self, data):
        if self.head == '':
            print('노드가 없습니다.')

        if self.head.data == data:
            temp = self.head
            self.head = self.head.next
            del temp
        else:
            node = self.node
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                else:
                    node = node.next
    
    def search(self, data):
        search_count = 0
        if self.head == '':
            print('노드가 없습니다.')
        
        if self.head.data == data:
            return self.head.data
        else:
            node = self.head
            while node.next:
                if node.next.data == data:
                    return node.next.data, search_count
                else:
                    node = node.next
                    search_count += 1

Math Function

● NumPy에도 파이썬처럼 다양한 수학적 연산 기능이 있다.

● 브로드캐스팅을 이용한 연산을 활용하여도 NumPy Math Function을 사용한 결과와 동일하게 나온다. 

import numpy as np

arr = np.arange(9).reshape(3, 3)
arr # array([[0,1,2], [3,4,5], [6,7,8]])

arr2 = np.ones([3,3])*2
arr2 # array([[2., 2., 2.], [2., 2., 2.], [2., 2., 2.]])

더하기 add()

arr + 10
np.add(arr, 10)
# array([[10,11,12],
#       [13,14,15],
#       [16,17,18]])

arr + arr2
np.add(arr, arr2)
# array([[ 2.,  3.,  4.],
#        [ 5.,  6.,  7.],
#        [ 8.,  9., 10.]])

빼기 substract()

arr - 5
np.subtract(arr, 5)
# array([[-5,-4,-3],
#       [-2, -1, 0],
#       [1, 2, 3]])

arr - arr2
np.subtract(arr, arr2)
# array([[-2., -1.,  0.],
#        [ 1.,  2.,  3.],
#        [ 4.,  5.,  6.]])

곱하기 multiply()

arr * 3
np.multiply(arr, 3)
# array([[0,3,6],
#       [9,12,15],
#       [18,21,24]])

arr * arr2
np.multiply(arr, arr2)
# array([[ 0.,  2.,  4.],
#        [ 6.,  8., 10.],
#        [12., 14., 16.]])

나누기 divide()

arr / 2
np.divide(arr, 2)
# array([[0., 0.5, 1.]
#       [1.5, 2., 2.5]
#       [3., 3.5, 4.]])

arr / arr2
np.divide(arr, arr2)
# array([[0. , 0.5, 1. ],
#        [1.5, 2. , 2.5],
#        [3. , 3.5, 4. ]])

배열의 합 sum()

np.sum(arr) # 36
np.sum(arr, arr2) # 54.0

배열 원소들 중 최대 값 max(), argmax()

np.max(arr) # 8
np.argmax(arr) # 8(여기서 8은 최대 값이 위치한 인덱스를 의미)

배열 원소들 중 최소 값 min(), argmin()

np.min(arr) # 0
np.argmax(arr) # 0(여기서 0은 최소 값이 위치한 인덱스를 의미)

배열의 평균 값 mean()

np.mean(arr) # 4

중복을 제외한 원소 unique()

arr = np.array([1,3,5,3,6,5,1,7,8])
np.unique(arr) # array([1,3,5,6,7,8)]

이외에도 수 많은 연산함수가 있고 궁금한 연산함수가 있다면 numpy.org/doc/stable/reference/routines.math.html를 참고

Broadcast

● 연산 모양이 다른 배열들 간의 연산이 특정 조건을 만족했을 때 연산이 가능하도록 배열을 자동적으로 변환한다.

  - 차원의 크기가 1일 때 가능하다.

  - 값이 하나인 배열은 어떤 배열에나 연산이 가능하다.

  - 차원의 짝이 맞을 때 가능하다.

투명하게 보이는 박스들은 브로드캐스트된 값을 나타낸다. 

Broadcast 예제

import numpy as np

arr = np.arange(9).reshape(3,3)
arr # array([[0,1,2], [3,4,5], [6,7,8]])

# 더하기 연산
arr + 3 # array([[3,4,5], [6,7,8], [9,10,11]])

# 빼기 연산
arr - 2 # array([[-2,-1,0], [1,2,3], [4,5,6]])

# 곱하기 연산
arr * 3 # array([[0,3,6], [9,12,15], [18,21,24]])

# 나누기 연산
arr / 2 # array([[0., 0.5, 1.], [1.5, 2., 2.5], [3., 3.5, 4.]])

# 배열끼리 연산
arr + np.array([1,2,3]) # array([[1,3,5], [4,6,8], [7,9,11]])

Indexing

● 기존 파이썬의 배열인덱싱과 비슷하다.

arr = np.array([[1,2,3], [4,5,6], [7,8,9]])
arr[:2] # array([[1,2,3], [4,5,6]])
arr[1][1] # 5
arr[2][1] # 8

Slicing

● 기존 파이썬의 배열슬라이싱과 비슷하다.

arr = np.array([[1,2,3], [4,5,6], [7,8,9]])
arr[1:] # array([[4,5,6], [7,8,9]])
arr[1:, 1:] # array([[5,6], [8,9]])

Boolean Indexing

arr = np.array([[-1.,-2.,1.], [1.1, 0.1, 0.2], [0., 0.2, -0.1]])

arr < = 0  # 0보다 작다면 True, 크다면 False
# array([[ True,  True, False],
#       [False, False, False],
#       [ True, False,  True]])

arr[arr <= 0] = 1
# array([[1. , 1. , 1. ],
#       [1.1, 0.1, 0.2],
#       [1. , 0.2, 1. ]])