알고리즘들에 대한 설명으로 옳지 않은 것은? | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 25년 1회차
알고리즘들에 대한 설명으로 옳지 않은 것은?
1
크루스칼의 최소 신장 트리 알고리즘은 가중치가 가장 작으면서 사이클을 만들지 않는 간선을 추가하여 트리를 구성한다.
2
프림(Prim)의 최소 신장 트리 알고리즘은 현재까지 만들어진 트리에 최소 가중치로 연결되는 정점을 트리에 추가한다.
3
허프만(Huffman) 압축에서 파일에 빈번히 나타나는 문자는 긴 이진코드를 할당하고, 드물게 나타나는 문자는 짧은 이진코드를 할당한다.
4
벨만－포드(Bellman-Ford)의 최단 경로 알고리즘은 음의 가중치를 갖는 간선이 존재하는 상황에서도 단일 출발점 최단 경로 문제를 해결하는 알고리즘이다.
해설
옳지 않은 설명은 허프만 압축에서 자주 나오는 문자에 긴 코드를 준다는 내용이다.
허프만 코드는 빈도가 높은 문자에 짧은 코드, 빈도가 낮은 문자에 긴 코드를 할당해 전체 비트 수를 줄인다.
- 크루스칼 알고리즘은 가중치가 작은 간선부터 사이클을 만들지 않는 것만 추가하므로 옳다.
- 프림 알고리즘은 현재 트리에 최소 가중치로 연결되는 정점을 하나씩 추가하므로 옳다.
- 벨만-포드 알고리즘은 음의 가중치 간선이 있어도 단일 출발점 최단 경로를 구하므로 옳다.
오류나 개정된 내용이 보이면 알려주세요