코딩딩딩

1. 하노이의 탑 소개 하노이의 탑은 한 기둥에 있는 원반들을 다른 기둥으로 전부 옮기는 방식을 따른다. 단, 아래의 규칙을 따라야 한다. 1) 가장 위에 있는 한 개의 원반 하나씩만 이동시킬 수 있다. 2) 작은 원반 위에 큰 원반을 놓을 수 없다. n개의 원반을 다른 기둥으로 모두 옮기는 횟수의 최소 값 공식은 아래와 같다. 2. 알고리즘 알고리즘 원리는 아래와 같다. 1) n개의 원반에 대해서 먼저 n - 1 개의 원반들(가장 큰 원반 제외)을 temp로 옮긴다. 2) n번째 원반(가장 큰 원반)을 destination으로 옮긴다. 3) temp에 있던 n - 1개의 원반들을 destination으로 옮긴다. 코드 구현은 아래와 같다. def TowerOfHanoi(n, source, destina..

1. 개념 포함-배제 원칙은 합집합의 원소의 개수를 구하는 것과 동일하다고 볼 수 있다. 집합 2개: |A∪B| = |A| + |B| - |A∩B| 집합 3개: |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C| 집합 4개: |A∪B∪C∪D | = |A| + |B| + |C| + |D| - |A∩B| - |A∩C| - |B∩C| - |A∩D| - |B ∩D| - |C∩D| + |A∩B∩C| + |A∩B∩D| + |A∩C∩D| + |B∩C∩D| - |A∩ B∩C∩D| 위의 공식에서 나타나듯이 집합의 개수를 늘려가면서 교집합 연산을 하는 것을 확인할 수 있다. 부호는 양수, 음수를 번갈아 가며 나타난다. 그러므로 집합 n개에 대하여 아래와 같은 공식이 ..