방통대 ) 2020 )알고리즘
- 최초 등록일
- 2020.05.10
- 최종 저작일
- 2020.05
- 5페이지/ MS 워드
- 가격 5,000원
소개글
"방통대 ) 2020 )알고리즘"에 대한 내용입니다.
목차
1. 분할정복 ( divide and conquer ) 방법
2. 동적 프로그래밍 ( dynamic programming )
3. 욕심쟁이( greedy ) 방법의 원리
4. 분할 정복 방법
5. 동적 프로그래밍 방법
6. 욕심쟁이 알고리즘
본문내용
분할정복 ( divide and conquer ) 방법
순환적으로 문제를 푸는 하향식 접근 방법 (거대한 문제를 작은 하위 문제로 분해) 이다. 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제들로 순환적으로 분할하고, 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방법이다. 분할된 작은 문제들은 서로 독립적이다.(크기만 작아지고 원래 문제와 동일한 문제이다.) 각 순환 호출마다 분할, 정복 결합의 단계를 걸친다.
동적 프로그래밍 ( dynamic programming )
문제의 크기가 작은 소 문제에 대한 해를 저장해 놓고 이를 이용하여 크기가 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법이다. 주로 최솟값 또는 최댓값을 구하는 최적화 문제에 사용된다. 최적성의 원리가 반드시 성립해야 하며, 성립이 되는지 우선 확인 해야 한다. 최적성의 원리란 주어진 문제에 대한 최적해는 주어진 문제의 소 문제에 대한 최적해로 구성된다는 원리이다. 이 방법의 처리과정은 1. 주어진 문제에 대해서 최적해를 제공하는 점화 식을 도출한다.
참고 자료
없음