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

"C로 배우는 알고리즘"는 1994년에 1판이 출간되었고, 제가 가지고 있는 책은 2001년판입니다. 그래서 책 맨 뒤에 3.5인치 플로피 디스크가 붙어 있습니다. 그래서 간단한 예를 위해서 ASCII와 gotoxy()등을 사용하고 있습니다.

그런데, Python에서는 기본적으로 Terminal 관련 기능을 제공하지 않습니다.^[각주:1] 이를 사용하기 위해서 "curses"라는 모듈을 설치/사용해 보았습니다.

"curses" 모듈^[각주:2] 사용을 위해서 아래와 같이 진행했습니다.

1. 현재 사용하고 있는 Python의 version 을 윈도우 cmd 창에서 아래 명령어로 확인했습니다.

C:\ python --version
Python 3.6.5

즉, Python version은 3.6.5임을 확인했습니다.

2. "curses" 모듈 홈페이지^[각주:3]에서 적절한 파일을 다운로드합니다. 블로그^[각주:4] 내용을 참고해서 "curses-2.2+utf8-cp36-cp36m-win_amd64.whl"을 다운로드하고, Python을 위한 pip가 있는 폴더(보통 Python이 있는 위치의 scripts 폴더에 위치합니다)에 복사합니다.

3. 윈도우 cmd창에서 pip가 있는 폴더로 이동해서 "pip install" 명령으로 설치합니다.

c:\>pip install curses-2.2-cp36-cp36m-win_amd64.whl
Processing c:\python36\scripts\curses-2.2-cp36-cp36m-win_amd64.whl
Installing collected packages: curses
Successfully installed curses-2.2

4. 아래와 같은 예제 코드를 사용해서 시험합니다.

import curses
stdscr = curses.initscr()

# Clear screen
stdscr.clear()

stdscr.addstr(10, 5, "First Position(10, 5)")
stdscr.addstr(20, 5, "Second Position(20, 5)")
stdscr.addstr(5, 20, "Third Position(5, 20)")

stdscr.refresh()
stdscr.getkey()

5. 그런데, Pycharm에서는 "Redirection is not supported." 메시지만 확인되고, 동작을 확인할 수 없습니다. Pycharm등의 GUI가 Terminal을 지원하지 않기 때문^[각주:5]이라고 합니다.

6. 윈도우 cmd 창에서 "python 파일명"으로 동작을 확인할 수 있었습니다.

이상으로 Python을 위해서 curses 모듈을 설치/시험해 보았습니다.

1. 알고리즘

텍스트 모드에서 그래픽 문자를 이용하여 미로를 화면에 표시합니다. 미로는 2차원 배열로 미리 작성해 둔 것을 사용하며, 우측 하단에서 출발하여 좌측 상단에 도착하는 것을 목표로 합니다. "C로 배우는 알고리즘"^[각주:1]에 설명된 알고리즘은 우선법(right hand all wall) 방법으로 최단 경로를 계산하여 계산된 최단 경로로 다시 한번 이동하는 모습을 보입니다. 내용을 찾아서 검색하다가 유용한 링크를 찾았습니다.

• http://ddmix.blogspot.kr/2014/12/cppalgo-4-array-maze.html
• http://codingdojang.com/scode/481

2. 동작 코드

아래와 같은 상수를 정의해서 미로를 배열로 표시합니다.

UP = 1
RIGHT = 2
DOWN = 4
LEFT = 8

OR 연산을 이용해서 다양한 표현이 가능하도록, 2^0, 2^1, 2^2, 2^3으로 신경써서 정의했습니다. 이를 이용해서 벽의 모양을 표시하면 아래와 같은 표를 작성할 수 있습니다.

아래 링크들을 참고했습니다.

• http://www.theasciicode.com.ar/
• https://stackoverflow.com/questions/46063974/printing-extended-ascii-characters-in-python

• http://svn.python.org/projects/stackless/trunk/Lib/encodings/cp720.py

그림을 그리기 위한 get_shape 함수는 다음과 같습니다.

def get_shape(m, x, y):
    shape = (u' ', u'\u2502', u'\u2500', u'\u2514', u'\u2502', u'\u2502', u'\u250c', u'\u251c', u'\u2500', u'\u2518',
             u'\u2500', u'\u2534', u'\u2510', u'\u2524', u'\u252c', u'\u253c')
    s = 0
    if m[x][y] != 0:
        # Check upper range
        if x > 0 and m[x-1][y] != 0:
            s |= UP
        # Check lower range
        if x < MAZE_SIZE - 2 and m[x+1][y] != 0:
            s |= DOWN
        # Check left range
        if y > 0 and m[x][y-1] != 0:
            s |= LEFT
        # Check right range
        if y < MAZE_SIZE - 2 and m[x][y+1] != 0:
            s |= RIGHT

    return shape[s]

그림을 그리는 실제 함수는 다음과 같습니다.

def draw_maze(m):
    for j in range(MAZE_SIZE):
        for i in range(MAZE_SIZE):
            ch = get_shape(m, i, j)
            stdscr.addstr(i+1, j+1, ch)

터미널을 사용하기 위해서 curses^[각주:2]를 이용했습니다. C언어의 gotoxy()에 해당하는 함수가 stdscr.addstr()입니다.

3. 실행 코드

위의 두 함수를 이용해서 문제에 이용하는 미로를 그리는 코드입니다. ("C로 배우는 알고리즘" 리스트 3-3 : ROBOT.C의 일부)

maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ,1, 1, 1, 1, 1, 1, 1, 1],
        [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ,0, 0, 0, 1, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1],
        [1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

stdscr = curses.initscr()
# Clear screen
stdscr.clear()

draw_maze(maze)

stdscr.refresh()
stdscr.getkey()

윈도의 cmd창에서 위 코드를 수행하면 아래와 같은 미로 그림을 볼 수 있습니다.

1. 알고리즘

"C로 배우는 알고리즘"에 설명된 에라토스테네스의 체는 정해진 숫자 이하의 모든 소수를 구하는 것입니다. 이를 위해서 정해진 숫자 크기의 배열을 만들고 진행한다.

2. 실행 코드

MAX_RANGE = 9999

numbers = []
for i in range(MAX_RANGE+1):
    numbers.append(0)

for i in range(2, MAX_RANGE+1):
    # If value is '1', it was deleted
    if numbers[i] == 1:
        continue
    for j in range(i+i, MAX_RANGE+1, i):
        # Delete values which are multiple i. Value '1' means, it was deleted.
        numbers[j] = 1

for i in range(2, MAX_RANGE+1):
    if numbers[i] != 1:
        # To print one line, use 'end=" "'
        print(i, end=" "),
print()

4. Tips