문제 04 팩토리얼 구하기

팩토리얼 : 1부터 n까지의 곱

1! = 1

2! = 1 * 2

n! = 1 * 2 * 3 .... (n - 1) * n

풀이

# 재귀를 이용한 방법
def factorial(n):
    if n < 2:
        return 1
    return factorial(n-1)*n

# 내가 좋아하는 메모이제이션
memo = {}
def factorial(n):
    if n < 2:
        return 1
    if n not in memo:
      memo[n] = factorial(n-1)*n
    return memo[n]

print(factorial(40))

# 그런거 다 필요없는 반복을 이용한 방법
def factorial(num):
    sum = 1
    for n in range(1, num+1):
        sum*=n
    return sum

재귀

마트료시카 인형을 생각하면된다. 인형안에 또 인형안에 또인형이 있는 형태고 더이상 열수 없을만큼 작아지면 멈춘다. 재귀도 멈추는 지점이 있어야한다.

재귀로 팩토리얼을 정의하면, n! = n * (n-1)!이 된다.

연습문제

• 1부터 n까지의 합을 구하는 재귀호출을 만들어 보세요.

def sum(n)
    if n == 1 or n == 0:
        return n
    return sum(n-1)+n

• 숫자 n개중 최댓값 찾기를 재귀호출로 만들어 보세요

def find(biggest,array):
    if len(array) < 1:
        return biggest

    new_num = array.pop(0)
    if biggest < new_num:
        biggest = new_num

    return find(biggest, array)

문제 05 최대공약수(GCD) 구하기

최대공약수(Greatest Common Divisor, GCD)는 두개 이상의 정수의 공통 약수 중에 가장 큰값을 의미한다.

최대공약수 알고리즘

1. 두 수중 더 작은 값을 i에 저장한다.
2. i가 두수의 공약수인지 확인한다.
3. 공약수이면 이 값을 반환한다.
4. 공약수가 아니면 i를 1만큼 감소시킨다. 그리고 2로 돌아간다.

def gcd(n1,n2):
    i = 0
    if n1 < n2:
        i = n1
    else:
        i = n2
    while(i):
        if (n1%i == 0) and (n2%i == 0):
            return i
        else:
            i -= 1

print(gcd(4,6))

유클리드 알고리즘

수학자 유클리드는 최대공약수에 다음과 같은 성질이 있다는것을 발견했다.

• a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다. 즉 gcd(a,b) = gcd(b,a%b)이다.
• 어떤수와 0의 최대공약수는 0이다. 즉 gcd(n,0) = 0이다.

def gcd(n1,n2):
  m = min(n1,n2)

  if n1%m == 0 and n2%m == 0:
    return m
  else:
    return gcd(m,n1%n2)

print(gcd(81,18)) # => 9


def gcd(n1,n2):
    if n2 == 0:
        return n1 # 약수중 가장큰약수
    return gcd(n2,n1%n2)
# 두번째 인자가 0인지 확인만 하면 되는거다. 0 으로 떨어지면 그게 약수라는 뜻이기 때문.

생각해보니 원래 최대공약수 구할때 100/40 -> 40/20 = 0 -> 20이구나 이런식으로 했던거 같긴하다.

수학을 아는게 진짜 도움되는듯...

문제 06 하노이의 탑 옮기기

원반이 n개인 하노이의 탑을 옮기기 위한 원반 이동 순서를 출력하는 알고리즘을 만들어 보세요.

(ㄷㄷ하노이의 탑..)

하노이의 탑을 옴길때는 세가지 제약사항이 있다.

• 원반은 한번에 한개씩만 옮길수 있고,
• 각 기둥 맨위의 원반은 다른 기둥의 맨위로만 움직여야하며,
• 옮기는 과정에서 큰원반은 작은 원반 위에 옮겨서는 안된다.

# h(1) => 1
# h(2) => h(1) + 1 + h(1)
# h(3) = h(2) + 1 + h(2)

def hanoi(n)
    if n == 1:
        return 1
    return hanoi(n-1) + 1 + hanoi(n-1)

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")

증명과정

2, 1,3,2

0 0 1

0 0 2

1 -> 2 (from => aux)

1 -> 3 (from => to)

2 -> 3 (aux -> to)

3, 1, 3, 2

0 0 0

0 1 0

0 2 3

1 -> 3 (from -> to)

1 -> 2 (from -> aux)

3 -> 2 (to -> aux)

to와 aux가 바뀐걸 눈치깜

1 -> 3 (from -> to)

2 -> 1 (aux -> from)

2 -> 3 (aux -> to)

1 -> 3 (from -> to)

aux와 from이 바뀐것을 눈치깜