다음 설명에 해당하는 알고리즘은?○ 주어진 문제에 대해 근사해나 일정 … | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 25년 1회차
다음 설명에 해당하는 알고리즘은?○ 주어진 문제에 대해 근사해나 일정 확률 이상의 최적해를 출력함
○ 근사해나 간혹 틀린 해를 허용할 수 있는 경우에 사용 가능함
○ 효율적인 결정론적 알고리즘이 밝혀져 있지 않은 문제에 효과적임
1
유클리드(Euclid) 알고리즘
2
스트라센(Strassen) 알고리즘
3
몬테카를로(Monte Carlo) 알고리즘
4
플로이드－워샬(Floyd-Warshall) 알고리즘
해설
설명에 해당하는 알고리즘은 몬테카를로 알고리즘이다.
몬테카를로는 난수를 이용하는 확률적 알고리즘으로, 정해진 시간 안에 끝나지만 결과가 근사해이거나 일정 확률로 틀릴 수 있다.
- 유클리드 알고리즘은 최대공약수를 정확히 구하는 결정론적 알고리즘이다.
- 스트라센 알고리즘은 분할 정복으로 행렬 곱셈 횟수를 줄이는 결정론적 알고리즘이다.
- 플로이드-워샬 알고리즘은 동적 프로그래밍으로 모든 정점 쌍의 최단 경로를 정확히 구한다.
오류나 개정된 내용이 보이면 알려주세요