다음 하노이 탑 문제를 해결하는 파이썬(Python) 코드의 시간 복잡… | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 23년 1회차

다음 하노이 탑 문제를 해결하는 파이썬(Python) 코드의 시간 복잡도는? (단, n은 원판의 개수이고 first, second, third는 기둥 번호이다)def hanoiT(n, first, second, third):
  if n == 1:
    print("원판1 : %s 에서 %s"%(first, third))
  else:
    hanoiT(n - 1, first, third, second)
    print("원판%d : %s 에서 %s"%(n, first, third))
    hanoiT(n - 1, second, first, third)

 $O(n)$

 $O(n^2)$

 $O(2^n)$

 $O(\log_2 n)$

해설

하노이 탑 재귀 코드의 시간 복잡도는  $O(2^n)$ 이다.
원판 n개를 옮기려면 n−1개 이동을 두 차례 재귀 호출하고 원판 하나를 옮기므로  $T(n) = 2T(n-1) + 1$ ,  $T(1) = 1$ 이다. 이를 풀면  $T(n) = 2^n - 1$ 로, 원판이 하나 늘 때마다 작업량이 두 배가 된다.
 $O(n)$ : 재귀 호출이 한 갈래뿐인  $T(n) = T(n-1) + 1$ 의 결과다.
 $O(n^2)$ : 한 갈래 재귀에서 호출마다 선형 작업을 할 때의 결과로, 두 갈래로 갈라지는 이 코드보다 훨씬 작다.
 $O(\log_2 n)$ : 문제 크기가 절반씩 줄 때의 결과인데, 여기서는 1씩 줄면서 호출이 두 배로 늘어난다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 23년 1회차 25문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요

비슷한 기출

7급 국가직 자료구조론 기출문제 암기장 전체 보기

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→