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

1. 개요 & 알고리즘

"C로 배우는 알고리즘"에 설명된 내부 영역 그리기 알고리즘(Flood Fill)은 다음과 같습니다.

1. 현재 위치 (X, Y)의 점을 읽어 그것이 경계색이거나 이미 채워진 부분이면 끝낸다.

2. 현재 위치 (X, Y)의 점을 지정된 색으로 찍는다.

3. (X-1, Y)에 대해 영역을 칠하는 알고리즘을 실행한다.

4. (X+1, Y)에 대해 영역을 칠하는 알고리즘을 실행한다.

5. (X, Y-1)에 대해 영역을 칠하는 알고리즘을 실행한다.

6. (X, Y+1)에 대해 영역을 칠하는 알고리즘을 실행한다.

링크를 참고해서 matplotlib로 원을 그릴 수는 있었습니다. 그런데, 현재 위치 (X,Y)의 점을 읽는 방법을 찾을 수 없었습니다. 그래서 다른 방법을 사용했습니다. 다행히 예제가 원 내부를 칠하는 것이라서, 현재 위치 (X,Y)가 원 내부에 있는지를 수치적으로 판단해서 점을 찍을지 끝낼지를 판단하도록 했습니다.

이렇게 해서 점으로라도 원 내부를 칠할 수 있었지만, 알고리즘의 3, 4, 5, 6 단계에서 동일한 위치에 대해서 재귀 호출이 중복해서 일어납니다. 예를 들며 (0,0)에 대해서 점을 찍는 동작이 현재 위치 (0,0)에 대해서도 일어나지만, 현재 위치 (1,0) 위치에서 (X-1, Y) 재귀 함수를 호출 하는 경우에도 일어납니다. 동일한 위치에 대해서 재귀 호출이 중복되어 일어나는 바람에 Python에서는 재귀 호출이 너무 많다는 에러가 발생했습니다. Python의 List를 이용해서 저장하고, 검색해서 가능한한 중복 호출이 일어나지 않도록 했습니다.

2. 동작 코드

원을 그리는 동작 코드는 다음과 같습니다. 반지름(radius)는 global 변수로 사용했습니다.

def create_circle():
    circle= plt.Circle((0,0), radius= radius, fill=False)
    return circle


def show_shape(patch):
    ax=plt.gca()
    ax.add_patch(patch)
    plt.axis('scaled')

plt.Circle()에서 "fill=False"를 사용해서 원 둘레만 그렸습니다. "fill=False"를 생략하면 색칠한 원이 그려집니다.

위 함수들을 이용해서 원을 그리는 코드는 다음과 같습니다.

c = create_circle()
show_shape(c)
plt.show()

반복 실행을 최대한 줄이기 위해서 List를 이용해서 찍은 점을 저장했는데, List에서 점의 포함 여부를 확인하는 방법은 링크를 참고했습니다. List에 포함 여부를 확인하는 방법은 아래와 같이 매우 간단합니다.

if 'abc' in my_list:

이를 이용해서 원 내부에만 점을 찍는 함수는 다음과 같이 작성했습니다.

def recur_fill(x, y, pixel_list):
    if x > radius or x < -radius:
        return
    else:
        y_ref = math.sqrt(radius*radius - x*x)

    if y < (-1) * y_ref or y > y_ref:
        return
    else:
        plt.plot([x], [y], 'bo')
        pixel_list.append([x, y])

        if not [x-step, y] in pixel_list:
            recur_fill(x-step, y, pixel_list)

        if not [x+step, y] in pixel_list:
            recur_fill(x+step, y, pixel_list)

        if not [x, y-step] in pixel_list:
            recur_fill(x, y-step, pixel_list)

        if not [x, y+step] in pixel_list:
            recur_fill(x, y+step, pixel_list)

작업하려는 도형이 원이었기 때문에 억지스럽게 작성한 코드로 실용성은 없습니다.

3. 실행 코드

실행 코드는 다음과 같습니다.("C로 배우는 알고리즘" 리스트 4-3 : FILL1.C에 대응)

if __name__ == '__main__':
    c = create_circle()
    show_shape(c)
    pixel_list = []
    recur_fill(0, 0, pixel_list)
    plt.show()

결과는 다음과 같습니다.

재귀 호출을 비재귀 호출 함수로 변경하는 작업은 진행하지 않았습니다.

4. Tips

Python에서 "(-1)*variable"은 그냥 "-variable"로 표현해도 됩니다.

5. 코드

주로 "C로 배우는 알고리즘"에 적혀 있는 내용을 주고 사용하고, 필요시 인터넷 검색의 결과를 이용하였습니다. 이용한 출처는 밝히는 것을 원칙으로 합니다만, 혹시 실수가 있거나 문제되는 사항이 있다면 알려 주십시오. 수정하도록 하겠습니다.

1. matplotlib

Python의 가장 큰 장점은 누군가 미리 개발해 놓은 다양한 모듈들을 import해서 사용할 수 있다는 것입니다. Graphic 관련해서도 다양한 모듈이 있는데 그 중에서 matplotlib가 유명합니다. 시작된지 약 15년 이상된 프로젝트로 상용 프로그램에 버금가는 결과물을 만드는 것이 목표입니다.

Matplotlib 관련해서는 인터넷을 통해서 다양한 자료들을 찾을 수 있습니다. 그 중에서도 아래 링크와 그 후속 포스팅 내용들을 그대로 따라하면서 matplotlib에 대해서 감을 잡을 수 있었습니다.

https://wikidocs.net/2875

Matplotlib 홈페이지(https://matplotlib.org/)등을 참고하면 보다 전문적인 내용들을 확인할 수 있습니다.

이미 matplotlib만으로 직선 그리기와 원 색칠하기등을 수행할 수 있습니다만, 알고리즘을 배우는 차원에서 "C로 배우는 알고리즘"에 설명된 내용을 따라가 보겠습니다. (matplotlib는 pip등으로 이미 설치되어 있다고 가정하겠습니다.)

2. 동작 코드

Mathplotlib를 이용하기 위해서 import했습니다.

import matplotlib.pyplot as plt

두 점이 주어지면 재귀 함수를 이용해서 선을 그리는 동작 코드입니다.

pixel_step = 0.5


def recursive_line(x1, y1, x2, y2):
    if -pixel_step <= x1-x2 <= pixel_step and -pixel_step <= y1-y2 <= pixel_step:
        pass
    else:
        plt.plot([(x1+x2)/2], [(y1+y2)/2], 'bo')
        recursive_line(x1, y1, (x1+x2)/2, (y1+y2)/2)
        recursive_line(x2, y2, (x1+x2)/2, (y1+y2)/2)

plt.plot() 함수와 'bo' 옵션을 사용해서 파란색에 원 모양의 marker를 그리도록 하였습니다. 점간의 간격은 pixel_step이라는 global 변수를 사용했습니다. read only 변수이므로 따로 global이라는 키워드를 사용하지는 않았습니다.

3. 실행 코드

(10, 10)에서 (600, 350) 사이에 선을 그리는 실행 코드는 다음과 같습니다. ("C로 배우는 알고리즘" 리스트 4-2 : LINE.C에 대응)

if __name__== '__main__':
    recursive_line (10, 10, 600, 350)
    plt.show()

실행 결과는 아래와 같습니다.

recursive_line()로는 데이터 list만 만들고, 만든 데이터 list를 한꺼번에 plt.plot()으로 그리는 방법도 있어 보입니다.

4. 코드

주로 "C로 배우는 알고리즘"에 적혀 있는 내용을 주고 사용하고, 필요시 인터넷 검색의 결과를 이용하였습니다. 이용한 출처는 밝히는 것을 원칙으로 합니다만, 혹시 실수가 있거나 문제되는 사항이 있다면 알려 주십시오. 수정하도록 하겠습니다.

1. 개요 & 알고리즘

재귀 호출은 다음과 같은 이유로 실질적인 사용에 있어서는 배제되는 경우가 많습니다. ("C로 배우는 알고리즘", p.274)

1. 함수 호출에 따른 Context Switching에 시간이나 resource를 사용해야 하므로, 재귀 호출을 사용하지 않는 경우에 비해서 속도가 느립니다.

2. 재귀 호출시 계속 Stack을 사용하게 되므로, 시스템 다운의 우려(혹은 메모리의 과도한 사용)가 있습니다.

재귀 함수를 비재귀 함수로 변경하는 것은 생각보다 쉬운일이 아니지만, 유형별로 확인해 봅니다.

1.1. 재귀 호출이 하나인 경우

For나 While등의 순환문을 이용해서 비재귀 함수를 재구성해 봅니다.

1.2. 재귀 호출이 둘인 경우 1

세 가지로 구분할 수 있습니다. 재귀 호출하는 부분을 제외한 나머지 실제로 작업을 하는 부분을 process() 함수라고 정의한다면, 이 process()가 두 재귀 호출의 앞에 나와 있는가, 아니면 두 재귀 호출의 사이에 있는가, 아니면 두 재귀 호출의 뒤에 있는가하는 세가지입니다.

1.2.1 유형 1 - process()가 두개의 재귀 호출 앞에 있는 경우

recursive(인자 리스트)
{
    if (종료 조건)
    {
        종료 처리
    }
    else
    {
        process(인자 리스트)
        recursive(변경된 인자 1)
        recursive(변경된 인자 2)
    }
}

를 아래와 같이 변형합니다. ("C로 배우는 알고리즘", p.276)

non_recursive(인자 리스트)
{
    /* 스택의 초기화 */
    init_stack()
    push(인자 리스트)
    /* 스택이 비면 끝 */
    while(!is_stack_empty())
    {
        인자 리스트 = pop()
        if(!종료 조건)
        {
            process(인자 리스트)
            push(변경된 인자 1)
            push(변경된 인자 2)
        }
        /* 종료 조건이면 */
        else
        {
            종료 처리
        }
}

1.2.2 유형 2 - process()가 두개의 재귀 호출 가운데 있는 경우

recursive(인자 리스트)
{
    지역 변수들
    if (종료 조건)
    {
        종료 처리
    }
    else
    {
        recursive(변경된 인자 1)
        process(인자 리스트)
        recursive(변경된 인자 2)
    }
}

를 아래와 같이 변형합니다. ("C로 배우는 알고리즘", p.279~280)

non_recursive(인자 리스트)
{
    /* 작업을 완료 했은지를 확인하기 위한 Flag */
    int done = 0;
    /* 스택의 초기화 */
    init_stack()
    while(!done)
    {
        while(!종료 조건)
        {
            push(인자 리스트)
            인자 리스트 = 변화된 인자 1
        }
        종료 처리
        if(!is_stack_empty())
        {
            인자 리스트 = pop()
            process(인자 리스트)
            인자 리스트 = 변화된 인자 2
        }
        else
        {
            done = 1
        }
}

1.2.3 유형 3 - process()가 두개의 재귀 호출 뒤에 있는 경우

recursive(인자 리스트)
{
    지역 변수들
    if (종료 조건)
    {
        종료 처리
    }
    else
    {
        recursive(변경된 인자 1)
        recursive(변경된 인자 2)
        process(인자 리스트)
    }
}

를 아래와 같이 변형합니다. ("C로 배우는 알고리즘", p.282~284)

non_recursive(인자 리스트)
{
    /* 작업을 완료 했은지를 확인하기 위한 Flag */
    int done = 0;
    /* 무한 루프를 방지하기 위한 방책 */
    인자 리스트의 복사본
    /* 스택의 초기화 */
    init_stack()
    while(!done)
    {
        while(!종료 조건)
        {
            push(인자 리스트)
            인자 리스트 = 변화된 인자 1
        }
        종료 처리
        if(!is_stack_empty())
        {
            인자 리스트 복사본 = 인자 리스트
            인자 리스트 = pop()
            if (인자 2로의 변화가 종료 조건이 아니면)
            {
                if(인자 2로의 변화 == 인자 리스트의 복사본)
                {
                    process(인자 리스트)
                }
                else
                {
                    push(인자 리스트)
                    인자 리스트 = 변화된 인자 2
                    break
                }
            }
        }
        else
        {
            process(인자 리스트)
        }
        if(is_stack_empty)
        {
            done = 1
        }
}

2. 동작 코드

이진 나무 타기 함수들을 앞서의 내용에 따라 Python으로 작성했습니다. 함수명 뒤에 _nr이 붙은 함수가 비재귀 함수입니다.

유형 1

def preorder_traverse(self, n):
    node = n
    if node != self.tail:
        self.visit(node)
        self.preorder_traverse(node.left)
        self.preorder_traverse(node.right)

def preorder_traverse_nr(self, n):
    stack = []
    node = n
    stack.append(node)
    while len(stack) != 0:
        node = stack.pop()
        if node != self.tail:
            self.visit(node)
            stack.append(node.right)
            stack.append(node.left)

유형 2

def inorder_traverse(self, n):
    node = n
    if node != self.tail:
        self.inorder_traverse(node.left)
        self.visit(node)
        self.inorder_traverse(node.right)

def inorder_traverse_nr(self, n):
    stack = []
    node = n
    done = 0
    while done == 0:
        while node != self.tail:
            stack.append(node)
            node = node.left
        if len(stack) != 0:
            node = stack.pop()
            self.visit(node)
            node = node.right
        else:
            done = 1

유형 3

def postorder_traverse(self, n):
    node = n
    if node != self.tail:
        self.postorder_traverse(node.left)
        self.postorder_traverse(node.right)
        self.visit(node)

def postorder_traverse_nr(self, n):
    stack = []
    node = n
    done = 0
    while done == 0:
        while node != self.tail:
            stack.append(node)
            node = node.left
        while len(stack) != 0:
            t = node
            node = stack.pop()
            if node.right != self.tail:
                if node.right == t:
                    self.visit(node)
                else:
                    stack.append(node)
                    node = node.right
                    break
            else:
                self.visit(node)
        if len(stack) == 0:
            done = 1

"C로 배우는 알고리즘"을 그대로 작성한 것으로, Python 코드를 작성해서 동일한 결과를 얻을 수는 있었습니다만, 충분히 이해하지는 못하고 있습니다.

3. 실행 코드

실행 코드는 다음과 같습니다.

# main() function
if __name__ == "__main__":
    # Change infix notation to postfix notation
    source = ['A', 'B', '+', 'C', 'D', '-', '*', 'E', '/', 'F', 'G', '*', '+']

    tree = Tree()
    tree.make_parse_tree(source)

    print("[Preorder]")
    print("    Recursive : ", end=' ')
    tree.preorder_traverse(tree.head.right)
    print()
    print("Non Recursive : ", end=' ')
    tree.preorder_traverse_nr(tree.head.right)
    print()

    print("[Inorder]")
    print("    Recursive : ", end=' ')
    tree.inorder_traverse(tree.head.right)
    print()
    print("Non Recursive : ", end=' ')
    tree.inorder_traverse_nr(tree.head.right)
    print()

    print("[Postorder]")
    print("    Recursive : ", end=' ')
    tree.postorder_traverse(tree.head.right)
    print()
    print("Non Recursive : ", end=' ')
    tree.postorder_traverse_nr(tree.head.right)
    print()

4. Tips

1. Python에서 리스트의 복사와 관련해서 잘 정리된 문서^[각주:1]를 참고하세요.

5. 코드

주로 "C로 배우는 알고리즘"에 적혀 있는 내용을 주고 사용하고, 필요시 인터넷 검색의 결과를 이용하였습니다. 이용한 출처는 밝히는 것을 원칙으로 합니다만, 혹시 실수가 있거나 문제되는 사항이 있다면 알려 주십시오. 수정하도록 하겠습니다.