문제
아래에서 설명하는 알고리즘 설계 기법은 무엇인가?
<보기>
- 어떤 문제를 해결하기 위해 그 문제를 더 작은 문제의 연장선으로 생각하는 방식이다.
- 작은 문제의 풀이를 활용하여 큰 문제의 풀이를 찾는 Bottom-Up 방식이다.
① 동적 계획법 ② 재귀적 알고리즘 ③ 근사 알고리즘 ④ 분할 정복법
정답
1번
해설
정답: 1. 작은 문제의 해를 저장하고 활용해 큰 문제를 해결하는 방식은 동적 계획법이다.
오답 풀이
- 1번: 동적 계획법은 부분 문제의 해를 이용해 전체 문제를 해결한다.
- 2번: 재귀적 알고리즘은 함수가 자기 자신을 호출하는 방식이다.
- 3번: 근사 알고리즘은 최적해 대신 근사해를 구하는 방식이다.
- 4번: 분할 정복법은 문제를 독립적인 작은 문제로 나누어 해결한다.
보충 개념 동적 계획법은 중복 부분 문제와 최적 부분 구조가 있을 때 효과적이다.