문제 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)는 두개 이상의 정수의 공통 약수 중에 가장 큰값을 의미한다.
최대공약수 알고리즘
- 두 수중 더 작은 값을 i에 저장한다.
- i가 두수의 공약수인지 확인한다.
- 공약수이면 이 값을 반환한다.
- 공약수가 아니면 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이 바뀐것을 눈치깜