[Python] 알고리즘 개념4 퀴즈 - 재귀와 백트래킹

 

 

📌 퀴즈 개요

이 퀴즈는 "재귀와 백트래킹" 개념을 이해하고 있는지 확인하기 위한 문제들로 구성되어 있습니다. 각 문제의 답을 선택하거나 직접 작성해보세요!

---

 

 

🧩 1. 개념 이해 문제

 

❓ 문제 1

재귀 함수가 반드시 가져야 하는 요소는?

1. 반복문
2. 종료 조건
3. 글로벌 변수
4. 정렬된 입력 데이터

 

❓ 문제 2

다음 코드의 실행 결과는?

def func(n):
    if n == 0:
        return 1
    return n * func(n - 1)

print(func(3))

1. 6
2. 9
3. 3
4. 1

---

 

 

🧩 2. 실전 문제

 

❓ 문제 3

다음 코드에서 fibonacci(n) 함수의 시간복잡도는?

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

1. O(n)
2. O(n log n)
3. O(2^n)
4. O(1)

 

❓ 문제 4

백트래킹 기법을 사용하면 탐색 과정에서 어떤 최적화가 가능한가?

1. 중복된 계산을 줄일 수 있다.
2. 탐색 범위를 무조건 절반으로 줄일 수 있다.
3. 모든 경우를 반드시 탐색해야 한다.
4. 정렬된 데이터에서만 사용할 수 있다.

 

❓ 문제 5

다음 코드에서 백트래킹을 사용하는 주요 이유는?

def solve_n_queens(board, row, n):
    if row == n:
        print(board)
        return
    for col in range(n):
        if is_safe(board, row, col, n):
            board[row] = col
            solve_n_queens(board, row + 1, n)
            board[row] = -1

1. 모든 가능한 경우를 검사하기 위해
2. 유망하지 않은 경우를 미리 제거하기 위해
3. 탐색 속도를 느리게 하기 위해
4. 모든 해결책을 찾지 못하도록 제한하기 위해

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🏆 정답 및 해설

✅ 문제 1 정답: 2)

• 재귀 함수는 반드시 종료 조건(Base Case)이 있어야 무한 루프를 방지할 수 있습니다.

✅ 문제 2 정답: 1)

func(3) = 3 * func(2)
func(2) = 2 * func(1)
func(1) = 1 * func(0)
func(0) = 1
# 결과: 3 * 2 * 1 * 1 = 6

✅ 문제 3 정답: 3)

• 피보나치 수열의 재귀 구현은 중복 계산이 많아 O(2^n) 시간복잡도를 가집니다.

✅ 문제 4 정답: 1)

• 백트래킹을 사용하면 유망하지 않은 경우를 조기에 제거하여 중복된 계산을 줄일 수 있습니다.

✅ 문제 5 정답: 2)

• N-Queen 문제에서 백트래킹은 유망하지 않은 경우를 빠르게 배제하여 탐색 시간을 줄이는 데 사용됩니다.

---