🌓 알고리듬, 하노이탑

💫 하노이탑

---

재귀적인/순환적인 풀이로도 유명하지만,
분할 정복으로 풀 수 있다

규칙
→ 원판은 한 번에 맨 위에 있는 한 개씩 옮겨야
→ 작은 원판 위에 큰 원판을 올려놓을 수 없음

부문제가 문제 크기 1만큼만 줄어들기 때문에
시원하게 분할 정복이다 ! 말하기는 내키지 않지만
무튼 조금씩 분할하는 분할 정복이다

분할정복 알고리즘 부문제의 정복은 순환호출에 의존 부문제는 해결되었다고 보고 부문제를 어떻게 풀지 고민하지 않음  순환적 사고의 장점이고 분할정복 알고리즘이 갖는 외형적 단순함의 근원 효율성 문제를 보완하려면 (시스템) 스택의 순환 구조를 (명시적) 스택의 반복 구조로 변환

분할정복 기법을 사용하면 좋지 않은 경우? ➊ 부문제의 크기가 커지는 경우 현실적으로 없는 ➋ 두 개 이상의 부문제로 나누어지지만, 부문제의 크기가 거의 변하지 않는 경우 피보나치 수열 계산 알고리즘: 두 개의 부문제로 나누어지지만, 각 부문제의 크기는 n-1과 n-2 문제 특성상 O(2n)의 복잡도를 갖는다면 분할정복 기법을 배제할 필요는 없음(하노이탑) ➌ 동일한 부문제들이 자주 등장하는 경우 (중첩,재활용) 분할정복은 모든 부문제들을 독립적으로 해결: 부문제들이 중첩되는 경우 비효율적 피보나치 수열 문제는 부문제의 크기도 조금씩 줄어들고 동일한 부문제들도 자주 등장 상대적으로 높은 복잡도의 가능성이 있는 문제들의 유형 부문제의 크기가 줄어들지만 부문제의 크기를 모두 합하면 문제의 크기보다 커지는 경우 상대적으로 낮은 로그형이나 선형의 복잡도를 가질 수 없음 체스판 채우기 알고리즘: 부문제가 4개 이고 부문제의 크기의 합이 원래 문제 크기의 2배