동적 계획법(dynamic programming)에 대한 설명으로 옳지… | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 26년 1회차
동적 계획법(dynamic programming)에 대한 설명으로 옳지 않은 것은?
1
부분 문제들 사이에는 의존적 관계가 없다.
2
동일한 부분 문제들을 다시 풀지 않도록 하기 위해 부분 문제들의 해를 저장한다.
3
주어진 문제를 작은 문제로 나누어 해결하고 이를 이용하여 원래 문제의 해를 도출한다.
4
이 기법을 적용할 수 있으려면 최적성의 원리(principle of optimality)가 성립하여야 한다.
해설
동적 계획법에서 부분 문제들 사이에 의존 관계가 없다는 설명은 옳지 않다.
동적 계획법은 큰 문제의 해가 작은 부분 문제의 해에 의존하고, 같은 부분 문제가 반복해서 나타나는(중복 부분 문제) 상황에 쓰인다. 부분 문제들이 서로 독립적인 것은 분할 정복의 특징이다.
- 부분 문제의 해를 테이블에 저장해 다시 풀지 않는 것은 동적 계획법의 핵심이다.
- 문제를 작은 문제로 나누어 풀고 그 해로 원래 문제의 해를 구하는 것은 옳은 설명이다.
- 최적의 해가 부분 문제의 최적해로 구성된다는 최적성의 원리가 성립해야 적용할 수 있다.
오류나 개정된 내용이 보이면 알려주세요