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

1. 개요 & 알고리즘

간단한 텍스트뷰어를 이중 연결 리스트를 응용해서 작성해 봅니다. 이중 연결 리스트를 이용해서 텍스트 파일을 읽는 방법은 아래와 같습니다. ("C로 배우는 알고리즘"^[각주:1])

1. 파일을 연다.

2. 전체 라인 수를 0으로 초기화한다.

3. 파일의 끝에 도달할 때까지

3.1 파일에서 한 라인을 읽어서 buf에 저장한다.

3.2 buf에 저장된 문자의 길이가 80을 넘으면 자른다. (?)

3.3 새로운 노드를 생성하고 여기에 buf에 저장된 문자열을 복사한다.

3.4 새로 생성된 노드를 이중 연결 리스트의 제일 뒤에 삽입한다.

3.5 전체 라인 수를 증가시킨다.

3.6 3으로 돌아간다.

4. 파일을 닫고 끝낸다.

텍스트 파일을 보여 주는 동작은 PGUP, PGDN, ESC 키를 이용해서 동작합니다.

2. 동작 코드

텍스트 파일의 각 라인을 읽어서 double linked list를 구성하기 위한 기본적인 class는 다음과 같습니다.

class LineBufferNode:
    def __init__(self, line=""):
        self.line = line
        self.next = -1
        self.prev = -1

파일명을 인수로 받아서, 파일을 읽어서 double linked list를 구성하는 함수는 다음과 같습니다.

def load_file(self, file_name):
    fd = open(file_name, 'r')
    self.file_name = file_name
    self.total_line_num = 0

    print("File loading...")
    while (True):
        line_buffer = fd.readline()
        if not line_buffer:
            break

        new_line_buffer_node = LineBufferNode(line_buffer)
        new_line_buffer_node.prev = self.tail.prev
        new_line_buffer_node.next = self.tail
        self.tail.prev.next = new_line_buffer_node
        self.tail.prev = new_line_buffer_node

        self.total_line_num += 1

    fd.close()

파일에서 한 라인의 텍스트를 읽기 위해서 readline()함수를 사용했고, return 값이 없는 경우 EOF(End Of File)로 처리했습니다.^[각주:2], ^[각주:3]

Display하는 문자열을 반전하기 위해서 "curses.A_REVERSE"를 사용했습니다.

def show_header(self):
    string = " Text Viewer : " + self.file_name
    self.stdscr.addstr(0, 0, string, curses.A_REVERSE)
    self.stdscr.refresh()

하나의 페이지를 보이기 위해서 아래와 같은 함수를 작성했습니다. 윈도우의 command 창의 높이는 일정하지 않고 command 창을 변경하면 높이 값도 변경됩니다. 이에 command창의 라인수를 특정하지 않고 "try ... except"를 이용해서 error가 발생하기전까지는 계속 정상 출력하도록 했습니다.^[각주:4]

def show_page(self, line_node):
    # Clear screen
    self.stdscr.clear()
    # Show header
    self.show_header()

    line_num = 1
    # Can show total 29 lines (1 line for header and 28 lines for context
    while line_node != self.tail:
        try:
            self.stdscr.addstr(line_num, 0, line_node.line)
        except:
            break

        line_node = line_node.next
        line_num += 1

    self.stdscr.refresh()

    return line_num

키보드의 키 입력을 받아서 처리하도록 아래와 같이 작성했습니다. stdscr.getch()를 이용합니다. stdscr.getch()의 출력값은 integer입니다.print()를 이용해서 입력 받은 key 값을 출력하려면 chr(stdscr.getch()의 출력값)을 이용하면 됩니다.^[각주:5]

def key_proc(self):
    curses.noecho()
    self.stdscr.keypad(1)

    line_node = self.head.next
    line_num = self.show_page(line_node)

    while True:
        key = self.stdscr.getch()
        if key == curses.KEY_PPAGE: # Page Up
            line_node = self.move_line(-1*line_num, line_node)
            self.show_page(line_node)
        if key == curses.KEY_NPAGE: # Page Down
            line_node = self.move_line(line_num, line_node)
            self.show_page(line_node)
        if key == ord('q') or key == ord('Q'):
            break
        self.stdscr.refresh()

예를 들면 아래 코드를 사용해서 화면에 입력 받은 key를 출력할 수 있습니다.

self.stdscr.addstr(0, 0, chr(key))

3. 실행 코드

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

# main() function
if __name__ == "__main__":
    # Get file name to read
    file_name = input("Please input file name to load -> ")

    # Initialize TextFileViewer class
    text_viewer = TextFileViewer()
    # Read file
    text_viewer.load_file(file_name)
    # Handle key input
    text_viewer.key_proc()

4. 코드

1. 개요 & 알고리즘

단순 연결 리스트를 이용하면 작은 데이터베이스를 구축할 수 있습니다. 여기서는 데이터베이스까지는 아니지만 명함을 입력하고, 삭제하고, 검색하고, 리스팅하고, 디스크에 저장하고, 디스크에서 읽어들이는 등의 기능을 가진 간단한 프로그램을 작성해 봅니다. ("C로 배우는 알고리즘"^[각주:1]) - 프린트 출력 기능은 제외하였다.

1. 저장 필드로 이름, 회사, 전화번호만 갖는다.

2. 메뉴는 다음과 같다.

   2.1. 명합을 입력 받는다.

   2.2. 이름으로 찾아서 명함을 삭제한다

   2.3. 이름으로 명함을 검색한다.

   2.4. 디스크에서 명함을 읽는다.

   2.5. 디스크에 명함을 저장한다.

   2.6. 명함들의 리스트를 화면에 보여준다.

   2.7. 프로그램을 끝낸다.

2. 동작 코드

기본적인 Node의 정의는 다음과 같습니다.

class NameCardNode:
    def __init__(self, name, corp, tel):
        self.name = name
        self.corp = corp
        self.tel = tel
        self.next = -1

실제 함수들을 포함하는 NameCardList classs의 초기화는 다음과 같습니다.

class NameCardList:
    def __init__ (self):
        self.head = NameCardNode("", "", -1)
        self.tail = NameCardNode("", "", -1)
        self.head .next = self.tail
        self.tail.next = self.tail

inputCard(name, corp, tel), deleteCard(name), deleteNodeAll(), searchCard(name), printCard(), printCardAll()함수들도 작성했습니다.

노드들을 파일로 저장하는 함수는 다음과 같이 작성했습니다.

def saveCard(self, fileName):
    fd = open(fileName, 'wb')
    t = self.head.next
    while t != self.tail:
        # Use pickle to save "object" itself
        pickle.dump(t.name, fd)
        pickle.dump(t.corp, fd)
        pickle.dump(t.tel, fd)
        t = t.next
    fd.close()

파일로부터 노드를 다시 읽어오는 함수는 다음과 같이 작성했습니다.

def loadCard(self, fileName):
    try:
        fd = open(fileName, 'rb')
    except FileNotFoundError:
        print("Error : \"%s\" file can't be found" % fileName)
        return False

    while True:
        # Use pickle to load "object" itself
        try:
            name = pickle.load(fd)
            corp = pickle.load(fd)
            tel = pickle.load(fd)
            self.inputCard(name, corp, tel)
        except EOFError:
            break
    fd.close()
    return True

마지막으로, 간단한 CLI(Command Line Interface) 명령을 수행하기 위한 메뉴는 selectMenu()로 다음과 같이 작성했습니다.

def selectMenu():
    print("")
    print("Namecard Manager")
    print("-------------------------------------")
    print("1. Input  Namecard")
    print("2. Delete Namecard")
    print("3. Search Namecard")
    print("4. Load   Namecard")
    print("5. Save   Namecard")
    print("6. List   Namecard")
    print("7. End    Program")
    while(True):
        print("")
        # Try to handle only integer
        try:
            i = int(input("Select operation -> "), 10)
        except ValueError:
            pass
        else:
            if i > 0 and i < 8:
                break
    return i

3. 실행 코드

selectMenu() 함수를 호출해서 명령을 입력 받는 실행 코드는 아래와 같이 작성했습니다. ("C로 배우는 알고리즘" 리스트 3-7 : NAMECARD.C에 대응)

# main() function
if __name__ == "__main__":
    fileName = "Namecard.dat"
    # Initialize namecard class
    nameCard = NameCardList()
    while(True):
        menuNum = selectMenu()
        # End program
        if menuNum == 7:
            break

        # Input namecard
        if menuNum == 1:
            print("Input namecard menu : ")
            name = input("     Input name : ")
            corp = input("     Input corporation : ")
            tel = input("     Input telephone number : ")
            if name == "":
                print("Name in mandatory. Please input name.")
                continue
            else:
                nameCard.inputCard(name, corp, tel)

        # Delete namecard
        elif menuNum == 2:
            name = input("Input name to delete ->")
            results = nameCard.deleteCard(name)
            if results is None:
                print("Can't find that name.")

        # Search namecard
        elif menuNum == 3:
            name = input("Input name to search ->")
            results = nameCard.searchCard(name)
            if results is None:
                print("Can't find that name.")
            else:
                nameCard.printCard(results)

        # Load namecard
        elif menuNum == 4:
            if nameCard.loadCard(fileName) == True:
                print("Load namecard done!!")

        # Save namecard
        elif menuNum == 5:
            nameCard.saveCard(fileName)
            print("Save namecard done!!")

        # List namecard
        elif menuNum == 6:
            nameCard.printCardAll()

4. Tips

1. saveCard()를 사용해서 파일에 데이터를 저장하거나, loadCard()를 사용해서 파일에서 데이터를 로드할 때, Python이 제공하는 pickle 모듈을 사용했습니다. 위 예제에서와 같이 각각 pickle.dump()와 pickle.load()를 사용해서 매우 손쉽게 처리할 수 있었습니다.(^[각주:2]), (^[각주:3]), ()

2. 실제 코드를 보면,  try ~ else 형식의 예외 처리 방법^[각주:4]이 정리되어 있습니다. Integer로 입력을 받을 때등등에 예외 처리를 추가했습니다. 가장 기본적인것에 대해서, 시험을 하면서 발생한 경우에 대해서만 추가했습니다.

예를 들면, while() 내에서 데이터를 load 하는 pickle.load()를 계속 실행하는 경우, save된 데이터를 모두 읽고 나서 아래와 같은 에러가 발생했습니다. 이때 EOFError에 대해서 예외 처리 코드(try...except...)를 추가하면 동작했습니다.

    name = pickle.load(fd)
EOFError: Ran out of input

5. 코드

1. 개요 & 알고리즘

단순 연결 리스트와 달리 이중 연결 리스트는 다음 노드를 가리키는 링크와 이전 노드를 가리키는 링크 두 가지를 가져서 바로 이전 노드에 접근할 수 있다는 차이점이 있습니다. ("C로 배우는 알고리즘"^[각주:1])

2. 동작 코드

지금까지는 Class에서 Node에 대한 정보를 return하지 않고, Class 내부적으로만 처리하도록 하였으나, 이번에는 Node 정보를 Class 외부에서 입력 받거나 출력할 수 있도록 진행합니다.

Doubly Linked List는 링크로 next 이외에 prev를 갖게 됩니다.

class Node:
    def __init__(self, key=-1):
        self.key = key
        self.prev = None
        self.next = None

최초 Class 생성시, head와 tail 노드를 생성하고, 각각이 prev와 next로 가리키도록 합니다.

# Class for doubly linked list
class LinkedList:
    def __init__(self):
        self.head = Node(-1)
        self.tail = Node(-1)
        self.head.next = self.tail
        self.head.prev = self.head
        self.tail.next = self.tail
        self.tail.prev = self.head

List에 포함된 노드 t 앞에 key 값을 갖는 새로운 노드를 삽입하는 함수는 다음과 같습니다.

# Insert new node ahead of tNode
def insert_dnode_ptr(self, key, tNode):
    if tNode == self.head:
        return None
    iNode = Node(key)
    tNode.prev.next = iNode
    iNode.prev = tNode.prev
    tNode.prev = iNode
    iNode.next = tNode

특정 노드 t를 지우는 함수는 다음과 같습니다.

def delete_dnode_ptr(self, tNode):
    # Can't remove head and tail
    if tNode == self.head or tNode == self.tail:
        return 0
    tNode.prev.next = tNode.next
    tNode.next.prev = tNode.prev

    return tNode

특정 Key 값을 갖는 노드를 찾는 함수는 다음과 같습니다. Key 값을 갖는 노드를 찾지 못하면 "False"를 return 합니다.

def find_node(self, key):
    s = self.head.next
    while s.key != key and s != self.tail:
        s = s.next
    if s == self.tail:
        return False
    else:
        return s

3. 실행 코드

Doubly Linked List 관련 실행 코드는 다음과 같습니다. ("C로 배우는 알고리즘" 리스트 3-6 : LINKED2.C에 대응)

#main() function
if __name__ == "__main__":
    list = LinkedList()
    list.ordered_insert(10)
    list.ordered_insert(5)
    list.ordered_insert(8)
    list.ordered_insert(3)
    list.ordered_insert(1)
    list.ordered_insert(7)
    list.ordered_insert(8)

    print("Initial linked list is")
    list.print_all()

    print()
    findNumber = 4
    if list.find_node(findNumber) != False:
        print("Finding %d is successful" % findNumber)
    else:
        print("Finding %d is unsuccessful" % findNumber)

    print()
    findNumber = 5
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful" % findNumber)
    else:
        print("Finding %d is unsuccessful" % findNumber)

    print()
    print("Inserting 7 before 5")
    list.insert_dnode_ptr(7, t)
    list.print_all()

    print()
    findNumber = 3
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful and Deleting" % findNumber)
        list.delete_dnode_ptr(t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    findNumber = 10
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful" % findNumber)
        print("Inserting 2 before %d" % findNumber)
        list.insert_dnode_ptr(2, t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    findNumber = 2
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful and Deleting" % findNumber)
        list.delete_dnode_ptr(t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    findNumber = 1
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful and Deleting" % findNumber)
        list.delete_dnode_ptr(t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    print("Inserting 15 at last")
    list.insert_dnode_ptr(15, list.head.next)
    list.print_all()

    print()
    print("Delete all node")
    list.delete_all()
    list.print_all()

4. Tips

1. Python의 class는 특별히 public, private, protected등의 keyword를 제공하지 않으며, 일반적으로 class내에 선언된 변수들은 외부에서 access가 가능합니다^[각주:2]. 앞으로는 이를 그대로 사용하기로 합니다.

5. 코드

1. 개요 & 알고리즘

Circular linked list는 Simple linked list와 같은 노드 구조를 가지고 있지만, 제일 마지막 노드가 가장 처음의 노드를 가리키고 있다는 점이 다릅니다. 즉, Circular linked list에는 tail이라는 개념이 없습니다. ("C로 배우는 알고리즘"^[각주:1])

Circular linked list를 이용하는 문제는 "요셉의 문제"입니다. A에서 J까지 10명이 시계 방향으로 원모양을 만들어 순서대로 앉아 있다고 할 때, A부터 시작해서 4명 간격으로 사람을 그 원에서 뽑아낸다고 하면 그 순서는 어떻게 될까하는 문제입니다. 이 경우는 A, E, I, D, J, G, F, H, C, B의 순이됩니다.

2. 동작 코드

기본적인 코드는 Simple linked list와 거의 유사하지만, LinkedList class 초기화시 tail을 정의하지 않았습니다.

class LinkedList:
    def __init__(self, key):
        self.head = Node()
        self.head.key = key
        self.head.next = self.head

추가로 delete node 부분에서 header를 삭제하는 경우에 대해 보완을 했습니다.

def delete_node(self, key):
    p = self.head
    s = p.next
    # If we need to delete head
    if key == p.key:
        if s == self.head:
            return -1
        else:
            while True:
                if s.next == self.head:
                    s.next = self.head.next
                    self.head = s.next
                    return key
                else:
                    s = s.next
    # delete except head node
    while s.key != key and s != self.head:
        p = p.next
        s = p.next
    if s != self.head:
        p.next = s.next
        return key
    else:
        return -1

"요셉의 문제"도 LinkedList class내에서 수행하도록 했습니다.

def josephus(self, step):
    s = self.head
    while(True):
        print(s.key, "->", end=" ")
        self.delete_node(s.key)
        for i in range(step):
            s = s.next
        if s == self.head:
            print(s.key)
            break

3. 실행 코드

실행 코드는 LinkedList class를 정의하고, node를 입력 받은 수 만큼 생성한 후 "요셉의 문제"를 풀도록 하였습니다. ("C로 배우는 알고리즘" 리스트 3-5 : JOSEPH.C에 대응)

#main() function
if __name__ == "__main__":
    totalcount = int(input("Input total node's count : "))
    step = int(input("Input step for josephus's problem : "))

    list = LinkedList('A')
    # Already insert 'A' for header. So we only need to insert_node (totalcount-1)
    for i in range(totalcount-1):
        list.insert_node(chr(ord('B')+i))
    list.josephus(step)

4. Tips

1. LinkedList를 생성하면서 head node를 하나 생성하므로, 실제 insert_node()는 입력 받은 갯수-1만큼만 수행합니다.

5. 코드

1. 사전 지식

"C로 배우는 알고리즘"^[각주:1]에 설명된 Linked List에 대한 주요 내용은 다음과 같습니다.

1. Linked List는 Node와 Link로 구성됨

2. Linked List는 Link의 개수와 연결 상태에 따라 "단순 연결 리스트", "환형 연결 리스트", "이중 연결 리스트", "이중 환형 연결 리스트"등이 있음

2. Simple Linked List

• Simple Linked List는 "정보를 저장하는 Node"와 "바로 다음 Node를 가리키는 Link" 하나로 구성됩니다.
• Linked List의 최대 장점은 재배열(rearrangement)이 쉽다는 것입니다.
• 관리를 위해서 Head Node와 Tail Node를 가집니다.

2. 동작 코드

class Node:
    def __init__(self, key=-1):
        self.key = key
        self.next = None

Global로 head와 tail을 선언해서 작성해도 되겠지만, class 내에서 처리할 수 있도록 LinkedList라는 class를 작성했습니다. "C로 배우는 알고리즘"에 있듯이 head는 tail을, tail을 tail을 next로 지정하였습니다.

key 입력에 따라 정렬한 상태로 입력할 수 있도록 ordered_insert() 함수와 해당 key 값의 node를 지우고, 모든 node들을 print하는 함수를 작성하였습니다.

class LinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.next = self.tail

    def ordered_insert(self, key):
        newNode = Node(key)
        p = self.head
        s = p.next
        while s.key <= key and s != self.tail:
            p = p.next
            s = p.next
        p.next = newNode
        newNode.next = s

    def delete_node(self, key):
        p = self.head
        s = p.next
        while s.key != key and s != self.tail:
            p = p.next
            s = p.next
        if s != self.tail:
            p.next = s.next
            return True
        else:
            return False

    def print_node(self):
        p = self.head
        p = p.next
        print("Start", end=" ")
        while p != self.tail:
            print(p.key, "->", end=" ")
            p = p.next
        print("End")

3. 실행 코드

Simple Linked List 함수들의 실행 코드는 아래와 같습니다. ("C로 배우는 알고리즘" 리스트 3-4 : LINKED1.C에 대응)

ordered_insert() 함수로 임의의 integer type의 key값을 갖는 node들을 생성한 후 print합니다. 그리고 하나의 node를 그리고 다시 print합니다.

#main() function
if __name__ == "__main__":
    list = LinkedList()
    list.ordered_insert(7)
    list.ordered_insert(8)
    list.ordered_insert(1)
    list.ordered_insert(9)
    list.print_node()

    list.delete_node(7)
    list.print_node()

5. 코드

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