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만큼만 수행합니다.


2. Node의 key 값은 str type인데, for loop를 사용해서 integer 단위로 증가시키기 위해서는 변환이 필요[각주:2]합니다. 이때 ord()를 사용했습니다.

5. 코드


  1. http://www.yes24.com/24/goods/18003 [본문으로]
  2. https://stackoverflow.com/questions/704152/how-can-i-convert-a-character-to-a-integer-in-python-and-viceversa [본문으로]
반응형

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를 가집니다.
Python 배열은 그 자체로 append()나 remove()등을 제공합니다만, Python으로 Linked List를 구현한 웹문서들[각주:2],[각주:3],[각주:4],[각주:5]을 찾을 수 있었습니다. 이들 코드를 모두 참조하여 C로 배우는 알고리즘"에 있는 내용을 구현하였습니다.

Integer type의 key를 처리하는 class 구현을 목표로 하며, 구태여 Node 자체가 class 외부로 return되지는 않도록 설계합니다. 따라서 "C로 배우는 알고리즘"에 있는 insert_after(), delete_next(), find_node(), insert_node(), delete_all()는 구현하지 않고, delete_node(), ordered_insert(), print_list() 일부만 구현하는 것으로 합니다.

2. 동작 코드

Node는 class로 구현합니다. Node 생성시 Key 값이 입력되지 않으면 '-1'을 사용하도록 하였습니다. Key는 예제 목적상 integer를 입력 받는 것을 가정합니다.
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. http://www.yes24.com/24/goods/18003 [본문으로]
  2. https://wayhome25.github.io/cs/2017/04/17/cs-19/ [본문으로]
  3. http://onestep.tistory.com/33 [본문으로]
  4. http://sjce.tistory.com/8 [본문으로]
  5. http://doorbw.tistory.com/117 [본문으로]
반응형

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


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




  1. http://www.yes24.com/24/goods/18003 [본문으로]
  2. http://hashcode.co.kr/questions/1008/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8%EC%9D%84-50-ms-sleep%ED%95%98%EB%A0%A4%EB%A9%B4-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED%95%B4%EC%95%BC%EB%90%A0%EA%B9%8C%EC%9A%94 [본문으로]
반응형

"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. https://stackoverflow.com/questions/21330632/pythonic-alternative-of-gotoxy-c-code 참조 [본문으로]
  2. https://docs.python.org/3/howto/curses.html [본문으로]
  3. https://www.lfd.uci.edu/~gohlke/pythonlibs/#curses [본문으로]
  4. https://margaretsoftware.wordpress.com/2015/12/05/%EC%9C%88%EB%8F%84%EC%9A%B0-64-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EC%97%90%EC%84%9C-numpy-%EC%84%A4%EC%B9%98/ [본문으로]
  5. https://stackoverflow.com/questions/16740385/python-curses-redirection-is-not-supported [본문으로]
반응형

1. 알고리즘

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


2. 동작 코드

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

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

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


 벽배치의 고유값

벽의 배치 

벽의 모양 

벽모양의 ASCII 코드 

 0

 벽없음, 공간

 

 32

 1

 UP

 179

 2

 RIGHT

 196

 3

 UP | RIGHT

 192

 4

 DOWN

 179

 5

 UP | DOWN

 179

 6

 RIGHT | DOWN

 218

 7

 UP | RIGHT | DOWN

 195

 8

 LEFT

 196

 9

 UP | LEFT

 217

 10

 RIGHT | LEFT

 196

 11

 UP | RIGHT | LEFT

 193

 12

 DOWN | LEFT

 191

 13

 UP | DOWN | LEFT

 180

 14

 RIGHT | DOWN | LEFT

 194

 15

 UP | RIGHT | DOWN | LEFT

 197


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

기본적으로 Python으로 Extended ASCII 문자를 표현하기 어려우므로, Unicode를 이용해서 표현했습니다.

그림을 그리기 위한 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. http://www.yes24.com/24/goods/18003 [본문으로]
  2. http://steadyandslow.tistory.com/99 [본문으로]
반응형

1. 알고리즘

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


2. 실행 코드

최대 9999까지 소수를 모두 출력하도록 합니다. 소수를 구하고, 해당 소수의 배수에 해당하는 숫자들을 지워야 하는데, 해당 숫자에 해당하는 배열의 값을 '1'로 변경해서 소수가 아니라는 것을 표시하였습니다.

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

Python2에서는 print문에 ','를 붙여서 서로 다른 라인에서 실행하는 print문을 한줄에 표시할 수 없습니다. 그런데 Python3에서는 이 방법이 동작하지 않습니다. 그래서 'end=" "'를 print문에 추가하여, 한줄에 결과를 출력하도록 하였습니다.

5. 코드


반응형

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

반응형

+ Recent posts