하노이탑은 첫번째 기둥에 있는 원판들을

몇가지 규칙을 지키며 마지막 기둥으로 옮겨야 한다.


규칙

한번에 한 원판만 이동 가능

자식보다 작은 원판 위로는 이동 불가능(위 < 아래)

상단에 원판이 있으면 이동 불가능








저작자표시 비영리

'알고리즘 > 기타 알고리즘' 카테고리의 다른 글

피보나치 수열(Fibonacci Numbers)  (0) 2017.02.08
최소 공배수(Least Common Multiple)  (0) 2017.02.07
최대 공약수(Greatest Common Divisor)  (0) 2017.02.07




피보나치 수열은 앞의 두 수를

더하며 나아가는 수열이다.


f(n)을 n번째 피보나치 수라고 한다면

f(n) = f(n-2) + f(n-1)

라는 식으로 표현가능하다.

※단, 피보나치 수열을 계산 하기 위해선, f(1) & f(2) (첫번째 & 두번째)는 주어져야 한다.


f(1) = 0

f(2) = 1

일때, 피보나치 수열은

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 84....

이 된다.





피보나치 수열의 대표적인 문제는 계단 문제다.


문제

계단을 한번에 1개 or 2개를 올라갈 수 있다.

n개의 계단을 올라 갈 수 있는 방법의 수는 몇 개인가?





해설

계단을 올라가는 방법은


계단을 마지막에 계단을 1개 올라가는 방법(주황색 선) 

계단을 마지막에 계단을 2개 올라가는 방법(파란색 선)

이 두 방식의 합이다.


f(n)방식으로 표현하면 아래와 같다.

f(n-1) : 마지막에 1개 올라가는 방법

f(n-2) : 마지막에 2개 올라가는 방법


즉, 

f(n) = f(n - 1) + f(n - 2)

(계단 n개를 올라가는 방법 = 마지막에 1개 올라가는 방법 + 마지막에 2개 올라가는 방법)


피보나치 수열이 성립한다는 것을 알 수 있다.


이제 f(1)과 f(2)만 구하면 된다.


계단 1개 : 1개(1개로 한번에)

계단 2개 : 2개(1개씩, 2개로 한번에)


계단 n개를 올라가는 방법은

1, 2, 3, 5, 8, 13, 21, 34, 55, 84....

이렇게 된다.



  • 재귀함수 이용



  • 반복문 이용


저작자표시 비영리

'알고리즘 > 기타 알고리즘' 카테고리의 다른 글

하노이탑 알고리즘(Tower of Hanoi Algorithm)  (0) 2017.02.12
최소 공배수(Least Common Multiple)  (0) 2017.02.07
최대 공약수(Greatest Common Divisor)  (0) 2017.02.07




최소 공배수란?


2개 이상의 수의 공배수 중 가장 작은 수


5의 배수 : 5, 10, 15, 20. 25, 30. 35, 40...

7의 배수 : 7, 14, 21, 27, 35, 42...


5와 7의 최소 공배수 = 35


식으로 나타내면

f(X, Y)는 정수 X와 Y의 최소 공배수

G는 정수 X와 Y의 최대 공약수

라고 할때


f(X, Y) = (X × Y) / G

이다



물론, 이러한 수학식을 몰라도

최소 공배수를 구할 수 있다.





하지만 최대 공약수와 위의 식을 활용하면

조금 더 효율적으로 최소 공배수를 구할 수 있다.


최대 공약수는 유클리드 호제법을 활용하면 쉽게 구할 수 있다.


최대 공약수 & 유클리드 호제법 보기(클릭)




저작자표시 비영리

'알고리즘 > 기타 알고리즘' 카테고리의 다른 글

하노이탑 알고리즘(Tower of Hanoi Algorithm)  (0) 2017.02.12
피보나치 수열(Fibonacci Numbers)  (0) 2017.02.08
최대 공약수(Greatest Common Divisor)  (0) 2017.02.07





최대 공약수란?

2개 이상의 수의 공약수 중 가장 큰 수


10의 약수 : 1, 2, 5, 10

15의 약수 : 1, 3, 5, 15


10과 15의 공약수 : 1, 5


10과 15의 최대 공약수 = 5



  • 수학 공식없이 반복문으로 찾는 방법



1부터 반복문으로 두 수 모두를 나눌 수 있는 수를 검색


반복은 입력된 수 중 작은 숫자까지만





  • 유클리드 호제법을 활용하여 찾는 방법


유클리드 호제법(Euclidean algorithm)


두 정수 혹은 두 다항식의 최대 공약수를 구하는 알고리즘

정수 : X, Y (X ≠ 0, Y ≠ 0, X > Y)
나머지 : Z (X를 Y로 나눴을때 나머지)
최대 공약수 : f(X, Y)

라고 하면

f(X, Y) = f(Y, Z)
라고 할 수 있다는 것이 유클리드 호제법이다.

공식으로 보면, 이해하기 어렵지만 숫자로 보면 쉽게 이해가 된다.

예를 들어
X = 1480, Y = 540 이라고 하자

1480 = 540 x 2 + 400
540 = 400 x 1 + 140
400 = 140 x 1 + 120
140 = 120 x 1 + 20
120 = 20 x 6 + 0

나머지가 0이 되는 20이 최대 공약수이다.

f(x, y)식으로 적어보면 이렇다.
f(1480, 540) = f(540, 400) = f(400, 140) = f(140, 120) = f(120, 20) = 20


-재귀함수 이용

-반복문 이용




저작자표시 비영리

'알고리즘 > 기타 알고리즘' 카테고리의 다른 글

하노이탑 알고리즘(Tower of Hanoi Algorithm)  (0) 2017.02.12
피보나치 수열(Fibonacci Numbers)  (0) 2017.02.08
최소 공배수(Least Common Multiple)  (0) 2017.02.07

+ Recent posts

티스토리툴바