<모두의 알고리즘 with 파이썬> 문제풀이 (6~11)

하노이탑 쌓기

def hanoi(n, from_pos, to_pos, aux_pos):
  if n == 1:
    print(from_pos, "->", to_pos)
    return
  
  hanoi(n-1, from_pos, aux_pos, to_pos)
  print(from_pos, "->", to_pos)
  hanoi(n-1, aux_pos, to_pos, from_pos)

hanoi(3, 1, 3, 2)

재귀 호출을 이용한 그림 그리기

* 종료 조건, 자기 복제 과정

import turtle as t

def spiral(sp_len):
  if sp_len <= 5:
    return
  t.forward(sp_len)
  t.right(90)
  spiral(sp_len - 5)

t.speed(0)
spiral(200)
t.hideturtle()
t.done()

import turtle as t

def tri(tri_len):
  if tri_len <= 10:
    for i in range(0, 3):
      t.forward(tri_len)
      t.left(120)
    return
  new_len = tri_len / 2
  tri(new_len)
  t.forward(new_len)
  tri(new_len)
  t.backward(new_len)
  t.left(60)
  t.forward(new_len)
  t.right(60)
  tri(new_len)
  t.left(60)
  t.backward(new_len)
  t.right(60)

t.speed(0)
tri(160)
t.hideturtle()
t.done()

import turtle as t

def tree(br_len):
  if br_len <= 5:
    return
  new_len = br_len * 0.7
  t.forward(br_len)
  t.right(20)
  tree(new_len)
  t.left(40)
  tree(new_len)
  t.right(20)
  t.backward(br_len)

t.speed(0)
t.left(90)
tree(70)
t.hideturtle()
t.done()

import turtle as t

def snow_line(snow_len):
  if snow_len <= 10:
    t.forward(snow_len)
    return
  new_len = snow_len / 3
  snow_line(new_len)
  t.left(60)
  snow_line(new_len)
  t.right(120)
  snow_line(new_len)
  t.left(60)
  snow_line(new_len)

t.speed(0)
snow_line(150)
t.right(120)
snow_line(150)
t.right(120)
snow_line(150)
t.hideturtle()
t.done()

순차 탐색

def search_list(a, x):
  n = len(a)
  for i in range(0, n):
    if x == a[i]:
      return i

  return -1

v = [18, 22, 1, 10, 5]
print(search_list(v, 18))

예제 1. 

def search_list(a, x):
  n = len(a)
  b = []
  for i in range(0, n):
    if x == a[i]:
      b.append(i)

  return b

v = [18, 22, 1, 10, 5, 18]
print(search_list(v, 18))

예제 2. 

def search_list(a, b, c):
  n = len(a)
  for i in range(0, n):
    if a[i] == c:
      return b[i]

  return "?"

v = [1, 2, 3, 4, 5]
m = ["a", "b", "c", "d", "e"]
print(search_list(v, m, 1))

선택 정렬

쉽게 설명한 선택 정렬 알고리즘

#a에서 최솟값의 위치를 찾는다. 
def find_min_idx(a):
  n = len(a)
  min_idx = 0
  for i in range(1, n):
    if a[i] < a[min_idx]:
      min_idx = i
  return min_idx

#a에서 최솟값을 하나씩 빼서 result에 넣는다. 
def sel_sort(a):
  result = []
  while a:
    min_idx = find_min_idx(a)
    value = a.pop(min_idx)
    result.append(value)
  return result

일반적인 선택 정렬 알고리즘

def sel_sort(a):
  n = len(a)
  for i in range(0, n-1):
    min_idx = i
    for j in range(i+1, n):
      if a[j] < a[min_idx]:
        min_idx = j
    a[i], a[min_idx] = a[min_idx], a[i]

a = [1, 3, 100, 50, 7]
sel_sort(a)
print(a)

삽입 정렬

쉽게 설명한 삽입 정렬 알고리즘

def find_ins_idx(r, v):
  for i in range(0, len(r)):
    if v < r[i]:
      return i
  return len(r)

def ins_sort(a):
  result = []
  while a:
    value = a.pop(0)
    ins_idx = find_ins_idx(result, value)
    result.insert(ins_idx, value)
  return result

d = [2, 4, 5, 1, 3]
print(ins_sort(d))

일반적인 삽입 정렬 알고리즘

def ins_sort(a):
  n = len(a)
  for i in range(1, n):
    key = a[i]
    j = i -1
    while j >= 0 and a[j] > key:
      a[j + 1] = a[j]
      j -= 1
    a[j +1] = key

d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)