관계기반 알고리즘 설계
(1) 탐색기반 알고리즘 설계 : 컴퓨터의 빠른 연산 속도를 이용하여 짧은 시간에 가능한 해의 집합을 탐색하면서 최적의 해를 구하는 기술적인 방법
(2) 관계기반 알고리즘 설계 : 해를 구하는 행위를 하나의 함수로 표현하고 이 함수들의 관계를 이용하여 해를 구하는 방법
- 문제의 정의 및 상태를 함수로 정의, 이 함수들 간의 관계를 점화식 혹인 이와 유사한 형태로 표현, 수학적 귀납법/점화식 등의 표현 기반
수학적 귀납법
- 자연수 n에 관한 명제 P(n)이 모든 자연수에 대해서 성립함을 증명하기 위한 수학의 증명법 중 한 방법
- 다음의 두가지 단계로 증명
1) P(1)이 성립함을 보인다.
2) P(k)가 성립한다고 가정하고 P(k+1)이 성립함을 보인다.
- 수학적 귀납법을 이용한 문제해결의 절차
1) 입력값이 n인 문제의 해를 f(n)으로 정의
2) f(1)을 직접 구하여 출력
3) f(k)를 이미 구해두었다고 가정하고 f(k)를 통하여 f(n)을 구하고 출력한다.
- 예제1 : 임의의 정수 n을 입력받아 1부터 n까지 합을 구하는 프로그램을 작성하시오. (단, n<=100)
-> 풀이1
1) f(n)을 다음과 같이 정의
- f(n)='1부터 n까지의 합'
2) f(1)을 정의에 의하여 직접 구하면,
- f(1) = 1
3) f(n-1)을 이미 구해두었다고 가정, 다음과 같이 f(n)을 구할 수 있다. f(10)을 f(9)를 이용하여 나타내면,
- f(10) = 1+2+3+4+5+6+7+8+9+10
- f(9) = 1+2+3+4+5+6+7+8+9
->f(10) = f(9) + 10, 이를 일반화 하면
->f(n) = f(n-1)+n
이 관계를 재귀함수를 이용하여 풀면,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include<iostream> using namespace std; int f(int n) { if (n == 1) return 1; return f(n - 1) + n; } int main() { int n; cin >> n; cout << f(n) << endl; return 0; } | cs |
이러한 문제해결 방법을 분할정복(divide and conquer)기법이라고 한다.
일반적으로 분할정복 기법은 입력크기 n을 동일한 크기의 k개의 함수로 분할하여 이 분할의 결과를 이용하여 전체 문제를 해결하는 방법을 말한다.
'Software Development > Algorithm' 카테고리의 다른 글
Combination, n개 중 k개를 고르는 방법의 수 (0) | 2016.03.06 |
---|---|
DFS/BFS 숙달을 위한 알고리즘 문제(기본/응용) (6) | 2016.02.17 |
탐색기반 알고리즘 설계_3.깊이우선탐색(DFS) (0) | 2016.01.30 |
탐색기반 알고리즘 설계_2.비선형구조탐색 (0) | 2016.01.30 |
탐색기반 알고리즘 설계_1.선형구조탐색 (0) | 2016.01.17 |