본문 바로가기

방송통신대학교1220

[알고리즘] 5강 동적 프로그래밍 알고리즘 1. 동적 프로그래밍 방법의 원리 문제의 크기가 작은 소문제에 대한 해를 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법 각 작은 문제는 원래의 문제와 동일한 문제이지만 입력의 크기만 작음 입력의 크기가 아주 작은 단순한 문제가 되면 쉽게 해를 구할 수 있고, 이를 테이블에 저장 이후 해당 소문제의 해가 필요할 때마다 테이블에 저장된 결과를 바로 이용 동적 프로그래밍 dynamic programming => 동적 계획법 (타 서적, 교육에서는 동적 계획법이라 많이 부른다.) 컴퓨터에서의 프로그램과는 무관, 해를 구축하는 테이블을 이용한다는 의미 최솟값/최댓값을 구하는 최적화 문제에 적용 2. 피보나치 수열 문제 3. 연쇄 행렬 곱셈 문제 2018. 6. 18.
[알고리즘] 4강 분할정복 알고리즘 2 2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 3강 분할정복 알고리즘 - 1 2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 2강 알고리즘 소개 2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개 1. [복습] 분할정복 방법의 원리 순환적으로 문제를 푸는 하향식 접근 방법 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식 '분할' - '정복' - 결합 특징 - 분할된 문제는 원래 문제와 동일(입력 크기만 감소) 하고 서로 독립적 .. 2018. 5. 25.
[알고리즘] 3강 분할정복 알고리즘 - 1 2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 2강 알고리즘 소개 2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개 1. 분할정복 방법의 원리 순환적으로 문제를 푸는 하향식 접근 방법 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식 특징 분할된 작은 문제는 원래 문제와 동일 → 단, 입력 크기만 작아진다. 분할된 문제는 서로 독립적 → 순환적 분할 및 결과 결합이 가능 각 순환 호출 시의 처리 과정 분할: 주어진 문제를 여러 개의 작은 문제로 분할 정복: 작은 문제.. 2018. 5. 22.
[알고리즘] 2강 알고리즘 소개 2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개 1. 알고리즘의 설계 1) 최댓값 찾기 1-1) 값들을 하나씩 모두 비교해 가면서 최댓값을 찾는 방법 1-2) 토너먼트 방식 둘씩 비교해서 큰값을 찾아가는 방법 더 효율적인것을 결정해야한다. (n-1)번 1-1과 1-2 의 효율성은 7번으로 같다. 2) 뒤섞인 카드에서 원하는 카드 찾기 2-1) 순차탐색(Sequential Search) 순차적으로 전부 다 뒤집는다 1 2 3 4 5 6 7 8 SequentialSearch(A[], n, x) // 배열 A[0..n-1]에서 x를 찾는 알고리즘 { for(i = 0; i Right) return -1; Mid = (left + right) / 2; .. 2018. 5. 22.