참고자료

Grokking Algorithms
소프트웨어 속 알고리즘 #3 슬라이드
쥬피터 노트북 파일

동적 프로그래밍 (dynamic programming)

최장 공통 부분 문자열 (LCS, Longest common substring)

Longest common substring

문자열간의 가장 긴 공통 영역을 찾는다.
HISH 와 FISH 공통 부분은 ISH 다.
결과는 3이다.

  • 코드
if word_a[i] == word_b[j]:
    cell[i][j] = cell[i-1][j-1] + 1
else:
    cell[i][j] = 0

최장 공통 부분열 (Longest common subsequence)

longest common subsequence

longest common subsequence

문자열간의 공통된 모든 영역을 찾아 계산한다.
FSH를 찾아 결과를 증가시킨다.

  • 코드
if word_a[i] == word_b[j]:
    cell[i][j] = cell[i-1][j-1] + 1
else:
    cell[i][j] = max(cell[i-1][j], cell[i][j-1])

KNN 알고리즘 (k-nearest neighbors algorithm)

피타고라스 정리 거리구하기 공식

거리구하기

$\sqrt{(X_{1}-X_{2})^2+(Y_{1}-Y_{2})^2}$

  • 2차원 거리 구하기

$\sqrt{(2-2)^2+(2-1)^2}$

= $\sqrt{0+1}$

= $\sqrt{1}$

= $1$

  • 다차원 거리 구하기

다차원의 경우에도 거리를 구하는 것이 가능하다.

$\sqrt{(a_{1}-a_{2})^2+(b_{1}-b_{2})^2+(c_{1}-c_{2})^2+(d_{1}-d_{2})^2+(e_{1}-e_{2})^2}$

$\sqrt{(3-4)^2+(4-3)^2+(4-5)^2+(1-1)^2+(4-5)^2}$

= $\sqrt{1+1+1+0+1}$

= $\sqrt{4}$

= 2

  • KNN 구현

심플하게 구현한 div3125/k-nearest-neighbors 코드입니다.

Where to go next

이진트리

출처 : https://gist.github.com/samidhtalsania/6659380

class Node():

    def __init__(self,key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None


class Tree():

    def __init__(self):
        self.root = None

    def add_node(self, key, node=None):

        if node is None:
            node = self.root

        if self.root is None:
            self.root = Node(key)

        else:
            if key <= node.key :
                if node.left is None:
                    node.left = Node(key)
                    node.left.parent = node
                    print("left")
                    return 
                else:
                    # return self.add_node(key,node = self.root.left)
                    return self.add_node(key, node = node.left)
            else:
                if node.right is None:
                    node.right = Node(key)
                    node.right.parent = node
                    print("right")
                    return 
                else:
                    # return self.add_node(key,node = self.root.right)
                    return self.add_node(key, node = node.right)


    def search(self,key,node = None):

        if node is None:
            node = self.root

        if self.root.key == key:
            print ("key is at the root")
            return self.root

        else:
            if node.key == key :
                print ("key exists")
                return node

            elif key < node.key and node.left is not None:
                print ("left")
                return self.search(key, node = node.left)

            elif key > node.key and node.right is not None:
                print ("right")
                return self.search(key, node = node.right)

            else:
                print ("key does not exist")
                return None

    def delete_node(self,key,node=None):
        #search for the node to be deleted in tree
        if node is None:
            node = self.search(key)#return the node to be deleted

        #root has no parent node
        if self.root.key == node.key: #if it is root
            parent_node = self.root
        else:
            parent_node = node.parent


        '''case 1: The node has no chidren'''
        if node.left is None and node.right is None:
            if key <= parent_node.key:
                parent_node.left = None
            else:
                parent_node.right = None
            return

        '''case 2: The node has children'''
        ''' if it has a single left node'''
        if node.left is not None and node.right is None :
            if node.left.key < parent_node.key : 
                parent_node.left = node.left
            else:
                parent_node.right = node.left

            return

        '''if it has a single right node'''
        if node.right is not None and node.left is None:
            if node.key <= parent_node.key:
                parent_node.left = node.right
            else:
                parent_node.right = node.right
            return

        '''if it has two children'''
        '''find the node with the minimum value from the right subtree.
           copy its value to thhe node which needs to be removed.
           right subtree now has a duplicate and so remove it.'''
        if node.left is not None and node.right is not None:
            min_value = self.find_minimum(node)
            node.key = min_value.key
            min_value.parent.left = None
            return


    def find_minimum(self, node = None):

        if node is None:
            node = self.root

        '''find mimimum value from the right subtree'''

        '''case when there is only a root node'''
        if node.right is not None:
            node = node.right
        else:
            return node

        if node.left is not None:
            return self.find_minimum(node = node.left)
        else:
            return node

    def tree_data(self,node=None):
        if node is None:
            node = self.root

        stack = []
        while stack or node:
            if node is not None:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                yield node.key
                node = node.right





t=Tree()
t.add_node(10)
t.add_node(13)
t.add_node(14)
t.add_node(8)
t.add_node(9)
t.add_node(7)
t.add_node(11)
right
right
left
right
left
left

퓨리에 변환 (fourier transform)

https://techreviewtips.blogspot.com/2017/11/05-02-fft.html

  • matplotlib 설치
pip install matplotlib
pip3 install matplotlib
  • numpy 설치
pip install install numpy
pip3 install install numpy
# FFT  그래프 그리기 1

import matplotlib.pyplot as plt
import numpy as np
import math

#St=0.0005

#Fs = 1/St                    # Sampling frequency
Fs = 2000                    # Sampling frequency
T = 1/Fs                     # Sample interval time
te= 0.5                     # End of time
t = np.arange(0, te, T)   # Time vector

# Sum of a 50 Hz sinusoid and a 120 Hz sinusoid
noise = np.random.normal(0,0.05,len(t))
x = 0.6*np.cos(2*np.pi*60*t+np.pi/2) + np.cos(2*np.pi*120*t)
y = x # + noise     # Sinusoids plus noise

# if energy was collapsed by forced code like belows...
#BB=range(math.trunc(len(t)/2), len(t))
#y[BB]=0

plt.figure(num=1,dpi=100,facecolor='white')
plt.plot(t,y,'r')
plt.xlim( 0, 0.05)
plt.xlabel('time($sec$)')
plt.ylabel('y')

plt.savefig("./test_figure1.png",dpi=300)


# Calculate FFT ....................
n=len(y)        # Length of signal
NFFT=n      # ?? NFFT=2^nextpow2(length(y))  ??
k=np.arange(NFFT)
f0=k*Fs/NFFT    # double sides frequency range
f0=f0[range(math.trunc(NFFT/2))]        # single sied frequency range

Y=np.fft.fft(y)/NFFT        # fft computing and normaliation
Y=Y[range(math.trunc(NFFT/2))]          # single sied frequency range
amplitude_Hz = 2*abs(Y)
phase_ang = np.angle(Y)*180/np.pi

# figure 1 ..................................
plt.figure(num=2,dpi=100,facecolor='white')
plt.subplots_adjust(hspace = 0.6, wspace = 0.3)
plt.subplot(3,1,1)

plt.plot(t,y,'r')
plt.title('Signal FFT analysis')
plt.xlabel('time($sec$)')
plt.ylabel('y')
#plt.xlim( 0, 0.1)

# Amplitude ....
#plt.figure(num=2,dpi=100,facecolor='white')
plt.subplot(3,1,2)

# Plot single-sided amplitude spectrum.

plt.plot(f0,amplitude_Hz,'r')   #  2* ???
plt.xticks(np.arange(0,500,20))
plt.xlim( 0, 200)
plt.ylim( 0, 1.2)
#plt.title('Single-Sided Amplitude Spectrum of y(t)')
plt.xlabel('frequency($Hz$)')
plt.ylabel('amplitude')
plt.grid()

# Phase ....
#plt.figure(num=2,dpi=100,facecolor='white')
plt.subplot(3,1,3)
plt.plot(f0,phase_ang,'r')   #  2* ???
plt.xlim( 0, 200)
plt.ylim( -180, 180)
#plt.title('Single-Sided Phase Spectrum of y(t)')
plt.xlabel('frequency($Hz$)')
plt.ylabel('phase($deg.$)')
plt.xticks([0, 60, 120, 200])
plt.yticks([-180, -90, 0, 90, 180])
plt.grid()

plt.savefig("./test_figure2.png",dpi=300)
plt.show()

png

png

맵리듀스(mapreduce)

  • map
arr1 = [1, 2, 3, 4, 5]
arr2 = map(lambda x: 2 * x, arr1)
for i in arr2:
    print(i)

2
4
6
8
10
  • reduce
from functools import reduce
arr1 = [1, 2, 3, 4, 5]
sum = reduce(lambda x, y: x+y, arr1)
print(sum)
15
블룸 필터(bloom filter)와 하이퍼로그로그
  • 블룸필터
    https://github.com/jaybaird/python-bloomfilter

  • 하이퍼 로그로그
    https://github.com/svpcom/hyperloglog

SHA 알고리즘

  • 문자열 해싱

https://docs.python.org/3/library/hashlib.html

import hashlib
m = hashlib.sha256()
m.update(b"Nobody inspects")
m.update(b" the spammish repetition")
print(m.digest())
b'\x03\x1e\xdd}Ae\x15\x93\xc5\xfe\\\x00o\xa5u+7\xfd\xdf\xf7\xbcN\x84:\xa6\xaf\x0c\x95\x0fK\x94\x06'

파일 해싱

https://www.pythoncentral.io/hashing-files-with-python/

import hashlib
BLOCKSIZE = 65536
hasher = hashlib.sha1()
with open('3.algorithm.ipynb', 'rb') as afile:
    buf = afile.read(BLOCKSIZE)
    while len(buf) > 0:
        hasher.update(buf)
        buf = afile.read(BLOCKSIZE)
print(hasher.hexdigest())
9e602fda6e7192e1c98d6da0e5e788b85f70d927
  • MySQL Password hashing
    https://dev.mysql.com/doc/refman/5.5/en/password-hashing.html

디피-헬만 알고리즘 (Diffie-Hellman algorithm)

https://sublimerobots.com/2015/01/simple-diffie-hellman-example-python/

# use Python 3 print function
# this allows this code to run on python 2.x and 3.x
from __future__ import print_function
 
# Variables Used
sharedPrime = 23    # p
sharedBase = 5      # g
 
aliceSecret = 6     # a
bobSecret = 15      # b
 
# Begin
print( "Publicly Shared Variables:")
print( "    Publicly Shared Prime: " , sharedPrime )
print( "    Publicly Shared Base:  " , sharedBase )
 
# Alice Sends Bob A = g^a mod p
A = (sharedBase ** aliceSecret) % sharedPrime
print( "\n  Alice Sends Over Public Chanel: " , A )
 
# Bob Sends Alice B = g^b mod p
B = (sharedBase ** bobSecret) % sharedPrime
print( "    Bob Sends Over Public Chanel: ", B )
 
print( "\n------------\n" )
print( "Privately Calculated Shared Secret:" )
# Alice Computes Shared Secret: s = B^a mod p
aliceSharedSecret = (B ** aliceSecret) % sharedPrime
print( "    Alice Shared Secret: ", aliceSharedSecret )
 
# Bob Computes Shared Secret: s = A^b mod p
bobSharedSecret = (A ** bobSecret) % sharedPrime
print( "    Bob Shared Secret: ", bobSharedSecret )
Publicly Shared Variables:
    Publicly Shared Prime:  23
    Publicly Shared Base:   5

  Alice Sends Over Public Chanel:  8
    Bob Sends Over Public Chanel:  19

------------

Privately Calculated Shared Secret:
    Alice Shared Secret:  2
    Bob Shared Secret:  2

선형 프로그래밍

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%98%95_%EA%B3%84%ED%9A%8D%EB%B2%95

LinkedList 구현

https://gist.github.com/ptigas/2820165

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

        
class LinkedList :
    def __init__(self) :
        self.head = None

    def add(self, data) :
        node = Node( data )
        if self.head == None :
            self.head = node
        else :
            node.next = self.head
            node.next.prev = node
            self.head = node

    def search(self, k) :
        p = self.head
        if p != None :
            while p.next != None :
                if (p.data == k) :
                    return p
                p = p.next
            if (p.data == k) :
                return p
        return None

    def remove(self, p) :
        tmp = p.prev
        p.prev.next = p.next
        p.prev = tmp

    def __str__(self) :
        s = ""
        p = self.head
        if p != None :
            while p.next != None :
                s += p.data
                p = p.next
            s += p.data
        return s


# example code
l = LinkedList()

l.add('a')
l.add('b')
l.add('c')

print(l)
l.remove(l.search('b'))
print(l)
cba
ca