[Python Algorism] 5. 재귀 알고리즘
DO IT 자료구조와 함께 배우는 알고리즘 입문 파이썬책을 공부하는 취준생으로써 해당 책의 공부 내용을 정리하고
다른 입문자들이 쉽게 이해 하도록 공유하고자 만든 페이지입니다. 모든 문제의 저작권은 관련 저작자에게 있으며 문제가 됐을 시 삭제하겠습니다. 감사합니다
Chap5. 재귀알고리즘
재귀 : 자기 자신을 포함하고 자기 자신을 사용하여 정의되는 경우
직접재귀 : factorial() 함수는 내부에서 자신과 똑같은 함수 호출. 자신과 똑같은 함수를 호출하는 함수
간접 재귀 : a() 함수가 b()함수를 호출하고 다시 b() 함수가 a() 함수를 홏ㄹ하는 구조
P186: n의 팩토리얼 구하기
math() import 해서 fatcorial 함수 쓰기
P190 : 유클리드 호재법 최대 공약수 구하기
두 수 input 으로 받고 두 수를 나눈 나머지랑 계속 비교해서 구하면 됨
P192: 재귀 알고리즘 _ 하향식/상향식
재귀 알고리즘 중에서 하향식 방법을 통해서 구하는 것.
하향식 알고리즘을 조금 이해하기 위해서 N=3으로 두어서 조금 간단하게 생각했다
그림이 좀 엉망진창이지만 그려보면 이해가 잘 된다. 정수가 나올 때까지 최대한 반복을 하고 0이하는 다 지워버리면
밑에서부터 올라오는 식으로 계산하면 1231 이 나오는 것을 이해할 수 있습니당
상향식은 그러면 어떻게 될까요? 반대로 아래쪽부터 쌓아올리면 됩니다
P196 비재귀적 표현
recur() 함수의 맨 끝에서 재귀 호출하는 꼬리 n-2로 업데이트하고 함수 시작 지점으로 돌아감.
*위에 값과 다른 이유는 출력값을 다르게 설정했기 때문입니다.
P197 스택으로 재귀 함수 구현하기
4강에서 했던 stack.pt를 불러온다. 값을 push하고 pop하기
P200 하노이의 탑
하노이의 탑은 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용하여 원반을 옮기는 문제
하노이의 탑 문제를 구현하면서 혼자 못풀었는데 왜 6-x-y이걸 왜 하는지 이해가 안되었다. 이 문제는 기둥이 3개일 때만 가정하는 건데 기둥 번호의 합을 6이라고 둔 것이다. 각 기둥은 1, 2, 3으로 번호가 매겨져 있고, 1 + 2 + 3 = 6입니다.
따라서 6-x-y는 출발 기둥(x)과 도착 기둥(y)을 제외한 나머지 기둥을 나타내기 위한 것으로 표현해야 한다.
P204: 8퀸 문제
* 각 열에 퀸을 1개 배치하는 조합을 재귀적으로 나열하기
너무 많아서 중간에 스톱하였다. pos를 통해 퀸의 배치를 나타내고 몇행몇열에 배치할지 계산하면 됨.
각 열에 배치했는지 / 대각선 방향으로 배치했는지 체크하면서 퀸을 설정하면 된다.
우선 이 문제는
1) -> 포인터 잡는 게 어려웠다 / 아직 이해는 됐지맘 적응하는 게 항상 어렵다
2) if문 이후 퀸을 모든 열에 배치 할 때 말고 다음 열에 어떻게 하는지 재귀를 적용하는 게 햇갈렸다