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

예전에는 Ultra editor를 사용했습니다. 데이터 정리등을 위해서 매크로 기능을 사용했는데, 프로그래밍하기도 간단했죠. 그러다 유료인 Ultra editor 대신 무료 application을 사용하라는 요청을 받았습니다. Vi도 대안이겠지만, Windows를 주로 사용하다 보니 GUI 지원을 선호해서 Vi 보다는 Notepad++를 선택했습니다. Notepad++에 대한 tips을 정리하면 이후 유용할 것으로 보여 정리하게 되었습니다.

• 중복되는 줄 삭제

reference: https://www.it-swarm.net/ko/notepad%2B%2B/%EB%A9%94%EB%AA%A8%EC%9E%A5%EC%97%90%EC%84%9C-%EC%A4%91%EB%B3%B5-%ED%96%89-%EC%A0%9C%EA%B1%B0/970641118/

원래는 Notepad++에서 TextFX plugin을 사용했습니다. 그런데, 윈도우를 64bit로 설치하면서 64bit용 TextFX plugin을 설치했는데도 동작하지 않았습니다. 그러다 링크의 site를 발견했죠.ㅕㅜ

Notepad++이 정규 표현식을 지원하는 줄도 몰랐는데, 단 몇자의 글자로 중복되는 줄을 삭제하는 기능을 사용할 수 있다니 정말 놀랍습니다. 간단한 정규표현식은 공부했습니다만, 여기에 사용하는 정규표현식을 해석하기도 쉽지 않으니, 정규표현식을 자유자재로 사용하는 것은 항상 부럽네요.

방법은 reference 링크과 같습니다.

1. Replace 메뉴를 선택 (Ctrl+h)

2. 윈쪽 아래 "Regular express"을 선택하고, "matches new line"도 체크

3. 찾는 문자열에 아래 정규식을 입력

^(.*?)$\s+?^(?=.*^\1$)

4. "찾아서 변경하기" 버튼을 누르면 중복되는 라인이 사라짐

• 바탕 화면만 나올 때 (reference: https://jangjy.tistory.com/217)

이유는 알기 어렵지만, 우분투로 부팅을 했는데 이상 동작을 했습니다.

1. 아이콘 하나도 없음

2. 바탕 화면만 나오면서,

3. "Ctrl+Alt+t"을 눌러도 터미널이 실행되지 않음

다행히 "Ctrl+Alt+F1"은 동작했고, console을 띄울 수 있었습니다.

링크의 블로그를 따라서 아래 명령어를 입력했을 때 아이콘도 보이고 런처가 정상 동작을 했습니다.

다만, 한글 설정이나 런처의 기본 아이콘 설정은 변경되어 다시 설정해야 했습니다.

$ sudo service lightdm stop
$ rm ~/.config/dconf/user
$ sudo service lightdm start

find 관련해서 가장 자주 사용하는 명령어는 아래와 같습니다.

$ find . -name "*.c" | xargs grep -n --color=auto "KeyWord" 2> /dev/null

명령어의 의미는

1. 현재 디렉토리 이하에서 'c'  확장자를 가지는 모든 파일을 찾아라.

2. 찾은 파일들에 대해서 grep 명령어로 'KeyWord'를 포함하는 행을 찾아라.

    이때 행 번호를 표시하고, color로 나타내라

3. 에러가 발생하는 경우 console에 표시하지 마라.

입니다.

기타 가끔 사용하지만 유용한 find 관련 내용을 정리합니다.

• cscope.files 생성

$ find . -name "*.[cCsShH] -a -type f > cscope.files

1. c(C), s(S), h(H) 확장자를 가지는 파일들을 검색합니다.

2. 그리고 (-a, and) 파일만 검색합니다. (링크 걸린 파일은 사용하지 않기 위해서)

3. cscope.files로 저장한다.

• 찾은 갯수 표시

$ find . -name "File.name" | cat -n

'cat -n' 명령은 출력마다 번호를 붙이는 명령입니다. 이를 pip로 연결하면 find한 파일마다 번호를 붙이게 됩니다.

1 ./3.txt
2 ./2.txt
3 ./1.txt

리눅스 Python 3.5.3 환경에서 Tensorflow를 'pip install tensroflow'로 설치 후 MNIST 예제를 실행하기 위해서 아래 코드를 수행했습니다.

# MNIST 데이터를 다운로드 한다.
from tensorflow.examples.tutorials.mnist import input_data
mnist = input_data.read_data_sets("MNIST_data/", one_hot=True)

그런데 아래와 같은 에러가 확인됩니다.

ImportError: No module named 'tensorflow.examples.tutorials'

Python 2.x 버전으로 변경해 봐도 동일한 문제가 확인됩니다.

아래 명령어를 이용해서 설치된 tensorflow의 버전을 확인해 보면, version 2.0을 사용하고 있습니다.

>>> import tensorflow as tf
>>> tf.__version__

virtualenv 환경을 이용해서 시험했는데, venv 폴더 하위에서 mnist 관련 examples 폴더는 없었습니다. github에서 tensorflow version 2.0을 살펴보면 example 폴더가 정상적으로 존재하는 것은 확인했습니다. 다운로드만 되지는 않은 것으로 보입니다.

다시 시험을 위해서 모두 지우고, virtualenv 환경을 다시 한번 셋업했습니다. 이번에는 Python 3.5 버전에 맞는 tensorflow를 아래 명령어를 이용해서 직접 설치했습니다. (https://www.tensorflow.org/install/pip 참조)

pip install https://storage.googleapis.com/tensorflow/linux/cpu/tensorflow-1.14.0-cp35-cp35m-linux_x86_64.whl

이후에는 MNIST 다운로드가 실행되었습니다.

Tensorflow version을 확인해 보면 "1.14.0"으로 확인되었으며, 아래와 같이 input_data.py 파일도 확인할 수 있었습니다.

./venv/lib/python3.5/site-packages/tensorflow/examples/tutorials/mnist/input_data.py

정확한 이유는 알기 어렵지만, python 3.5.x와 관련해서는 tensorflow version 2.0이 아닌 1.14.0으로 해야 example import 에러를 회피할 수 있는 것으로 생각됩니다. github에서 tensorflow version 2.0에 example 폴더가 정상적으로 존재하므로, github에서 직접 다운로드하는 해결책이 있을 것으로 보이지만, 진행해 보지는 않았습니다.

개요

리눅스를 개발환경으로 해서 프로그래밍을 하다보면 grep을 많이 사용하게 됩니다. 특히나 소스 코드를 직접 개발하기 보다는, 이미 개발되어 있는 소스 코드를 이용하는 경우에는 더욱 많이 사용합니다.
유용한 grep의 옵션들을 정리합니다.

[참고] 리눅스는 하나의 작업을 위한 매우 다양한 방법을 제공합니다. 당연히 본문의 예제들보다 효과적인 방법들이 있을 것입니다.

원하는 라인 전후 출력하기

프로그래밍에서는 grep으로 특정 keyword를 포함하는 파일들을 검색한후, 해당 파일들을  editor로 열어서 검토합니다. 그런데, 프로그래밍 이외에 매우 많은 양의 로그파일들에서 정형화된 포맷의 문제 부분들을 찾아서 검토하는 예의 경우, 일일이 파일들을 열어서 문제점을 검토하기는 번거롭습니다.

또 "git log"로 commit된 내용을 확인할 때, 특정 keyword로 내용을 확인한 후 해당 keyword 앞서에 위치하는 commit ID를 알아서 전체 내용을 검토하고자 할 때 유용합니다.

이때 grep의 -A 혹은 -B 옵션을 사용할 수 있습니다.

[기본]

grep -A 라인수1 -B 라인수2 키워드 파일명

[해석]

파일명의 이름을 갖는 파일에서 키워드를 찾아서, 키워드를 포함하는 라인 이후(-A 옵션) 라인수1 만큼의 라인, 키워드를 포함하는 라인 이전(-B 옵션) 라인수2 만큼의 라인을 출력한다.

[예제]

grep -A 10 -B 5 "Internal error" kernel_panic.txt

참조 sites

https://iknow.tistory.com/entry/grep-사용해서-원하는-라인-전후까지-출력하기

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