welcome!

하노이의 탑 하노이의 탑 이라는 문제는 일렬로 서있는 세 막대기 중 왼쪽 끝 막대기에 모든 원반들이 크기 순으로 꽂혀있고, 일정한 룰에 따라 그것을 전부 오른 쪽 끝 막대기로 이동하는 것을 묻는 문제이다. 아래는 하노이의 탑 사진 (wikipedia) 큰 원반이 항상 아래에 있어야 한다는 규칙을 준수하면서, 첫 번째 막대기에서 세 번째 막대기로 가는데에 가장 최단 수행 횟수가 존재할 거라 생각하는가? 만약 최단 수행이 존재한다면, 몇 번의 수행 만에 작업을 완료 할 수 있는가? 이에 대해 생각을 해볼 것이다. 하노이의 탑은 브라마의 탑이라고도 불리며 원래는 64개의 원반을 가지고 이동시키는 놀이로 부터 기원한다. 생각 step 1 처음부터 많은 수의 원반을 생각하지 말고 원반의 수를 줄여보자. 원반이 한..

시작하기에 앞서특정한 입력값 집합으로 이루어진 문제에 대한 정답은 같은 문제에 대한 작은 입력 값 집합에 대한 정답으로 축소할 수 있습니다. (이것은 부분 문제subproblem 이라는 꽤 중요한 표현입니다.)예를 들어, 두 양의 정수 a, b의 최대공약수(GCD)를 구하는 문제를 생각해보자. 여기서 b>a. 이 문제는 더 작은 입력값인 b mod a 와 a의 최대공약수를 구하는 문제로 축소될 수 있다. 왜냐하면 gcd(b mod a, a) = gcd(a, b)이기 때문이다.이런 문제 축소가 수행될 수 있다면, 원 문제의 정답은 이런 축소된 문제의 흐름(좀 더 엄밀하게는 축소된 문제의 나열sequence of reductions) 속에서 찾아 낼 수 있다. 계속 축소하다보면 정답을 정확하게 알 수 있는 ..