그리디 알고리즘에 해당하는 것은? | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 26년 1회차
그리디 알고리즘에 해당하는 것은?
1
크루스칼(Kruskal) 알고리즘
2
0/1 배낭(knapsack) 문제 풀이
3
플로이드－워셜(Floyd-Warshall) 알고리즘
4
최장 공통 부분 수열(LCS, Longest Common Subsequence) 구하기
해설
그리디 알고리즘에 해당하는 것은 크루스칼 알고리즘이다.
크루스칼 알고리즘은 사이클을 만들지 않는 범위에서 가중치가 가장 작은 간선을 매번 선택해 최소 신장 트리를 만드는 탐욕적 선택 방식이다.
- 0/1 배낭 문제는 물건을 쪼갤 수 없어 그리디로 최적해가 보장되지 않으며 동적 계획법으로 푼다.
- 플로이드-워셜 알고리즘은 경유 정점을 하나씩 늘려 가는 동적 계획법이다.
- 최장 공통 부분 수열은 부분 문제 표를 채우는 동적 계획법으로 구한다.
오류나 개정된 내용이 보이면 알려주세요