import numpy as np
def Fibonacci_1(number):#O(2^n)
    if(number == 0):
        return 0
    elif(number == 1):
        return 1
    return Fibonacci_1(number-1) + Fibonacci_1(number-2)

def Fibonacci_2(M, number):#O(logn)
     if(number > 1):
         if number % 2 ==0:
             M = Fibonacci_2(M, number/2)
             M = np.dot(M,M)
         elif number % 2 ==1:
             M = Fibonacci_2(M,(number-1)/2)
             M = np.dot(M,M)
             M_1 = np.array([[1,1],[1,0]])             
             M = np.dot(M,M_1)
     return M

def Fibonacci_3(number):
    Fibonacci_T = []
    if number ==0 or number == 1:
        return number
    Fibonacci_T.append(0)
    Fibonacci_T.append(1)
    for i in range(2,number+1):
        Fibonacci_T.append(Fibonacci_T[i-1]+Fibonacci_T[i-2])
    result = Fibonacci_T
    return result

if __name__=='__main__':
    M=np.array([[1,1],[1,0]])
    a = (Fibonacci_2(M,10))
    F2 = a[0][1]
    b = Fibonacci_3(10)
    F3 = b[len(b)-1]
    
    
    print("O(2^n)")
    print(Fibonacci_1(10))
    print("O(log n)")
    print(F2)
    print("O(n)")
    print(F3)


저작자표시

'파이썬으로 구현한 알고리즘' 카테고리의 다른 글

Iterative 거듭제곱 구현하기  (0) 2017.12.27
Postfix 구현하기  (0) 2017.11.16
Regular Expression으로 전화번호 Search 구현하기  (0) 2017.11.16
Nested tree를 tree로 만들고 left child right sibling구조로 변환 구현하기  (0) 2017.11.16
Boyer-Moore Algorithm 구현하기  (0) 2017.11.11 
def Power(Base, Exponent):
    result = Base
    count = 1
    ex_Exponent = Exponent
    list1 = []
    while(ex_Exponent > 1):
        if ex_Exponent % 2 == 0:
            list1.append(0)
            ex_Exponent = ex_Exponent/2
        else:
            list1.append(1)
            ex_Exponent = (ex_Exponent - 1)/2
    list1_len = len(list1)
    for count in range(list1_len):
        if list1[list1_len - count -1] == 0:
            result = result * result
        else:
            result = result * result * Base
    return result

if __name__=='__main__':
    print(Power(11,3))


저작자표시

'파이썬으로 구현한 알고리즘' 카테고리의 다른 글

다양한 빅오의 피보나치 구현하기  (0) 2017.12.27
Postfix 구현하기  (0) 2017.11.16
Regular Expression으로 전화번호 Search 구현하기  (0) 2017.11.16
Nested tree를 tree로 만들고 left child right sibling구조로 변환 구현하기  (0) 2017.11.16
Boyer-Moore Algorithm 구현하기  (0) 2017.11.11
import re
# (5.12-2.74+0.24)*(3.15-2.0) + 1.12*4.09 를 postfix로 구현
lis = []
expression = "(5.12-2.74+0.24)*(3.15-2.0) + 1.12*4.09"
expression = re.sub('([\+\-\*\/\(\)])' , ' \g<1> ' , expression)
calc = expression.split()
for k in calc:
    if k == '(':
        lis.append(k)
    elif k == '+' or k == '-':
        if '*'in lis or '/' in lis or '+' in lis or '-' in lis:
            temp = lis.pop()
            if temp == '(' :
                lis.append(temp)
                lis.append(k)
            else:
                lis.append(temp)
                print(lis.pop(), end=" ")
                lis.append(k)
        else:
            lis.append(k)
    elif k == '*' or k == '/':
        if '*'in lis or '/' in lis:
            print(lis.pop(), end=" ")
            lis.append(k)
        else:
            lis.append(k)
    elif k == ')':
        while lis:
            t=lis.pop()
            if t == '(':
                continue
            else:
                print(t, end=" ")
    else:
        print(k, end=" ")
while lis:
    print(lis.pop(), end=" ")
 
print("\n")
 
#(5*(3+4)-5.12/2.33)-1.23*100)를 postfix로 구현
lis = []
expression = "(5*(3+4)-5.12/2.33)-1.23*100)"
expression = re.sub('([\+\-\*\/\(\)])' , ' \g<1> ' , expression)
calc = expression.split()
for k in calc:
    if k == '(':
        lis.append(k)
    elif k == '+' or k == '-':
        if '*'in lis or '/' in lis or '+' in lis or '-' in lis:
            temp = lis.pop()
            if temp == '(' :
                lis.append(temp)
                lis.append(k)
            else:
                lis.append(temp)
                print(lis.pop(), end=" ")
                lis.append(k)
        else:
            lis.append(k)
    elif k == '*' or k == '/':
        if '*'in lis or '/' in lis:
            print(lis.pop(), end=" ")
            lis.append(k)
        else:
            lis.append(k)
    elif k == ')':
        while lis:
            t=lis.pop()
            if t == '(':
                continue
            else:
                print(t, end=" ")
    else:
        print(k, end=" ")
while lis:
    print(lis.pop(), end=" ")
print("\n")
 
#postfix계산기 구현
lis = []
expression = input("계산식을 입력하시오 : ")
expression = re.sub('([\+\-\*\/\(\)])' , ' \g<1> ' , expression)
calc = expression.split()
for k in calc:
    if k == '(':
        lis.append(k)
    elif k == '+' or k == '-':
        if '*'in lis or '/' in lis or '+' in lis or '-' in lis:
            temp = lis.pop()
            if temp == '(' :
                lis.append(temp)
                lis.append(k)
            else:
                lis.append(temp)
                print(lis.pop(), end=" ")
                lis.append(k)
        else:
            lis.append(k)
    elif k == '*' or k == '/':
        if '*'in lis or '/' in lis:
            print(lis.pop(), end=" ")
            lis.append(k)
        else:
            lis.append(k)
    elif k == ')':
        while lis:
            t=lis.pop()
            if t == '(':
                continue
            else:
                print(t, end=" ")
    else:
        print(k, end=" ")
while lis:
    print(lis.pop(), end=" ")
 
    
        
cs


저작자표시

'파이썬으로 구현한 알고리즘' 카테고리의 다른 글

다양한 빅오의 피보나치 구현하기  (0) 2017.12.27
Iterative 거듭제곱 구현하기  (0) 2017.12.27
Regular Expression으로 전화번호 Search 구현하기  (0) 2017.11.16
Nested tree를 tree로 만들고 left child right sibling구조로 변환 구현하기  (0) 2017.11.16
Boyer-Moore Algorithm 구현하기  (0) 2017.11.11
import re #다양한 종류의 전화번호를 파일에서 검색하기
with open('search.txt','rt',encoding='UTF8') as f: #한글이 포함된 파일에서 읽어들이기
    number = []
    for line in f:
        m = re.findall(r'[(]?(\d\d\d?)[)]?[-\s]?(\d\d\d\d?)-(\d\d\d\d)',line)
        if m:
            for i in m:
                number.append(("<TEL>"+i[0]+'-'+i[1]+'-'+i[2]+"<TEL>")) #형식을 <TEL><TEL>로 바꾸기
    print(number)
with open('number_list','w') as z:
    for k in number:
        z.write(k)
        z.write('\n')
cs


저작자표시

'파이썬으로 구현한 알고리즘' 카테고리의 다른 글

Iterative 거듭제곱 구현하기  (0) 2017.12.27
Postfix 구현하기  (0) 2017.11.16
Nested tree를 tree로 만들고 left child right sibling구조로 변환 구현하기  (0) 2017.11.16
Boyer-Moore Algorithm 구현하기  (0) 2017.11.11
KMP Algorithm 구현하기  (0) 2017.11.11
import re
class Node():
    def __init__(self, data=None,left=None,right=None):
        self.data = data
        self.next = list()
        self.left = left
        self.right = right
 
        
    def __str__(self):
        return str(self.data)
    
    def add_child(self, node):
        self.next.append(node)
 
class Tree:
    def __init__(self):
        self.root = Node()
        self.tree = list()
    def Nested_Tree(self,text): #스택을 사용하여 '('와 ')'를 사용해 구현
        stack = list()
        for calc in text:
            if calc == '(':
                stack.append(calc)
            elif calc == ')':
                input_n = stack.pop()
                stack.pop()
                if not stack:
                    self.root = input_n
                    break
                else:
                    k=stack.pop()
                    k.add_child(input_n)
                    #self.tree.append(k)
                    stack.append(k)
            else:
                t= Node(calc)
                stack.append(t)
                self.tree.append(t)
    def PrintLL(self,list):
        for i in range(0,len(list)):
            if not list[i].next:
                continue
            print()
            print(list[i],'--> [', end=" ")
            for j in range(0,len(list[i].next)):
                print("'",list[i].next[j], end="' ")
                if j < len(list[i].next) - 1:
                    print(",",end="")
            print("]")
    def left_right(self,tree):
        for i in range(0,len(tree)):
            if not tree[i].next:
                continue
            else:
                tree[i].left = tree[i].next[0]
                for j in range(0,len(tree[i].next)-1):
                    tree[i].next[j].right = tree[i].next[j+1]
    def left_right_print(self,list):
        for i in range(0,len(list)):
            if not list[i].left:
                continue
            print(list[i],'--> [ child : ',list[i].left,', sibling : ', end ='')
            right = list[i].left.right
            while right:
                print(right,' ', end = '')
                right = right.right
            print('] \n')
        
        
if __name__ == "__main__":
    text = "(A(B(C)(D(E)(F)))(G(H))(I(J(K))))"
    text = re.sub('([\(\)])' , ' \g<1> ' , text)
    calc = text.split()
    k = Tree()
    k.Nested_Tree(calc)
  #  print(k.tree[0] ,'-->',k.tree[0].next[0],k.tree[0].next[1])
    print('\n')
    print("ROOT --> ['",k.root,"']")
    k.PrintLL(k.tree)
    print('\n')
    print('left child right sibling structure \n')
    k.left_right(k.tree)
    k.left_right_print(k.tree)
 
    
 
 
 
 
 
 



저작자표시

'파이썬으로 구현한 알고리즘' 카테고리의 다른 글

Postfix 구현하기  (0) 2017.11.16
Regular Expression으로 전화번호 Search 구현하기  (0) 2017.11.16
Boyer-Moore Algorithm 구현하기  (0) 2017.11.11
KMP Algorithm 구현하기  (0) 2017.11.11
Priority Que 구현하기(우선순위 큐)  (0) 2017.09.25
def BuildGST(pattern, suffix, GST):
    m = len(pattern)
    suffix[m-1] = m
    g = m-1
    
    for i in range(m-2, -1, -1):
        if i > g and suffix[i+m-1-f] < i-g:
            suffix[i] = suffix[i+m-1-f]
        else:
            if i < g:
                g = i
            f = i
            while (g>=0 and pattern[g]==pattern[g+m-1-f]):
                g-=1
            suffix[i] = f-g
            
        for i in range(0,m,1):
            GST[i] = m
            
        j=0
        for i in range(m-1, -1, -1):
            if suffix[i] == i+1:
                while(j < m-1-i):
                    if GST[j] == m:
                        GST[j] = m-1-i
                    j+=1
        for i in range(0,m-1,1):
            GST[m-1-suffix[i]] = m-1-i
            
def BuildBCT(pattern,BCT):
    
    for i in range(10000):
        BCT.append(-1)
    for i in range(len(pattern)):
        BCT[ord(pattern[i])] = i
 
 
def search(pattern,GST,BCT,text):
    index = []
    m = 0
    t_len = len(text)
    p_len = len(pattern)
    i = p_len - 1
    
    while m+i < t_len:
        if pattern[i] == text[m+i]:
            if i == 0:
                index.append(m)
                i = p_len-1
                m += 1
            i -= 1
        else:
            m = m + max(GST[i], i-BCT[ord(pattern[i])])
            i = p_len-1
    return index
if __name__=='__main__':
    pattern = input("Please input the pattern : ")
    print('\n')
    GST = []
    BCT = []
    suffix = []
    leng = len(pattern)
    index_key = 0
    for i in range(len(pattern)):
        GST.append(0)
        BCT.append(0)
        suffix.append(0)
    BuildGST(pattern, suffix, GST)
    BuildBCT(pattern,BCT)
    with open('source.txt') as f:
        line_number = 1       
        for line in f:
            cols = list(line)
            index = search(pattern,GST,BCT,cols)
            if index:
                for index_target in index:
                    index_target = index_target + index_key
                    cols.insert(index_target,'[[')
                    cols.insert(index_target+leng+1,']]')
                    index_key += 2
                index_key = 0
                print(line_number,index,"------")
                for k in cols:
                    print(k,end='')
                print('\n')
            line_number += 1
 
    
              




저작자표시

'파이썬으로 구현한 알고리즘' 카테고리의 다른 글

Regular Expression으로 전화번호 Search 구현하기  (0) 2017.11.16
Nested tree를 tree로 만들고 left child right sibling구조로 변환 구현하기  (0) 2017.11.16
KMP Algorithm 구현하기  (0) 2017.11.11
Priority Que 구현하기(우선순위 큐)  (0) 2017.09.25
Linked list 구현하기  (0) 2017.09.25
def make_kmp_table(pattern,border):
    
    m= len(pattern)
    border[0] = -1
    border[1] = 0
    
    i = 2
    cnd = 0
    
    while(i < m):
        if pattern[i-1] == pattern[cnd]:
            cnd += 1
            border[i] = cnd
            i += 1
            
        elif cnd > 0:
            cnd = border[cnd]
            
        else:
            border[i] = 0
            i += 1
 
def kmp_search(pattern, border, text):
    index = []
    m = 0
    i = 0
    t_len = len(text)
    p_len = len(pattern)
    
    while m+i < t_len:
        if pattern[i] == text[m+i]:
            if i == p_len-1:
                index.append(m)
                i = 0
                m += 1
            i += 1
        else:
            if border[i] > -1:
                m = m + i- border[i]
                i = border[i]
            else:
                i = 0
                m += 1
    return index
 
if __name__=='__main__':
    pattern = input("Please input the pattern : ")
    print('\n')
    border = []
    leng = len(pattern)
    index_key = 0
    for i in range(len(pattern)):
        border.append(0)
    make_kmp_table(pattern,border)
    with open('source.txt') as f:
        line_number = 1       
        for line in f:
            cols = list(line)
            index = kmp_search(pattern,border,cols)
            if index:
                for index_target in index:
                    index_target = index_target + index_key
                    cols.insert(index_target,'[[')
                    cols.insert(index_target+leng+1,']]')
                    index_key += 2
                index_key = 0
                print(line_number,index,"------")
                for k in cols:
                    print(k,end='')
                print('\n')
            line_number += 1

cs


저작자표시

'파이썬으로 구현한 알고리즘' 카테고리의 다른 글

Regular Expression으로 전화번호 Search 구현하기  (0) 2017.11.16
Nested tree를 tree로 만들고 left child right sibling구조로 변환 구현하기  (0) 2017.11.16
Boyer-Moore Algorithm 구현하기  (0) 2017.11.11
Priority Que 구현하기(우선순위 큐)  (0) 2017.09.25
Linked list 구현하기  (0) 2017.09.25

class Node:

    def __init__(self, value = None, next = None):

        self.data = value

        self.next = next

    def __str__(self):

        return str(self.data)

#우선순위 큐

class Priority_que:

    def __init__(self, head = None ):

        self.node = Node(head)

        self.head = self.node

#제일 앞의 큐를 뽑아낸다

    def Dequeue(self):

        self.head = self.head.next

#데이터를 받아서 순위에 따라 배치한다

    def Enqueue(self,data):

        insert_data = Node(data)

        comp = self.head

        pre = Node()

        if insert_data.data < comp.data:

            self.head = insert_data

            insert_data.next = comp

        else:

            while  True:

                if comp.data >= insert_data.data:

                        pre.next = insert_data

                        insert_data.next = comp

                        break

                elif comp.data < insert_data.data:

                    if comp.next == None:

                        comp.next = insert_data

                        break

                    else:

                        pre = comp

                        comp = comp.next

#우선순위 큐를 출력한다

    def PrintLL(self):

        node_print = self.head

        

        while True :

            if node_print.next == None:

                print(node_print.data)

                break

            else:

                print(node_print.data , "->", end=" ")

                node_print = node_print.next

#큐를 만든다

k=Priority_que(5)

#여러 숫자로 큐를 만든다

k.Enqueue(4)

k.Enqueue(7)

k.Enqueue(8)

k.Enqueue(4)

k.Enqueue(7)

k.Enqueue(8)

k.Enqueue(4)

k.Enqueue(7)

k.Enqueue(8)

k.Enqueue(10)

#만든 큐를 출력한다

k.PrintLL()

#큐를 뽑아낸다

k.Dequeue()

k.PrintLL()

k.Dequeue()

k.Dequeue()

k.PrintLL()   


1. class Node:

우선 받은 data 값과 next 값을 초기화 해 줄수있다.



2. Priority_que:

노드를 가리키는 self.node와 제일 처음노드 self.head를 초기값으로 가진다.

2-1 Dequeue

제일 첫 머리의 큐를 밖으로 보내기 때문에 self.head 값을 next값으로 바꾸어 준다.

2-2 Enqueue

먼저 넣으려는 노드를 만들고 그 전의 값을 저장하기위해 노드를 하나더 만든다. 그리고 제일 첫값을 비교값으로 만든다. 우선 if문으로 비교하는 데이터값보다 넣으려는 값이 더 작다면 그 값을 제일 앞에 오게 만들어 준다.

그것이 아니라면 while문 안에서 우선 조건을 모두 만족시키지 않으면 pre값에는 현재 비교값 그리고 비교값에는 다음비교값을 넣어서 한칸 이동시켜준다. 그리고 만약 비교값이 넣어주려는 노드값보다 크면 pre값의 next에 삽입값을 넣어주고 삽입값의 next에 비교값을 넣어준다. 그리고 만약 모든 비교값보다 삽입값이 더 크다면 제일 뒤의 값의 next에 삽입값을 넣어준다.

2-3 PrintLL

제일 마지막 값까지 계속 출력시켜준다



저작자표시

'파이썬으로 구현한 알고리즘' 카테고리의 다른 글

Regular Expression으로 전화번호 Search 구현하기  (0) 2017.11.16
Nested tree를 tree로 만들고 left child right sibling구조로 변환 구현하기  (0) 2017.11.16
Boyer-Moore Algorithm 구현하기  (0) 2017.11.11
KMP Algorithm 구현하기  (0) 2017.11.11
Linked list 구현하기  (0) 2017.09.25

+ Recent posts

티스토리툴바