[알고리즘] 분할정복, 동적 프로그래밍 조사 > sati1

[알고리즘] 분할정복, 동적 프로그래밍 조사

페이지 정보

작성일 23-01-29 22:06

본문

이처럼 해를 구할 수 있을 만큼 충분히 더 작은 事例(사례)로 나누어 해결하는 방법이다.

일반적으로 적용되는 방법은 Merge, Quick Sort 등의 정렬분야와 곱셈, 고속 푸리에 변환등의 계산분야가 있다아

다. 일상 생활에서 가장 일반적으로 생각하는 것은 10개중에 가장 큰 값을 찾고, 9개중에 가장 큰 값을 찾는 식의 동작을 반복하는 것이다. 1805년 12월 2일 아우스터리츠 전투에서 프랑스의 황제 나폴레옹은 숫자면에서 우세했던 연합군을 물리치기 위해서 나폴레옹은 연합군의 중앙으로 쳐들어가 그들의 병력을 둘로 갈라 놓았고, 둘로 나누어진 병력은 개별적으로는 나폴레옹의 군대보다 숫자가 적었기 때문에 전투는 나폴레옹의 승리로 끝나게 되었다.
분할정복법은 주어진 문제를 작은 사례로 나누어(Divide) 각각의 작은 문제들을 해결(Conquer)하는 방법이다.
어떤 한 반의 4명의 학생들이 중간고사를 보았다. 결과는 아래와 같다. 작은 事例(사례)가 충분히 작지 않으면 재귀적으로 다시 분할한다. 성적 공시를 위해서 이 학생들의 등수를 높은 순서대로 나열해야 할 때 가장 빠르게 나열할 수 있는 방법을 記述하시오.

위와 같은 종류의 문제는 정렬 문제에 속하게 된다.

알고리즘,분할정복, 동적 프로그래밍
순서

분할정복법은 주어진 문제를 작은 example(사례) 로 나누어(Divide) 각각의 작은 문제들을 해결(Conquer)하는 방법이다.

여기서는 합병정렬 방법을 적용하겠다.

이다. 하지만 우리는 여기에 분할정복의 관념을 적용함으로써 훨씬 더 빠르게 작업할 수 있다아

합병정렬은 정렬 대상이 되는 값들을 계속해서 절반으로 쪼개고, 쪼개진 값들의 덩어리가 1개가되었을 때 덩어리들을 합쳐주고, 그 덩어리들을 합병하는 과정에서 정렬을 해주는 것이다. 또한 분할정복법은 하향식(top-down)접근 방법이다. 그렇기 때문에 분할정복법을 해결할때는 재귀적 방법이 많이 쓰인다. 즉, 문제의 최상위 事例(사례)의 해답은 아래로 내려가면서 작은 事例(사례)에 대한 해답을 구함으로써 구한다. 문제의 事例(사례)를 2개 이상의 더 작은 事例(사례)로 나눈다.

2. 작은 事例(사례)들을 각각 정복(Conquer)한다. 나눈 작은 事例(사례)의 해답을 바로 얻을 수 있으면 해를 구하고 아니면 더 작은 事例(사례)로 나눈다.

레포트 > 공학,기술계열
[알고리즘] 분할정복, 동적 프로그래밍 조사
설명

a(90), b(80), c(70), d(60) (알파벳은 식별번호, 괄호 안은 점수)

Download : [알고리즘] 분할정복, 동적 프로그래.docx( 53 )

3. 필요하다면, 각각의 작은 事例(사례)들을 통합(Combine)해서 원래 事例(사례)의 해답을 구한다.

분할정복법의 설계전략(strategy)은 다음과 같다.

예제1) 정렬분야
분할정복법은 위와 같은 事例(사례)를 호로그램에 이용한 것이다. 이 작은 事例(사례)는 주로 원래 문제에서 따온다.

1. 문제 事例(사례)를 하나 이상의 작은 事例(사례)로 분할(Divide)한다.

1805년 12월 2일 아우스터리츠 전투에서 프랑스의 황제 나폴레옹은 숫자면에서 우세했던 연합군을 물리치기 위해서 나폴레옹은 연합군의 중앙으로 쳐들어가 그들의 병력을 둘로 갈라 놓았고, 둘로 나누어진 병력은 개별적으로는 나폴레옹의 군대보다 숫자가 적었기 때문에 전투는 나폴레옹의 승리로 끝나게 되었다.

번호	제목
9296	[2023][SK그룹] SKC 자기紹介(소개)서(생산기술, 2009년 하반기)
9295	[현대시론] 김현승 시세계 분류(세시기) 및 각 시기별 대표작품 analysis
9294	사회복지조직의 원리
9293	[일반물리학실험] 전반사 및 초점거리 실험
9292	[Edge]세계 과학기술과 environment(환경) 문제에 대한 성찰
9291	2015년 LG하우시스 품질관리 합격 자기introduction서
9290	0세 11월 일일보육간편일지 (2019년 11월 1주~4주)
열람중	[알고리즘] 분할정복, 동적 프로그래밍 조사
9288	[시론] 현대시 동인들의 언어와 서정성에 대한 소논문 / 현대시 동인들의 언어
9287	주요 그룹사, 수익구조 크게 改善(개선) -순이익 급증
9286	노인학대 문제 analysis(분석)
9285	세대와 소비文化) 靑少年, 대학생, 노인의 소비文化
9284	가족간의 효율적인의사소통법 학습지도안과 학습자료(data)
9283	투자와 기업分析을 목적으로 한 동일금속 分析글입니다.
9282	[Edge][현대자동차그룹] 현대모비스 합격 자기紹介서(R&D 연구개발4, 2005년 하반기)

[알고리즘] 분할정복, 동적 프로그래밍 조사 > sati1

sati1

페이지 정보

본문

검색