다음 설명에 해당하는 알고리즘은?○ 문제의 입력 사례 분할 후, 분할된… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 23년 1회차
다음 설명에 해당하는 알고리즘은?○ 문제의 입력 사례 분할 후, 분할된 문제의 해답을 우선 구한다.
○ 문제의 입력 사례를 분할할 때, 재귀 관계식을 사용할 수 있다.
○ 분할된 문제의 해답을 저장하여 분할 전 문제의 해답을 구하는 상향식 방법이다.
1
브루트포스(bruteforce)
2
백 트랙킹(backtracking)
3
분기 한정법(branch-and-bound)
4
동적 프로그래밍(dynamic programming)
해설
설명은 동적 프로그래밍에 해당한다.
재귀 관계식으로 문제를 작은 부분 문제로 나누고, 작은 문제의 해답을 표에 저장해 두었다가 큰 문제의 해답을 구하는 상향식(bottom-up) 방법이 동적 프로그래밍의 특징이다.
- 브루트포스는 가능한 모든 경우를 전부 시도하는 방법으로, 부분 문제의 해답을 저장해 재사용하지 않는다.
- 백트래킹은 상태 공간 트리를 깊이 우선으로 탐색하다 유망하지 않으면 되돌아가는 방법이다.
- 분기 한정법은 한계값(bound)으로 유망하지 않은 노드를 가지치기하며 최적해를 찾는 방법이다.
오류나 개정된 내용이 보이면 알려주세요