728x90
1. 재귀 알고리즘
나 자신을 다시 호출하는 것을 재귀라고 한다. 반복문을 사용할 수 있지만 재귀함수를 사용하는 방법이 더 간결하다.
*를 사용해 tree를 만드는 코드를 재귀 함수를 통해 만들면 아래와 같다.
def recusion(num):
if num>0:
print('*'*num)
return recusion(num-1)
else:
return 1
recusion(10)
2. 재귀 알고리즘을 이용한 최대 공약수 계산
유클리드 호제법을 사용해 계산할 수 있다.
더보기
유클리드 호제법
두 자연수 n1, n2에 대하여 (n1 > n2) n1를 n2로 나눈 나머지를 r이라고 할 때,
n1과 n2의 최대공약수는 n2와 r의 최대공약수와 같다
42와 24의 최대공약수의 경우 n1=42를 n2=24로 나눈 나머지 r=18이라고 할 때,
42와 24의 최대공약수는 24와 18의 최대공약수와 같다
#최대공약수(greatest common devide)
def gcd(n1, n2):
if n1 % n2 == 0:
return n2
else:
r = n1 % n2
return gcd(n2, r)
print(f'gcd(82, 32): {gcd(82,32)}')
print(f'gcd(96, 40): {gcd(96,40)}')
3. 하노이의 탑
퍼즐게임의 일종으로 3개의 기둥을 이용해 원판을 다른 기둥으로 옮기면 되고, 제약 조건은 다음과 같다
- 한 번에 한 개의 원판만 옮길 수 있다.
- 큰 원판이 작은 원판 위에 있어서는 안 된다.
#원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
def moveDisc(discCnt, fromBar, toBar, viaBar):
if discCnt == 1:
print(f'1:{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동')
else:
#(discNo - 1)개들을 경유 기둥으로 이동
moveDisc(discCnt-1, fromBar, viaBar, toBar)
#discNo를 목적 기둥으로 이동
print(f'2:{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동')
#(discNo-1)개들을 도착기둥으로 이동
moveDisc(discCnt-1, viaBar, toBar, fromBar)
moveDisc(3, 1, 3, 2)
결과 출력
1:1disc를 1에서 3(으)로 이동
2:2disc를 1에서 2(으)로 이동
1:1disc를 3에서 2(으)로 이동
2:3disc를 1에서 3(으)로 이동
1:1disc를 2에서 1(으)로 이동
2:2disc를 2에서 3(으)로 이동
1:1disc를 1에서 3(으)로 이동
728x90
'코딩 > 알고리즘' 카테고리의 다른 글
[정렬] 병합정렬, 퀵정렬 (0) | 2023.02.09 |
---|---|
[비교] 최빈값, 근삿값, 평균 알고리즘 (0) | 2023.02.08 |
[비교] 최댓값, 최솟값 알고리즘 (0) | 2023.02.06 |
[정렬] 선택정렬 알고리즘 (0) | 2023.01.31 |
[정렬] 삽입정렬 알고리즘 (0) | 2023.01.31 |