더디지만... 꾸준히...

1. 개요 & 알고리즘

"재귀 호출로 문제를 해결함은 실행 시간이나 시스템의 위험성을 희생하고 소스의 간결함을 추구하고자 하느 ㄴ경우이다. 그래서 재귀 함수는 프로그램의 초기 작성 단계에서 애용되는 함수이다. 그리고 프로그램의 마무리 단계에서 재귀 함수는 같은 기능을 하는 비재귀 함수로 바꾸어지게 마련이다."

재귀적으로 문제를 해결함은 또 문제를 점점 더 작은 단위로 쪼개어서 해결함을 의미한다. 커다란 문제는 해결하기 위한 방법이 어려울지 모르나, 작은 문제는 해결 방법이 눈에 보이기 마련이다. 이렇게 큰 문제를 작은 문제로 쪼개어서 문제를 해결하는 방법이 재귀 호출을 이용하는 방법이다." (C로 배우는 알고리즘, p.263~p.264)

"재귀 호출이 이루어질 때마다 문제는 점점 작아져야 하며, 또한 재귀 호출이 끝이 나는 종료 조건(Terminate condition)이 있어야 한다는 것이다." (C로 배우는 알고리즘, p.266)

"재귀 호출은 한 함수 내에서 한번만 이루어져야 하는 것은 아니다. 한 함수 내에서 두번 혹은 그 이상도 자기자신을 호출할 수 있다. 자기 호출 횟수는 주어진 문제를 몇 개로 나누어서 푸느냐에 따라 결정이 된다." (C로 배우는 알고리즘, p.267)

"하노이의 탑 문제"는 세 개의 기둥과 서로 다른 크기인 N개의 원반으로 구성되며, 이 원반들은 세 걔의 기둥 중의 하나에 반드시 꽂혀 있어야 하고, 자신보다 작은 원반 위에는 그 원반을 놓을 수 없습니다. 그리고 기둥 1에서 기둥 3으로 모두 옮기는 것이 목표입니다.

하노이 탑의 문제를 푸는 방법은 다음과 같이 재귀적으로 표현할 수 있습니다.

1. 기둥 1에서  N-1 개의 원반을 기둥 2로 옮긴다.

2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다.

3. 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.

2. Python에서의 무한 재귀 호출

Python으로 잘못된 재귀 호출(무한 호출)하도록 함수를 구현 후 실행해 보았습니다.

def rose():
    rose()

실행시 일정 횟수를 실행하면 아래와 같은 메시지를 출력하면서 멈춥니다.

RecursionError: maximum recursion depth exceeded

Python은 Stack overflow에 의한 system 불안정을 막기 위해서 Recursion에 limitation을 가지고 있습니다.^[각주:1] 아래 명령어를 가지고 maximum recursion 횟수를 확인할 수 있습니다. 물론 sys 모듈을 사용하기 위해서 "import sys"를 먼저 해 줘야 합니다.

sys.getrecursionlimit()

그리고, 아래 명령어로 설정을 변경할 수 있습니다.

sys.setrecursionlimit(recursion횟수)

3. 동작 코드

원반을 from 기둥에서 to 기둥으로 by 기둥을 이용하여 옮기는 과정입니다.

def hanoi(self, num, where_from, where_by, where_to):
    if num == 1:
        self.move (where_from, where_to)
    else:
        self.hanoi (num-1, where_from, where_to, where_by)
        self.move(where_from, where_to)
        self.hanoi(num - 1, where_by, where_from, where_to)

(개인적으로 충분히 이해하지 못했습니다. 좀더 복잡할 것이라 생각했는데, 너무 당연하다거나 단순한 내용이 동작하는 것에 놀랍기도 합니다.)

4. 실행 코드

실행코드는 간단합니다.("C로 배우는 알고리즘" 리스트 4-1 : HANOI.C에 대응)

# main() function
if __name__ == "__main__":
    number = int(input("Enter height of HANOI tower -> "))
    hanoi = Hanoi()
    # From 1st pole to 3rd pole by using 2nd pole
    hanoi.hanoi(number, 1, 2, 3)

5. 코드

1. 개요 & 알고리즘

지금까지는 진행한 것들은 모두 선형적 자료 구조(Linear structure)"였지만, Tree는 비선형적 자료 구조(Non-linear structure)이며, 2차원적인 구조입니다. 뿌리(root)와 가지(link)로 구성되며, 잎(leaf)들이 달려 있는, 마치 나무의 모양을 거꾸로 뒤집어 놓은 모양입니다.^[각주:1] 

트리 구조는 뿌리 노드로부터 다른 노드에 이르는 경로(path)가 오직 하나 밖에 존재하지 않습니다. 이것은 트리 구조가 그래프 구조와 다른점입니다.

제일 마지막 레벨을 제외하고는 각 레벨의 노드가 꽉 차 있는 이진 트리를 완전한 이진 트리(complete binary tree)라고 하며, 모든 레벨이 꽉 차 있는 이진 나무를 꽉 차 있는 이진 나무(full binary tree)라고 합니다.

네 가지의 나무타기(Tree traverse) 방법이 있는데 이들은 각각 나무의 모든 노드들을 한 번씩 중복없이 순회하는 방법^[각주:2]을 제공합니다.

1. 뿌리를 먼저 타는 방법(전회순회, Preorder traverse)

2. 뿌리를 중간에 타는 방법(중위순회, Inorder traverse)

3. 뿌리를 나중에 타는 방법(후위순회, Postorder traverse)

4. 층별로 타는 방법(층별순회, Level order traverse)

(C로 배우는 알고리즘"^[각주:3])

기본적으로는 뿌리에서 시작해서 알고리즘에 맞는 방식에 따라서 원하는 위치를 찾아가고, 원하는 Node를 찾아서 처리하는 방식입니다.

트리 구조에 대해서는 계속 포스팅을 하게될 것입니다. 일단 수식 나무(Parse tree)^[각주:4]에 대해서 구현해봅니다. 수식 나무에서 외부 노드들은 모두 피연산자들이며, 내부 노드들은 모두 연산자들입니다.

후위 표기법을 입력으로 해서 수식 나무를 구성하는 알고리즘은 다음과 같습니다.

1. 피연산자를 만나면 node를 생성하여 stack에 push한다.

2. 연산자를 만나면 node를 생성하여

2.1 Stack에서 pop한 node를 오른쪽 자식으로 할당하고

2.2 Stack에서 또 pop한 node를 왼쪽 자식으로 할당한다.

2.3 그리고 연산자 node를 stack에 push한다.

3. Stack에서 마지막으로 남은 node가 뿌리 노드가 된다.

수식

((((A+B)*(C-D))/E) +(F*G))

을 후위 표기법으로 변환하면 아래와 같습니다.

A B + C D - * E / F G * +

이것을 위의 알고리즘에 맞춰 Tree로 구성하면 아래와 같습니다.^[각주:5]

2. 동작 코드

def is_legal(self, equation):
    num_of_operator = 0
    size = len(equation)
    step = 0
    while size != step:
        while equation[step] == ' ':
            step += 1
        if self.is_operator(equation[step]):
            num_of_operator -= 1
        else:
            num_of_operator += 1
        if num_of_operator < 1:
            break
        step += 1

    if num_of_operator == 1:
        return True
    else:
        return False

def make_parse_tree(self, equation):
    while len(equation) != 0:
        while equation[0] == ' ':
            del equation[0]
        node = Node()
        node.key = equation[0]
        node.left = self.tail
        node.right = self.tail
        if self.is_operator(equation[0]):
            node.right = self.stack.pop()
            node.left = self.stack.pop()
        self.stack.append(node)
        del equation[0]
    self.head.right = self.stack.pop()

3. 실행 코드

중위 표기법으로 수식을 입력 받아서 후위 표기법으로 변환한 후, 수식 나무를 구성하고, 네 가지의 나무타기 방법으로 수식 나무의 내용을 출력하는 프로그램입니다("C로 배우는 알고리즘" 리스트 3-14 : TREE1.C에 대응) 

중위 표기법을 후위 표기법으로 변경하는 프로그램은 앞선 포스팅^[각주:6]을 그대로 이용하였습니다.

후위 표기법으로 변환한 후에는 수식 나무로 구성한 후, 앞서 Tree를 순회하는 방법 4가지에 따라서 순회하도록 했습니다.

# main() function
if __name__ == "__main__":
    # Change infix notation to postfix notation
    source = "((((A+B)*(C-D))/E)+(F*G))"#input("Please input -> ")
    postfix = Postfix()
    contents = postfix.do_postfix(source)
    print(contents)
    #
    tree = Tree()
    if tree.is_legal(contents) is not True:
        print ("Expression is not legal")
    else:
        tree.make_parse_tree(contents)
        tree.preorder_traverse(tree.head.right)
        print()
        tree.inorder_traverse(tree.head.right)
        print()
        tree.postorder_traverse(tree.head.right)
        print()
        tree.levelorder_traverse(tree.head.right)
        print()

4. Tips

1. Python에서는 Node class와 같은 것도 append 함수로 List에 추가할 수 있었습니다.

@staticmethod
def visit(n):
    print(n.key, end=" ")

3. Queue는 따로 구현하지 않고, Python이 제공하는 Queue를 그대로 사용했습니다.^[각주:8]

5. 코드

1. 개요 & 알고리즘

Linked list로 Queue를 구현하는 경우, FIFO의 특성상 Doubly Linked List로 구현합니다. ("C로 배우는 알고리즘"^[각주:1])

2. 동작 코드

기존 포스팅에서 사용했던 Doubly linked list 코드^[각주:2]를 기본으로, put()과 get()등을 추가합니다. 추가한 put()은 다음과 같습니다.

def put(self, data):
    new_node = Node()
    new_node.key = data
    # Insert new_node in front of tail
    self.tail.prev.next = new_node
    new_node.prev = self.tail.prev
    self.tail.prev = new_node
    new_node.next = self.tail

    return data

get()은 아래와 같이 추가했습니다.

def get(self):
    t = self.head.next
    if t == self.tail:
        print("Queue underflow")
        return False
    data_temp = t.key
    # Remove node
    self.head.next = t.next
    t.next.prev = self.head

    return data_temp

3. 실행 코드

실행 코드는 앞선 포스팅^[각주:3]과 거의 같습니다 ("C로 배우는 알고리즘" 리스트 3-13 : QUEUE2.C에 대응)

# main() function
if __name__ == "__main__":
    queue = QueueWithDoubleLinkedList()

    print("Put 5, 4, 7, 8, 2, 1")
    queue.put(5)
    queue.put(4)
    queue.put(7)
    queue.put(8)
    queue.put(2)
    queue.put(1)
    queue.print_queue()

    print("Get")
    data = queue.get()
    queue.print_queue()
    print("Getting value is ", data)

    print("Put 3, 2, 5, 7")
    queue.put(3)
    queue.put(2)
    queue.put(5)
    queue.put(7)
    queue.print_queue()

    print("Initialize queue")
    queue.clear_queue()
    queue.print_queue()

    print("Now queue is empty, get")
    data = queue.get()
    queue.print_queue()
    print("Getting value is ", data)

5. 코드