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

1. 개요 & 알고리즘

정렬을 위해서는 다음과 같은 두 가지 동작이 필요합니다.

첫째 : 크고 작은지에 대한 '판단(decision)'

둘째 : 판단에 따라서 값을 바꾸는 '교환(exchange)'

정렬 알고리즘을 정의하자면 "판단과 교환을 어떻게 적절히 조합하는가에 대한 방법론"이라고 할 수 있습니다. ("C로 배우는 알고리즘")

정렬에서 사용하는 용어를 정리하면 다음과 같습니다.

* 파일(file) : 정렬을 하는 대상

* 레코드(record) : 파일에서 정보의 단위

* 필드(field) : 각 레코드의 정보 단위

* 키(key) : 정렬의 기준

Key를 정렬하는 방법에 따라서 아래와 같이 나눌 수 있습니다.

* 오름차순(ascending order) : 키값을 비교하여 작은 값을 앞에, 큰 값을 뒤에 두는 방법

* 내림차순(descending order) : 오름차순의 반대

정렬 알고리즘의 종류를 다음과 같이 분류할 수 있습니다.

* 간단한 알고리즘 : 선택 정렬, 삽입 정렬, 거품 정렬, 셀 정렬

* 복잡한 알고리즘 : 퀵 정렬, 기수 정렬, 힙 정렬, 병합 정렬

정렬 알고리즘의 "안정성"에 대해서 "C로 배우는 알고리즘"은 다음과 같이 정의하고 있습니다.

"안정성이란 같은 내용을 가지는 키값의 배열이 정렬 후에도 상대적 순서가 그대로 유지되면 그 알고리즘은 안정성이 있다고 하고 유지되지 않는 경우는 안정성이 없다고 한다"

예1 : 사번순으로 정렬한 후 다시 나이 순으로 정렬할 때, 사번의 순서가 유지되면 안정성이 있다고 한다.

예2 : 알파벳을 정렬할 때 같은 알파벳이 중복되어 존재하는 경우, 같은 알파벳의 순서가 정렬 과정에서 기존의 순서를 유지될 때 안정성이 있다고 한다.

"C로 배우는 알고리즘"에 설명된 선택 정렬 알고리즘은 다음과 같습니다.

1. i = 0

2. i가 n-2가 되면 끝낸다

3. 배열의 i항부터 n-1항까지 중 최소값을 찾아서 그 항을 min에 저장한다

4. 배열의 i항과 min항을 교환한다

5. i를 하나 증가시키고 2로 돌아간다

선택 정렬 알고리즘은 앞서 정의한 "안정성"이 없습니다.

정렬 알고리즘의 성능 평가를 위해서는 "이미 정렬된 배열", "난수의 배열", "반쯤 정렬된 배열", "역순의 배열"로 평가하고, 알고리즘간 성능을 비교할 수 있습니다.

2. 동작 코드

Python의 list는 링크 설명과 같이 sort method를 제공하며, 이것을 그대로 사용하면 됩니다. 다만, 알고리즘 이해를 위해서 직접 작성해 보았습니다.

# Select sort algorithm
def select_sort(elements):
    size = len(elements)
    for i in range(size - 1):
        min_index = i
        min_value = elements[i]
        for j in range(i+1, size):
            if min_value > elements[j]:
                min_index = j
                min_value = elements[j]
        elements[min_index] = elements[i]
        elements[i] = min_value

3. 실행 코드

List 'a'를 받아서 선택 정렬을 하는 실행 코드입니다.

if __name__ == '__main__':
    a = ['T', 'O', 'L', 'E', 'A', 'R', 'N', 'S', 'O', 'R', 'T', 'A', 'L', 'G', 'O', 'R', 'I', 'T', 'H', 'M']
    print("Original : ", a)
    select_sort(a)
    print("Sorted : ", a)

안정성 관련해서 원본 데이터를 동일한 'T'의 순서를 확인할 수 있도록 하고 index를 추가하고,

a = ['T1', 'O', 'L', 'E', 'A', 'R', 'N', 'S', 'O', 'R', 'T2', 'A', 'L', 'G', 'O', 'R', 'I', 'T3', 'H', 'M']

select_sort() 함수를 조금 고쳐서 첫번째 값만을 비교하도록 수정하면,

for j in range(i+1, size):
    if min_value[0] > elements[j][0]:

다음과 같은 결과를 얻을 수 있습니다.

Sorted :  ['A', 'A', 'E', 'G', 'H', 'I', 'L', 'L', 'M', 'N', 'O', 'O', 'O', 'R', 'R', 'R', 'S', 'T3', 'T1', 'T2']

즉, 'T'의 순서가 [1, 2, 3]으로 유지되지 않고, [3, 1, 2]로 변경된 것을 알 수 있으며, 이를 통해서 '선택 정렬'은 '안정성'이 없다를 확인할 수 있습니다.

4. 코드

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

"C로 배우는 알고리즘" 리스트 4-6 : REF.C에 대응하는 파일 검색과 관련한 프로그램은 아래 링크에 너무 자세히 잘 설명되어 있어서 건너 뛰도록 하겠습니다.

https://wikidocs.net/39

1. 개요 & 알고리즘

이번 포스팅에서는 프랙탈 나무를 그려보겠습니다. "C로 배우는 알고리즘"에 설명된 알고리즘은 다음과 같습니다.

1. 주어진 length와 angle을 이용하여 이동할 상대 좌표를 구한다.

2. 구한 상대 좌표로 선을 그린다. (제어점이 상대 좌표만큼 이동한다)

3. order가 0이면 6으로 간다. (종료 조건)

4. (order-1, length*SCALE, angle+TURN)에 대해 프랙탈 나무 알고리즘을 실행한다.

5. (order-1, length*SCALE, angle-TURN)에 대해 프랙탈 나무 알고리즘을 실행한다.

6. 제어점을 1의 상태로 되돌린다.

"C로 배우는 알고리즘"에서는 linerel(x, y) 함수를 사용했습니다. 링크를 참고해서 정리하면, linerel(x, y)는 (함수에는 표시되지 않지만) 현재 위치를 시작점으로 상대적(relative)으로 x, y만큼 "더" 이동한 위치를 끝점으로 선을 긋는 동작입니다.

즉, 현재 위치를 (xref, yref)라고 하면, (xref, yref)와 (xref+x, yref+y)간에 선을 긋게 됩니다.

2. 동작 코드

프랙탈 나무에 대해서는 다양한 예제를 찾아볼 수 있는데, "Turtle" 모듈을 사용한 예는 대단히 재미있습니다. 그중에서 "C로 배우는 알고리즘"과 거의 같은 코드를 찾을 수 있었습니다. Length, order, angle의 숫자만 바꾸면 되며, 이를 사용하도록 하겠습니다. 원본 코드의 실행예는 다음과 같습니다.

이를 바탕으로 "C로 배우는 알고리즘"에 있는 코드와 비슷하게 약간 변경해 봅니다.

def fixed_tree(x1, y1, angle, depth, order):
    if order > 0:
        x2 = x1 + (math.cos(math.radians(angle)) * depth)
        y2 = y1 + (math.sin(math.radians(angle)) * depth)
        plt.plot([x1, x2], [y1, y2], 'b.-')
        fixed_tree(x2, y2, angle - 30, depth * 0.8, order - 1)
        fixed_tree(x2, y2, angle + 30, depth * 0.8, order - 1)

"C로 배우는 알고리즘"에서는 0.5 radian 단위로 각도를 조정합니다. 하지만 fixed_tree()에서 angle 단위는 degree이므로, 변환하여 0.5 radian과 비슷한 30 degree를 임의로 사용했습니다.

Random 함수를 사용하는 경우의 코드는 다음과 같습니다.

def random_tree(x1, y1, angle, depth, order):
    if order > 0:
        x2 = x1 + (math.cos(math.radians(angle)) * depth)
        y2 = y1 + (math.sin(math.radians(angle)) * depth)
        plt.plot([x1, x2], [y1, y2], 'b.-')

        right_angle = random.randint(0, 40)
        left_angle = random.randint(0, 40)
        depth_scale = random.uniform(0.7, 0.9)

        random_tree(x2, y2, angle - right_angle, depth * depth_scale, order - 1)
        random_tree(x2, y2, angle + left_angle, depth * depth_scale, order - 1)

fixed_tree() 코드에서 각도를 0~40, 길이의 비율을 0.7~0.9 사이에서 random하게 선택하도록 하였습니다.

3. 실행 코드

프랙탈 나무를 그리는 실행 코드는 다음과 같습니다.("C로 배우는 알고리즘" 리스트 4-5 : FTREE.C에 대응)

if __name__ == '__main__':
    order = 10
    fixed_tree(100, 100, 90, 70, order)
#   random_tree(100, 100, 90, 70, order)
    plt.show()

order 10으로 fixed_tree()를 실행한 결과는 다음과 같습니다.

order 12로 fixed_tree()를 실행한 결과는 다음과 같습니다. (시간이 오래 걸리네요)

random_ tree를 실행한 결과는 다음과 같습니다.

4. 코드

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

1. 개요 & 알고리즘

"C로 배우는 알고리즘"에 설명된 "시어핀스키의 양탄자"를 위한 알고리즘(x, y, r)은 다음과 같습니다.

1. r이 0이 되면 끝이다 (종료 조건)

2. (x-2*r, y+2*r, r/3)에 대해 알고리즘을 실행한다.

3. (x-2*r, y, r/3)에 대해 알고리즘을 실행한다.

4. (x-2*r, y-2*r, r/3)에 대해 알고리즘을 실행한다.

5. (x, y+2*r, r/3)에 대해 알고리즘을 실행한다.

6. (x, y-2*r, r/3)에 대해 알고리즘을 실행한다.

7. (x+2*r, y+2*r, r/3)에 대해 알고리즘을 실행한다.

8. (x+2*r, y, r/3)에 대해 알고리즘을 실행한다.

9. (x+2*r, y-2*r, r/3)에 대해 알고리즘을 실행한다.

10. (x-r/3, y-r/3, x+r/3, y+r/3)에 크기의 사각형을 덜어낸다.

사각형을 그리기 위한 Python 코드입니다.

import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle

fig, ax = plt.subplots(1, 1)
rect = Rectangle((-1, 1), 1, 2, color='blue')
ax.add_patch(rect)
ax.autoscale_view()
plt.show()

Rectangle 패치를 사용했습니다(참조링크1, 참조링크2). Rectangle은 사각형의 왼쪽 아래 좌표를 주고, 가로 길이와 세로 길이를 입력하게 됩니다. 예제에서는 (-1,1)에서 시작해서 가로 1, 세로 2 크기를 갖는 사각형을 그리게 되며, 결과는 아래와 같습니다.

사각형 여러개를 그리기 위해서는 plt.show() 전에 다음 코드를 반복해서 사용하면 됩니다.

rect = Rectangle((-1, 1), 1, 2, color='blue')
ax.add_patch(rect)

2. 동작 코드

총 3가지 그림을 그리게 됩니다. ("C로 배우는 알고리즘" 리스트 4-4 : CARPET.C에 대응)

def carpet1(x, y, r):
    if r > 1:
        carpet1(x - 2 * r, y + 2 * r, r / 3)
        carpet1(x - 2 * r, y, r / 3)
        carpet1(x - 2 * r, y - 2 * r, r / 3)
        carpet1(x, y + 2 * r, r / 3)
        carpet1(x, y - 2 * r, r / 3)
        carpet1(x + 2 * r, y + 2 * r, r / 3)
        carpet1(x + 2 * r, y, r / 3)
        carpet1(x + 2 * r, y - 2 * r, r / 3)

        rect = Rectangle((x-r/6, y-r/6), r/3, r/3, color='blue')
        ax.add_patch(rect)


def carpet2(x, y, r):
    if r > 1:
        carpet2(x - 2 * r, y + 2 * r, r / 2)
        carpet2(x - 2 * r, y, r / 2)
        carpet2(x - 2 * r, y - 2 * r, r / 2)
        carpet2(x, y + 2 * r, r / 2)
        carpet2(x, y - 2 * r, r / 2)
        carpet2(x + 2 * r, y + 2 * r, r / 2)
        carpet2(x + 2 * r, y, r / 2)
        carpet2(x + 2 * r, y - 2 * r, r / 2)

        rect = Rectangle((x - r / 6, y - r / 6), r / 3, r / 3, color='blue')
        ax.add_patch(rect)


def carpet3(x, y, r):
    if r > 1:
        carpet3(x - r, y + r, r / 2)
        carpet3(x + r, y + r, r / 2)
        carpet3(x - r, y - r, r / 2)
        carpet3(x + r, y - r, r / 2)

        rect = Rectangle((x - r / 6, y - r / 6), r / 3, r / 3, color='blue')
        ax.add_patch(rect)

좌표값과 길이를 입력 받아서, 검은 바탕에 사각형의 1/3 위치(x-r/3, y-r/3)에 길이의 1/3 크기(r/3)의 하얀색 정사각형을 그리는 것입니다. 여기서 입력 받은 좌표값은 사각형의 중앙에 해당하는 값입니다. Rectangle patch 기준점은 사각형의 중앙이 아니라 좌측 아래이므로, 길이의 반(1/2)만큼 좌측 아래로 이동합니다. (x-r/3, y-r/3) -> (x-r/3/2, y-r/3/2)

3. 실행 코드

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

if __name__ == '__main__':
    fig, ax = plt.subplots(1, 1)
    carpet1(0, 0, 60)
#    carpet2(0, 0, 50)
#    carpet3(0, 0, 100)
    ax.autoscale_view()
    plt.show()

세 개의 graph를 그리게 되는데, 각각을 버튼등을 눌러서 실시간으로 전환할 수 있으면 좋겠지만, 일단은 그리려는 그래프의 주석을 풀어서 실행시 그림 하나에 대해서만 동작하도록 했습니다.

carpet1(0, 0, 60)의 실행 화면은 다음과 같습니다.

carpet2(0, 0, 50)의 실행 화면은 다음과 같습니다. (실행시간이 많이 걸렸습니다.)

carpet3(0, 0, 100)의 실행 화면은 다음과 같습니다.

4. Tips

1. 세 개의 그림을 버튼을 눌러서 전환하고 싶었습니다. matplotlib에서 그림이 나올때 아래에 아래와 같은 toolbar가 있습니다.

여기에 "Forward"와 "Back"이 있어서 이 버튼을 이용할 수 있을까하고 이것 저것 찾아보았으나 찾을 수 없었습니다. 그러다가 링크의 설명을 보니, 다른 버튼인 "확대", "이동"등과 같이 사용하는 버튼으로 제가 사용하려는 용도가 아니라는 것을 알 수 있었습니다.

5. 코드

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

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

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. 코드