[ Algorithm ] 동적 계획 (2)
동적 계획
1) 함수
단일 변수 함수(function) : f는 변수 x를 유일한 값 f(x)와 연관 짓는 규칙 또는 법칙
주어진 실수 x와 그 실수의 제곱과 연관 짓는 함수 f는 순서쌍(ordered pair)집합으로 나타낼 수 있다.(ex) f(x) = x^2 는 모든 순서쌍 (x,x^2))
함수의 그래프(graph)는 그 함수로 구하는 모든 순서쌍의 집합이며 x ≠ 0이 아닐 때만 정의.
- 함수의 변역(domain)은 함수가 정의하는 값의 집합.
- f(x) = 1 / x의 변역은 0을 제외한 모든 실수.
- f(x) = x^2의 변역은 모든 실수.
f(x) = x^2은 음수가 아닌 값만 가지는데, 여기서 “음수 아닌 값＂이란 0보다 크거나 같은 값을 의미(“양수 값”이란 0보다 엄밀히 큰 값을 의미)
함수의 치역(range)은 함수가 가지는 값의 집합, f(x) = x^2의 치역은 음이 아닌 실수가 되고, f(x) = 1 / x의 치역은 0을 제외한 모든 실수, (ex) f(x) = 〖(1/x)〗^2의 치역은 모든 양의 실수)
- 함수는 변역에서 치역으로 간다.
2) 수학적 귀납법
어떤 합산은 일반형으로 표현할 수 있으나, 양수인 정수의 개수는 무한하기 때문에 개별적으로 각 n에 대해서 일일이 검사해서는 모든 양의 정수 n에 대해서 이 등식이 성립하는지 확신 X. 모든 양의 정수 n에 대해서 등식이 성립함을 보여줄 수 있는 강력한 방법이 수학적 귀납법(mathematical induction)
수학적 귀납법은 도미노 원칙(domino principle)과 같은 방법으로 , 만약 두 도미노 사이의 거리가 도미노의 높이보다 항상 작다면 첫째 도미노만 넘어뜨리면 모든 도미노를 넘어뜨릴 수 있다.
- 첫째 도미노를 넘어뜨린다.
- 두 도미노 사이의 거리가 도미노의 높이보다 작게 모든 도미노를 세우면, n 번째 도미노가 넘어지면, (n+1) 번째 도미노도 넘어진다고 보장할 수 있다.
이론적으로 임의의 아무리 많은 수의 도미노를 세우더라도 모두 넘어진다고 할 수 있다.
귀납법 또한 같은 원리인데, n = 1일 때 증명하려고 한 것이 사실임을 먼저 보이고, 임의의 양의 정수 n에 대해서 사실이라면 n+1일 때도 반드시 사실임이 밝혀지면, 이와 같은 방식으로 무한히 계속 이야기 할 수 있으며 따라서 모든 양의 정수 n에 대해서 사실이라고 결론 지을 수 있다.
※ 양의 정수에 관한 어떤 문장이 사실임을 귀납법으로 증명할 때 쓰는 용어
귀납 기초(induction base) : n=1(또는 다른 초기 값)에 대해서 그 문장이 사실이라는 증명
귀납 가정(induction hypothesis) : n≥1(또는 다른 초기 값)인 임의의 n에 대해서 그 문장이 사실이라는 가정
귀납 단계(induction step): 만약 문장이 n에 대해서 사실이라면, n+1에 대해서도 반드시 사실이어야 한다는 증명
귀납기초는 결국 첫번째 도미노를 쓰러뜨리는 것에 해당하고, 귀납절차는 만약 n째 도미노가 넘어지면, (n+1) 째 도미노도 넘어진다는 것에 해당
귀납법은 사실일 가능성이 있는 문장이 있는 경우에 이를 증명할 때만 제 역할을 하며, 직관적 귀납법(constructive induction)이 이를 도와준다.
3) 정리와 보조 정리
정리(theorem): 무엇인가를 증명해야 할 명제라 정의.
앞의 사례들을 각각 정리라고 할 수 있고, 귀납법으로 정리를 증명. 정리를 기술하고 증명하는 이유는 다른 사례에 두루 쓰기 위한 일반적인 결과를 얻기 위한 것이다.(바로 계산 가능)
ex) 정리와 증명
정리 : 모든 실수 x에 대해서 x에 대해서 x > 0이면, x^2 > 0이다.
증명 : 두 양수의 곱은 양수라는 사실에 의해서 이 정리는 성립한다. (귀납법 증명)
기술된 문장의 역(reverse implication)은 사실이 아니다. (x^2 > 0 이면 x > 0 이다.)
역도 사실이라면 그 정리는 필요 충분 조건문이 되고, 정(implication)과 역을 모두 증명할 필요가 있다.
보조 정리(lemma): 다른 명제를 증명하기 위해 사용되는 보조적인 명제로 정의(정리와 마찬가지로 무언가를 증명하여 보여주는 명제)
보통 보조 정리 안에 있는 명제들은 그 자체로서는 별로 가치가 없고, 오히려 정리의 증명이 하나 이상의 보조적인 명제의 사실 여부에 의존할 때 이러한 명제에 관한 보조 정리를 기술하고 증명
4) 순열과 조합
항아리 안에 A,B,C,D 의 공이 존재할 때, 2개의 공을 순서에 맞게 꺼낼 확률을 4행과 3열로 결과를 정리
-> (4)(3) = 12
3개의 공을 순서에 꺼낼 확률
-> (4)(3)(2) = 24
일반적으로 n 개의 공이 있고, 그 가운데 k개를 꺼낸다면
-> (n)(n-1)(n-k-1)
이를 n개의 물체에서 한 번에 k개를 취하는 순열(permutation)의 수라고 한다.
이 알고리즘의 효율을 파악하기 위하여 각 n에 대하여 이 함수가 곱셈을 몇 번 수행하였는지 알아본다.
주어진 n에 대한 곱셈의 총 수행 횟수는 fact(n-1)을 계산할 때 곱셈의 수행횟수에다 n을 fact(n-1)로 곱할 때 수행하는 곱셈 1회를 더하면 된다. 주어진 n에 대하여 t_n 으로 표시하면
이와 같은 방정식은 n에 대한 함수값을 n보다 작은 값에 대한 함수값의 형태로 나타내기 때문에 재현식(recurrence equation)이라고 한다.
재현 그자체로는 함수를 제대로 나타내 주는 것이 아니고, 재현식에는 초기조건(initial condition)이라고 하는 재귀 기초가 반드시 있어야 한다.
이와 같은 방법으로 계속하여 어떤 t_n의 값도 구할 수 있지만, 0에서 시작하지 않고 임의의 n에 대하여 바로 t_n 을 계산할 수 있는 것은 아니다. 따라서 t_n을 명백히 식(expression)으로 나타낼 수 있어야 하며, 이러한 식을 재현식의 해(solution)라고 한다. 귀납법을 사용하여 해를 찾는 것은 불가능하며, 단순히 예상해(candidate solution)가 맞는지를 확인할 수 있을 뿐이다.
5) 대수(logarithm)
: 알고리즘 분석에서 가장 많이 사용되는 수학 도구 중 하나.
어떤 수 x의 사용 대수(common logarithm)는 log_x 로 표시, x가 10의 몇 승(power)이 되는지 나타내며, 일반적으로 어떤 수 x의 대수는 x가 또 다른 수 a의 몇 승이 되는 지를 나타낸다.
a는 1을 제외한 모든 양수가 될 수 있으며, 밑수(base)라고 한다.. 반면에 x는 반드시 양수여야한다.(음수나 0의 대수란 건 없다)
출처: 알고리즘 기초