다음 설명에 해당하는 알고리즘 기법은?○ 깊이 우선 탐색(DFS, De… | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 26년 1회차
다음 설명에 해당하는 알고리즘 기법은?○ 깊이 우선 탐색(DFS, Depth First Search)이 기본 골격이다.
○ 해를 찾는 도중에 해가 아니면 되돌아가서 다시 해를 탐색한다.
○ 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있다.
1
백 트래킹(back tracking)
2
k-NN(k-Nearest Neighbors)
3
그리디(greedy) 알고리즘
4
분할 정복(divide-and-conquer) 알고리즘
해설
설명에 해당하는 기법은 백트래킹이다.
백트래킹은 상태 공간 트리를 깊이 우선 탐색하다가 해가 될 가능성이 없는 노드를 만나면 부모로 되돌아가 다른 경로를 탐색하며, 결정 문제와 최적화 문제 모두에 쓰인다.
- k-NN은 가장 가까운 k개의 이웃으로 분류·회귀를 하는 기계학습 기법으로 되돌아가는 탐색과 무관하다.
- 그리디 알고리즘은 매 순간 최선의 선택을 하고 되돌아가지 않는다.
- 분할 정복은 문제를 독립적인 부분 문제로 나누어 풀고 결합하는 기법이다.
오류나 개정된 내용이 보이면 알려주세요