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

1. 알고리즘

경로를 모두 저장한 다음, 동일한 좌표가 나오는 경우를 확인합니다. 만약 동일한 좌표가 확인되면, 일종의 jump를 한다고 생각하고, 그 사이에 있는 좌표를 모두 삭제합니다. 이후에 "최단 경로"로 동작을 합니다.

2. 동작 코드

경로를 저장하는 코드는 매우 간단하게 작성합니다.

def record(x, y):
    rec.append(x)
    rec.append(y)

동일한 좌표를 찾았을 때 삭제하는 코드는 다음과 같습니다.

def del_path(i, j):
    k = i
    while(rec[j] >=0 ):
        rec[i] = rec[j]
        i += 1
        j += 1
    rec[i] = -1

    return k

최단 거리를 찾고, 다시 한번 애니메이션을 보여주는 코드는 다음과 같습니다.

def shortest_path():
    i = 0

    while rec[i] >= 0:
        x = rec[i]
        y = rec[i+1]
        j = i + 2
        while rec[j] >= 0:
            x1 = rec[j]
            y1 = rec[j + 1]
            if x==x1 and y==y1:
                j = del_path(i, j)
            j += 2
        i += 2

    # Display shortest path
    i = 0
    while rec[i] >= 0:
        x = rec[i]
        y = rec[i+1]
        i += 2
        if TERMINAL:
            stdscr.addstr(x + 1, 2*(y + 1), "*")
            stdscr.refresh()
            time.sleep(0.1)
            stdscr.addstr(x + 1, 2*(y + 1), " ")
            stdscr.refresh()

3. 실행 코드

최종적으로 미로를 그리고, right hand on wall 기법으로 출구를 찾고, 마지막으로 "최단거리"로 찾아가는 코드를 작성했습니다. ("C로 배우는 알고리즘" 리스트 3-3 : ROBOT.C) 아래 링크를 참고해 주십시오.

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_1_2.py

이상으로 "미로에 갖힌 생쥐"편을 마칩니다.

1. 알고리즘

"C로 배우는 알고리즘"^[각주:1]에 설명된 right hand on wall 알고리즘은 다음과 같습니다.

1. 앞으로 간다.

2.아직 미로 안에 갖혀 있다면

2.1. 오른쪽으로 방향을 90도 튼다.

2.2. 만약 벽이 앞에 있다면

2.2.1 왼쪽으로 방향을 90도 튼다.

2.3 앞으로 간다.

2.4 2로 돌아감

3. 미로 탈출 성공!

2. 동작 코드

앞으로 가는 함수은 forward() 함수는 다음과 같습니다.

def forward(x, y, dir):
    # Delete mouse
    if TERMINAL:
        stdscr.addstr(x + 1, 2*(y + 1), " ")
        stdscr.refresh()

    if dir == LEFT:
        y -= 1
    if dir == RIGHT:
        y += 1
    if dir == UP:
        x -= 1
    if dir == DOWN:
        x += 1

    # Record movement of mouse
    record(x, y)

    # Draw mouse
    if TERMINAL:
        stdscr.addstr(x + 1, 2*(y + 1), ROBOT)
        stdscr.refresh()

    return x, y

책과는 달리 x와 y를 바꿔서 진행했습니다. TERMINAL 변수는 윈도우의 cmd창에서 진행할때는 '1'로, PyCharm에서 컴파일이나 기타 Debugging을 할때 '0'으로 설정했습니다.

Right hand on wall을 실제로 구현한 right_hand() 함수는 다음과 같습니다.

def right_hand(m, x, y, dir):
    if TERMINAL:
        stdscr.addstr(x + 1, 2*(y + 1), ROBOT)
        stdscr.refresh()
        time.sleep(0.1)

    # Record movement of mouse
    record(x, y)

    x, y = forward(x, y, dir)
    while still_in_maze(x, y):
        # 100 ms sleep
        time.sleep(0.1)
        dir = right(dir)
        while wall_ahead(m, x, y, dir):
            dir = left(dir)
        x, y = forward(x, y, dir)

    # End of record
    record(-1, -1)

최초 start point에 마우스를 그리고, 미로에 있는 동안 forward() 함수를 계속 호출합니다. 만약 벽을 만났다면(wall_ahead() 함수) 방향을 전환(left() 함수)합니다.

여기서 mouse를 그리거나 지울때 y 좌표를 그대로 사용하지 않고, 2를 곱해서 미로의 line이 지워지는 것을 최소화했습니다.

실행되는 코드를 사람이 확인할 수 있도록 time.sleep()을 사용했습니다. 여기서 sleep()의 인자로는 "초단위" 이외에 floating으로 msec 단위도 설정할 수 있습니다.^[각주:2]

3. 실행 코드

미로를 그리고 마우스가 right hand on wall 기법으로 미로를 빠져나가는 것을 볼 수 있는 코드는 아래 링크를 참고해 주십시오. ("C로 배우는 알고리즘" 리스트 3-3 : ROBOT.C의 일부) 아직 "최단 경초 찾기" 코드는 추가하지 않았습니다.

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_1_1.py

다음편에서 "최단 경로 찾기"까지를 포함해서 완성해 보겠습니다.

"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

1. 알고리즘

"C로 배우는 알고리즘"은다음과 같이 알고리즘을 표현합니다.

1. 정수 N을 입력받는다.

2. 정수 i에 2를 대입한다.

2.1 N이 i로 나누어 떨어지는가? (% 연산자를 사용)

2.1.1 나누어 떨어지면 소수가 아니다. 끝

2.2 i를 하나 증가시킨다.

2.3 i가 N보다 작은가?

2.3.1 작으면 2.1로 돌아간다.

3. 정수 N은 소수이다. 끝

2. 동작 코드

이를 코드를 작성하였습니다.

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

개선을 위해서 모든 숫자에 대해서 검사하지 않고, sqrt()를 이용해서 범위를 줄였습니다.

def is_prime2(n):
    sqrn = int(math.sqrt(n))
    for i in range(2, sqrn+1):
        if n % i == 0:
            return False
    return True

3. 실행 코드

실행 코드는 다음과 같이 작성했습니다. ("C로 배우는 알고리즘" 리스트 1-5 : PRIME2.C에 대응)

def print_results(i, n, r, t):
    if r:
        print('Test case', i, ":", n, "is prime in", t)
    else:
        print('Test case', i, ":", n, "is not prime in", t)


# Main function
LOOP = 10000

print("Test input number is prime or not")
print("Input 0 to end program")

while True:
    print()
    input_data = int(input("Input number to test -> "))

    if input_data < 0:
        print("Please input positive integer")

    if input_data == 0:
        print("End of program")
        break

    start_time = time.process_time()
    for i in range(0, LOOP):
        test_result = is_prime(input_data)
    end_time = time.process_time()
    print_results(1, input_data, test_result, end_time-start_time)

    start_time = time.process_time()
    for i in range(0, LOOP):
        test_result = is_prime2(input_data)
    end_time = time.process_time()
    print_results(2, input_data, test_result, end_time-start_time)

4. Tips

1. is_prime2()에서 for loop의 range에 +1을 사용해야 합니다.

5. 예제 코드

1. 알고리즘

최대공약수를 찾기 위해 유클리드 알고리즘을 사용합니다. "C로 배우는 알고리즘"에서 유클리드의 알고리즘을 말로 표현하면 다음과 같다고 합니다. (내용을 조금 바꿨습니다. 인터넷에서 찾은 링크를 참고해도 좋겠습니다.)

1. 두 정수 u와 v를 입력 받는다.

2. v가 u보다 크다면, v와 u의 값을 교환한다.

3. u-v를 u에 저장한다.

4. u가 0인가? 아니면 2로 돌아간다. u가 0이면 v가 최대 공약수이다.

2. 동작 코드

아래와 같이 Python으로 작성했습니다.

# Minus methods
def get_gcd(u, v):
    while u != 0:
        if u < v:
            t = u
            u = v
            v = t
        u = u - v
    return v

단순히 C를 Python으로 옮긴 것입니다.

뺄셈으로는 속도가 느려서, modulus 연산자를 이용해서 속도를 개선합니다.

# Modulus methods
def gcd_modulus(u, v):
    while v != 0:
        t = u % v
        u = v
        v = t
    return u

재귀호출을 이용한 코드는 아래와 같습니다.

# Recursion methods
def gcd_recursion(u, v):
    if v == 0:
        return u
    else:
        return gcd_recursion(v, u % v)

3. 실행 코드

두 수를 입력 받아서 위의 함수들을 호출하는 실행 코드는 다음과 같이 작성했습니다. ("C로 배우는 알고리즘" 리스트 1-3 : EUCLID2.C에 대응)

# Main function
LOOP = 10000

print("Input 0 to end program")

while True:
    print()
    first_input = int(input("Input first integer : "))
    second_input = int(input("Input second integer : "))

    if first_input < 0 or second_input < 0:
        print("Please input positive integer")

    if first_input == 0 or second_input == 0:
        print("End of program")
        break

    start_time = time.process_time()
    for i in range(0, LOOP):
        gcd = get_gcd(first_input, second_input)
    end_time = time.process_time()
    print("Minus methods : GCD of", first_input, "and", second_input, "is", gcd, "in", end_time-start_time)

    start_time = time.process_time()
    for i in range(0, LOOP):
        gcd = gcd_modulus(first_input, second_input)
    end_time = time.process_time()
    print("Modulus methods : GCD of", first_input, "and", second_input, "is", gcd, "in", end_time-start_time)

    start_time = time.process_time()
    for i in range(0, LOOP):
        gcd = gcd_recursion(first_input, second_input)
    end_time = time.process_time()
    print("Recursion methods : GCD of", first_input, "and", second_input, "is", gcd, "in", end_time-start_time)

4. Tips

1. Python에서 사용자에게 입력을 받기 위해서 input()을 사용했으며, input()은 'str'을 입력 받기 때문에 int()를 이용해서 integer로 변환했습니다.

2. 시간 측정을 위해서는 Python의 time 모듈에서 process_time()을 사용하였습니다.

5. 코드

책장 한 구석을 차지하고 있는 "C로 배우는 알고리즘" 을 보며 다시 한번 공부해 봐야지 생각만 계속하다, 어차피 새로 한다면 Python으로 코드를 작성해 보면 어떨까라는 생각을 했습니다. 아직 Python 초보자라 필요한 것들은 인터넷에서 찾아야 하고, 작성된 코드는 최적화되지도, 예쁘지도 않고, 많이 부족하겠지만 재미있을 것 같습니다. 대부분은 C 코드를 그대로 옮기는 것이 되겠지만 말입니다.

Python은 3.6.5를, IDE로는 Pycharm community version을 사용했습니다. 설치 방법은 인터넷에서 쉽게 찾을 수 있으니 따로 적지 않습니다.

기본적으로 "C로 배우는 알고리즘"를 그대로 따라할 예정입니다. 작성하면서 이용한 출처는 기본적으로 밝히는 것을 원칙으로 하겠지만, 혹시 실수가 있다면 알려 주십시오. 시작해 봅니다.