11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 분석 1) 재귀 원반이 두 개 이상이면 원반의 개수를 n 이라 할 때, 가장 아래에 있는 원반 n을 도착 기둥에 옮기기 위해 그 위에 놓여 있는 n-1개의 원반을 보조 기둥에 옮긴다. 원반 n을 도착 기둥에 옮긴다. 보조 기둥에 있는 n-1개의 원반을 도착 기둥에 옮긴다. 2) 점화식 먼저 "수열 An​= n개의 원판을 이동하는 횟수" 라고 정의하자. n개의 원판을 이동시키기 위해서는 그 위의 n-1개의 원판을 다른 막대로 이동하고 맨 아래쪽 원판을 ..

1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 분석 숫자를 덧붙이는 방법으로 한자리, 두자리, 세자리,... 의 감소하는 수 리스트 생성 재귀 n = int(input()) nums = [] def add(idx, num): # 자리수에 따라 증가 if idx == 1: nums.append(num) else: for i in range(num % 10): # 앞자리보다 작은 숫자들만 이어붙이기 add(idx-1, num*10 + i) for i in range(1, 11): for j in ..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 분석 트리 순회(전위 순회, 중위 순회, 후위 순회), DFS 1. 전위순회 뿌리(root)를 먼저 방문 #전위순회 출력 : 1 2 4 5 3 6 7 def preorder(v): if v > 7: return else: print(v, end=' ') preorder(v * 2) preorder(v * 2 + 1) preorder(1) 2. 중위 순회 왼쪽 하위 트리를 방문 후 뿌리(root)를 karla.tistory.com 풀이 import sy..

10829번: 이진수 변환 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000,000,000,000) www.acmicpc.net 풀이 n=int(input()) def DFS(x): if x == 0: return else: DFS(x//2) print(x%2, end='') DFS(n)

1. 전위순회 뿌리(root)를 먼저 방문 #전위순회 출력 : 1 2 4 5 3 6 7 def preorder(v): if v > 7: return else: print(v, end=' ') preorder(v * 2) preorder(v * 2 + 1) preorder(1) 2. 중위 순회 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문 # 중위순회 출력 : 4 2 5 1 6 3 7 def inorder(v): if v > 7: return else: inorder(v * 2) print(v, end=' ') inorder(v * 2 + 1) inorder(1) 3. 후위 순회 하위 트리 모두 방문 후 뿌리(root)를 방문 #후위순회 출력 : 4 5 2 6 7 3 1 def postorder(v):..