[Python] 알고리즘 개념5 퀴즈 - 동적 프로그래밍(DP)

 

 

✅ 퀴즈 1

다음 중 동적 프로그래밍(DP)의 핵심 개념이 아닌 것은?

1. 최적 부분 구조 (Optimal Substructure)
2. 중복되는 부분 문제 (Overlapping Subproblems)
3. 그리디 알고리즘 (Greedy Algorithm)
4. 메모이제이션 (Memoization)

---

 

✅ 퀴즈 2

다음 코드의 출력 결과는?

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(6))

1. 5
2. 8
3. 13
4. 21

---

 

✅ 퀴즈 3

동적 프로그래밍에서 "탑다운(Top-Down) 방식"이 의미하는 것은?

1. 반복문을 사용하여 문제를 해결하는 방식
2. 재귀 호출을 이용해 문제를 해결하고, 결과를 저장하여 중복 계산을 줄이는 방식
3. 가장 작은 부분 문제부터 해결하여 큰 문제를 해결하는 방식
4. 정렬된 데이터에서 탐색하는 방식

---

 

✅ 퀴즈 4

다음 중 동적 프로그래밍의 바텀업(Bottom-Up) 방식의 특징으로 옳은 것은?

1. 재귀 호출을 사용하여 문제를 해결한다.
2. 작은 문제를 해결한 후 그 값을 테이블에 저장하며, 점진적으로 큰 문제를 해결한다.
3. 이전에 계산된 값을 저장하지 않으며, 매번 다시 계산한다.
4. 정렬된 리스트에서 이진 탐색을 수행한다.

---

 

✅ 퀴즈 5

동적 프로그래밍(DP)을 사용할 수 없는 문제 유형은?

1. 부분 문제들이 서로 독립적인 경우
2. 최적 부분 구조를 갖는 문제
3. 중복되는 부분 문제가 존재하는 경우
4. 피보나치 수열과 같은 계층적인 문제

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔍 정답 및 해설

✅ 퀴즈 1 정답: 3번 (그리디 알고리즘은 DP의 핵심 개념이 아님)

💡 해설:

• 동적 프로그래밍의 핵심 개념은 **최적 부분 구조(Optimal Substructure)**와 **중복되는 부분 문제(Overlapping Subproblems)**입니다.
• **그리디 알고리즘(Greedy Algorithm)**은 각 단계에서 최선의 선택을 하는 방식으로, DP와 다르게 미래의 결과를 고려하지 않고 최적해를 구하려고 합니다.
• **메모이제이션(Memoization)**은 계산된 값을 저장하여 중복 계산을 방지하는 중요한 기법입니다.

---

 

✅ 퀴즈 2 정답: 2번 (8)

💡 해설:

• 주어진 피보나치 함수는 메모이제이션을 사용한 재귀 방식으로 구현되어 있습니다.
• fibonacci(6)의 계산 과정은 다음과 같습니다.
  • fibonacci(6) = fibonacci(5) + fibonacci(4)
  • fibonacci(5) = fibonacci(4) + fibonacci(3)
  • fibonacci(4) = fibonacci(3) + fibonacci(2)
  • fibonacci(3) = fibonacci(2) + fibonacci(1)
  • fibonacci(2) = fibonacci(1) + fibonacci(0)
  • fibonacci(1) = 1, fibonacci(0) = 0
• 이 계산을 거쳐 최종적으로 fibonacci(6) = 8이 됩니다.

---

 

✅ 퀴즈 3 정답: 2번 (탑다운 방식은 재귀 호출을 이용한 메모이제이션 기법)

💡 해설:

• **탑다운 방식(Top-Down)**은 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출하는 방식입니다.
• 재귀 호출 과정에서 이미 계산된 결과는 저장하여 중복 계산을 방지합니다.
• 반면, 바텀업(Bottom-Up) 방식은 작은 문제부터 차근차근 해결하며 테이블을 채워가는 방식입니다.

---

 

✅ 퀴즈 4 정답: 2번 (바텀업 방식은 작은 문제부터 차근차근 해결)

💡 해설:

• 바텀업 방식은 작은 문제를 먼저 해결하고, 그 결과를 테이블에 저장하며 점진적으로 더 큰 문제를 해결하는 방식입니다.
• 반복문을 활용하여 작은 값부터 차례로 값을 구해나가기 때문에 재귀 호출이 필요하지 않습니다.
• 대표적인 예로 피보나치 수열을 반복문으로 계산하는 방식이 있습니다.

---

 

✅ 퀴즈 5 정답: 1번 (부분 문제들이 서로 독립적인 경우)

💡 해설:

• 동적 프로그래밍을 사용하려면 중복되는 부분 문제가 존재해야 합니다.
• 만약 부분 문제들이 서로 독립적이라면, 이전 결과를 저장하고 재사용할 필요가 없으므로 그리디 알고리즘 또는 분할 정복 알고리즘을 사용하는 것이 더 적절할 수 있습니다.

➡ 동적 프로그래밍은 최적 부분 구조와 중복되는 부분 문제를 활용하는 기법입니다. 다양한 문제에 적용할 수 있으므로, 코드 구현 연습을 통해 이해를 깊이 다져보세요! 🚀

---