알기쉬운알고리즘[개정판](생능출판,양성봉)-챕터5연습문제

소개

"알기쉬운알고리즘[개정판](생능출판,양성봉)-챕터5연습문제"에 대한 내용입니다.

목차

없음

본문내용

1. 다음의 괄호 안에 알맞은 단어를 채워 넣어라.
(1) 동적 계획 알고리즘은 입력 크기가 ( 작은 ) 부분문제들을 모두 해결한 후에 그 해들을 이용하여 보다 ( 큰 ) 크기의 부분문제들을 해결하는 알고리즘이다.
(2) 동적 계획 알고리즘에는 부분문제들 사이에 ( 함축적 ) 관계가 존재한다.
(3) 동적 계획 알고리즘은 그리디 알고리즘과 같이 ( 최적성 원칙 ) 특성을 가진다.
(4) 모든 쌍 최단 경로 문제를 위한 ( Floyd-Warshall ) 알고리즘은 ( 경유 ) 가능한 점 들을 점 1로부터 하나씩 추가하여 모든 점들을 ( 경유 ) 가능한 점들로 고려하면서, 최단 경로의 거리를 계산한다.
(5) 연속 행렬 곱셈을 위한 알고리즘은 주어진 연속된 행렬들의 순서를 지켜서( 이웃 )하는 행렬들끼리 곱하는 모든 ( 부분문제 )들을 해결한다.
(6) 편집 거리 문제를 위한 알고리즘은 2차원 배열의 한 원소인 E[j]를 계산 하는데 3개의 부분문제인 ( E[i, j-1], E[i-1, j], E[i-1, j-1] )만을 참조하여 계산한다.
(7) 배낭 문제를 위한 알고리즘은 배낭의 용량을 0부터 ( 1 )씩 증가시키면서 물건을 ( 1 )씩 추가하며 각각의 경우에 ( 최대 ) 가치를 계산하여 해를 찾는다.
(8) 동전 거스름돈 문제는 거스름돈을 0원부터 ( 1 )씩 증가시켜 해결한다. 이는 ( 배낭 ) 문제와 유사하며 거스름돈을 ( 배낭 )의 용량으로 생각하고, 동전을 ( 물건 )이라고 생각하면 된다.

참고자료

· 없음