Study Blog

하노이의 탑이란? - 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키며 기둥 3개를 이용해서 원반을 옮김. 하노이의 탑 조건 (1) 크기가 모두 다른 원반이 첫 번째 기둥에 쌓여 있는 상태로 시작(작은 원반이 위에, 큰 원반이 아래에 위치) (2) 이 상태에서 모든 원반을 세 번째 기둥에 최소 횟수로 옮김 (3) 원반은 1개씩 옮길 수 있으며, 큰 원반은 작은 원반 위에 쌓을 수 없음 그룹으로 묶어서 옮기기 - 원반이 3개일 때 - 원반이 2개일 때 - 원반이 4개일 때 원반을 옮기는 과정을 코드로 구현 def move(no: int, x: int, y: int) -> None: # 원반 no개를 x기둥에서 y기둥으로 옮김 if no > 1: move(no - 1, x, 6 - x - y) p..

순수한 재귀란? - 재귀 호출을 여러 번 실행하는 함수 def recur(n: int) -> int: if n > 0: recur(n - 1) print(n) recur(n - 2) x = int(input("정숫값을 입력하세요.: ")) recur(x) 실행 결과 정숫값을 입력하세요.: 4 1 2 3 1 4 1 2 - 순수한 재귀는 위와 같이 실행 과정이 복잡. 매개변수를 4가 아닌 3이나 5라면 어떤 결과를 출력할 지 간단히는 알 수 없음. 하향식 분석과 상향식 분석 위 코드를 하향식 분석(Top-down)방법과 상향식 분석(Bottom-up)방법으로 분석해보자. recur(4)의 실행 과정은 다음과 같다. 1. recur(3)을 실행한다. 2. 4를 출력한다. 3. recur(2)를 실행한다. 위 ..

재귀란? - 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우에 재귀라고 한다. - 재귀를 효과적으로 사용하면 이러한 정의뿐만 아니라 프로그램을 간결하고 효율성 좋게 작성할 수 있다. 팩토리얼이란? - 양의 정수를 순서대로 곱한다는 의미로 순차 곱셈이라고도 한다. - 10!(10의 팩토리얼)은 10 X 9!로 구할 수 있고, 다시 9!은 9 X 8!로 구할 수 있다. # 양의 정수 n의 팩토리얼 구하기 def factorial(n: int) -> int: # 양의 정수 n의 팩토리얼 값을 재귀적으로 구함 if n > 0: return n * factorial(n-1) else: return 1 if __name__ == "__main__": n = int(input("출력할 팩토리얼 값을 입..