다음에서 설명하는 알고리즘 설계 기법으로 가장 알맞은 것은?해결하고자 … | [계리직 컴퓨터일반] 18년 1회차 기출문제 상세 페이지
1[계리직 컴퓨터일반] 18년 1회차
다음에서 설명하는 알고리즘 설계 기법으로 가장 알맞은 것은?
해결하고자 하는 문제의 최적해(Optimal Solution)가 부분 문제들의 최적해들로 구성되어 있을 경우, 이를 이용하여 문제의 최적해를 구하는 기법이다.
1
동적 계획법(Dynamic Programming)
2
탐욕적 알고리즘(Greedy Algorithm)
3
재귀 프로그래밍(Recursive Programming)
4
근사 알고리즘(Approximation Algorithm)
해설
설명하는 기법은 동적 계획법(Dynamic Programming)이다.
동적 계획법은 최적 부분 구조를 가진 문제에서 작은 부분 문제의 최적해를 먼저 구해 저장하고, 이를 조합해 전체 문제의 최적해를 구한다.
- 탐욕적 알고리즘: 매 단계에서 그 순간 가장 좋아 보이는 선택을 확정해 나가는 기법으로, 부분 문제들의 최적해를 모아 결합하는 방식이 아니다.
- 재귀 프로그래밍: 함수가 자기 자신을 호출하는 구현 방식으로, 최적해를 구하는 설계 기법 자체를 가리키지 않는다.
- 근사 알고리즘: 최적해 대신 최적해에 가까운 해를 효율적으로 구하는 기법이다.
오류나 개정된 내용이 보이면 알려주세요