[조합론] 4. 점화식(1: 알고리즘, 점화식들의 예)

[조합론] 4. 점화식(1: 알고리즘, 점화식들의 예)

알고리즘(algorithm)은 주어진 문제를 (컴퓨터를 사용하여) 해결하기 위한 방법을 의미하며 어떤 값 또는 값의 집합을 입력으로 받아 갑 또는 값의 집합을 출력하는 잘 정의도니 절차이다. 

다음은 알고리즘의 5가지 특징이다.

(1) 유한성(finiteness): 알고리즘은 유한번 안으로 끝나야 한다.

(2) 명확성(definiteness): 알고리즘의 각 단계는 명확하게 정의되어야 한다.

(3) 입력(input): 알고리즘이 시작되기 위해서는 초기에 어떤 특정한 값을 입력해야 한다.

(4) 출력(output): 알고리즘은 입력과 관계가 있는 몇 개의 출력이 있어야 한다.

(5) 유효성(effectiveness): 알고리즘에서의 모든 작업은 정확해야 하며, 종이와 연필로 유한 시간에 끝낼 수 있어야 한다.

알고리즘에서는 정확성과 효율성 이 두가지를 고려해야 하며, 정확성과 관련해서 고려해야 할 요소는 다음과 같다.

(1) 유한회의 과정을 통해 답을 얻을 수 있어야 한다.

(2) 단계가 분명하게 정의되어 있어야 한다.

(3) 한 단계가 끝나면 다음 단계가 명확해야 한다.

다음은 알고리즘의 예시들이다.

*참고: 다음의 알고리즘은 의사코드(psuedo code)로 작성되었다.

호너의 방법(Horner's method)

호너의 방법은 특정한 $x$에 대하여 다항식 $f(x)=a_{0}x^{n}+a_{1}x^{n-1}+\cdots+a_{n-1}x+a_{n}$의 값을 구하는 과정이다.

Procedure poly(x) f_{0}=a_{0} for i=0 to n-1 do      f_{i+1}=f_{i}×x+a_{i+1} return f_{n} end poly

여러개의 수 중에서 큰 수를 찾는 알고리즘

algorithm max(a_{1}, a_{2}, ..., a_{n}) begin         max=a_{1}         i=2         while i<=n         {         if max<a_{i} then max=a_{i}         i=i+1         }         print max end

$n!$을 구하는 알고리즘

Procedure factorial(n) if n=0 then     return(1)    return(n*factorial(n-1)) end factorial

음이 아닌 두 정수 $a$와 $b$에 대하여 두 수의 최대공약수를 구하는 알고리즘(유클리드 알고리즘)

Procedure gcd(a, b)   if a<b then       swap(a, b) #큰 수로 바꾸기#   if b=0 then      return(a)   r=a mod b #r은 a를 b로 나누었을 때의 나머지#   return(gcd(b, r)) end gcd

순서도(flow chart)는 알고리즘을 그림으로 나타낸 것으로, 해결 과정을 단계적으로 쉽게 파악할 수 있게끔 그림(전개도)으로 나타낸 것이다. 

다음은 순서도에 사용되는 기호들이다.

	시작 또는 끝을 나타내는 기호
	처리 기호
	판단기호
	인쇄기호

 

다음은 순서도의 한 예시이다.

알고리즘의 효율성을 판단하는 기준은 문제를 해결하는데 소요되는 시간이다.

예: 다음은 $n$개의 수 $x_{1},\,x_{2},\,\cdots,\,x_{n}$을 크기순으로 배열하는 두가지 방법이다.

방법 1

1. 다음 알고리즘에 의해 $x_{1},\,x_{2},\,\cdots,\,x_{n}$의 최댓값 $\max\{x_{1},\,x_{2},\,\cdots,\,x_{n}\}$을 찾는다.

(1) $x_{1}$과 $x_{2}$를 비교하여 $\max\{x_{1},\,x_{2}\}$를 찾는다.

(2) $\max\{x_{1},\,x_{2}\}$와 $x_{3}$을 비교하여 $\max\{x_{1},\,x_{2},\,x_{3}\}$을 찾는다.

..........................................

(n-1) $\max\{x_{1},\,x_{2},\,\cdots,\,x_{n-1}\}$과 $x_{n}$을 비교하여 $\max\{x_{1},\,x_{2},\,\cdots,\,x_{n}\}$을 찾는다.

2. $x_{1},\,x_{2},\,\cdots,\,x_{n}$중 $\max\{x_{1},\,x_{2},\,\cdots,\,x_{n}\}$을 제외한 나머지 n-1개의 수를 가지고 1번의 알고리즘을 적용해서 $x_{1},\,x_{2},\,\cdots,\,x_{n}$중 두번째로 큰 수를 찾는다.

3. 위 과정을 반복해서 $x_{1},\,x_{2},\,\cdots,\,x_{n}$을 크기순으로 나열할 수 있다.

이 경우의 비교회수는 $\displaystyle(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$이다.

방법 2

1. $x_{1},\,x_{2},\,\cdots,\,x_{n}$ 중 임의로 $y$를 선택해서 나머지 $n-1$개의 원소들을 $y$를 기준으로 $y$보다 작으면 $y$의 앞에, $y$보다 크면 $y$의 뒤에 두어서 두 개의 집합 $X_{1}$과 $X_{2}$로 분리한다.

2. $X_{1}$과 $X_{2}$ 각각을 1과 같은 방법을 이용하여 크기순으로 나열해 합치면 원하는 배열을 얻을 수 있다.

이 경우의 비교회수는 대부분 방법 1보다 빠른 시간안에 해결가능하나 최악의 경우는 방법 1과 같은 비교회수를 통해 문제가 해결된다.

수열의 $n$번째 항을 그 이웃한 항이나 그보다 앞선 항들에 대한 관계식으로 나타낼 수 있을 때가 있다.(예: 피보나치 수열 $a_{n+2}=a_{n+1}+a_{n},\,a_{1}=a_{2}=1$) 이러한 관계를 점화관계(recurrence relation)라고 하고 여기의 관계식을 점화식(recurrence formula)이라고 한다. 특별한 경우, 점화식과 초기조건으로부터 일반항 $a_{n}$의 식을 유도할 수 있다.

예: 하노이 탑 문제(Hanoi tower problem)

(하노이 탑 모형)

등판에 막대가 3개 있고, 크기가 서로 다른 $n$개의 원판이 한 막대에 크기순으로(큰 원판이 작은 원판보다 아래에 놓임) 꽂혀 있다. 이때 다음의 규칙대로 원판을 다른 막대로 옮긴다.

(1) 한 번에 한개의 원판만을 옮긴다.

(2) 크기가 큰 원판은 반드시 크기가 작은 원판 아래쪽에 있어야 한다.

그러면 원판을 모두 다른 막대로 옮기는데 필요한 최소한의 이동 횟수는?

풀이: 원판의 개수가 $n$일 때, 최소 이동횟수를 $a_{n}$이라 하자. 그러면$a_{1}=1,\,a_{2}=3$이고

임의의 $n$에 대하여, 가장 큰 원판을 처음으로 옮길 때에는, 다른 원판들은 모두 하나의 막대에 크기순으로 배열되어 있어야 한다. 따라서 가장 큰 원판을 옮기기 전까지의 최소 이동횟수는 $a_{n-1}$이다. 가장 큰 원판을 비어있는 다른 원판에 이동한 다음, 나머지 $n-1$개의 원판을 가장 큰 원판이 놓여 있는 막대로 이동해야 한다. 따라서 $a_{n}=2a_{n-1}+1$이 성립하고 $$\begin{align*}a_{3}&=2a_{2}-1=7=2^{3}-1\\a_{4}&=2{a}^{3}+1=2(2^{3}-1)+1=2^{4}-1\end{align*}$$ 이므로 $a_{n}=2^{n}-1$이다.

($n=4$일 때, $a_{4}=2^{4}-1=15$이다)

*참고: 베트남 하노이 시 외곽에 있는 베나레스(Benares) 사원의 한 가운데에 있는 돔(Dome)에 다음의 전설이 기록된 동판이 있다:

"동판에 다이아몬드 막대가 3개 있고, 크기가 서로 다른 64개의 황금 원판이 한 막대에 꽂혀있다. 이때 다음과 같은 규칙으로 황금 원판을 다른 막대로 모두 옮기는 놀이를 신(god, 神)이 하고 있다

(1) 한번에 한개의 황금원판만을 옮긴다.

(2) 크기가 큰 황금원판은 반드시 크기가 작은 황금 원판 아래에 있어야 한다.

신이 이 놀이를 끝내면(황금원판이 다른 막대로 모두 옮겨졌다면), 이 세상은 종말이 올 것이다."

실제로 황금원판 한개를 다른 원판으로 옮기는데 1초가 걸린다고 가정하면, 황금원판이 다른 막대로 모두 옮겨지는데 걸리는 시간은 $2^{64}-1=18,446,744,073,709,551,615$초(대략 5833억년)가 걸린다.(걱정할 필요가 없다)

예: 한 아이가 7개의 계단을 올라간다고 하자. 이때 한번에 하나 또는 두개의 계단을 오를 수가 있다. 이 아이가 7개의 계단을 서로 다르게 오르는 방법의 수는?

풀이: $n$개의 계단을 오르는 경우의 수를 $a_{n}$이라 하자. 그러면 $a_{1}=1,\,a_{2}=2$익, $n\geq3$인 경우, 처음에 한 개의 계단을 오르는 경우, 이 경우의 수는 남아있는 $n-1$개의 계단을 오르는 방법의 수와 같으므로 $a_{n-1}$가지가 된다. 처음에 두개를 오르는 경우, 남아있는 $n-2$개의 계단을 오르는 방법의 수와 같으므로 $a_{n-2}$가지가 된다. 따라서 다음의 점화식 $$a_{n}=a_{n-1}+a_{n-2}\,(a_{1}=1,\,a_{2}=2,\,n\geq3)$$ 을 얻고 $$a_{7}=a_{6}+a_{5}=2a_{5}+a_{4}=3a_{4}+2a_{3}=5a_{3}+3a_{2}=8a_{2}+5a_{1}=16+5=21$$ 이다.

참고: 위의 점화식을 갖는 수열을 피보나치 수열(Fibonacci sequence)이라고 한다.

예: 평면상에 $n$개의 직선이 나누는 영역의 최대 개수(어떤 두 직선도 평행하지 않고, 어떤 세 직선도 한 점에서 만나지 않도록 직선을 그을 때 생기는 영역의 수)는?

풀이: $n$개의 직선으로 나눌 때 생기는 영역의 최대 개수를 $a_{n}$이라고 하자. 그러면 $a_{1}=2$이고 $n\geq2$일 때, $n$번째 직선을 그리면 나머지 $n-1$개의 직선과 만나는 교점의 수는 $n-1$개이고, 영역의 수는 $n$개 더 늘어난다. 따라서 점화식 $$a_{n}=a_{n-1}+n,\,a_{1}=2\,(n\geq2)$$ 을 얻고 일반항은 $$a_{n}=1+\frac{n(n+1)}{2}$$ 이다.

예: $0,\,1,\,2$로 이루어진 길이가 $n$인 $3^{n}$개의 수열 중 $0$의 개수가 홀수인 수열의 개수는?

풀이: 길이가 $n$이고 $0$의 개수가 홀수인 수열의 개수를 $b_{n}$이라고 하자.

끝자리가 $1$인 경우는 $b_{n-1}$개 이고, 끝자리가 $2$인 경우는 $b_{n-1}$개, 끝자리가 $0$인 경우, $3^{n-1}-b_{n-1}$이므로 다음의 점화식을 얻고 $$b_{n}=b_{n-1}+3^{n-1},\,b_{1}=1$$ 이므로 $\displaystyle b_{n}=\frac{3^{n}-1}{2}$이다.

참고자료:

조합론과 그래프이론, 조성진, 김한두, 경문사

https://www.scienceall.com/%EC%88%9C%EC%84%9C%EB%8F%84flow-chart/

https://support.office.com/ko-kr/article/%EA%B8%B0%EB%B3%B8-%EC%88%9C%EC%84%9C%EB%8F%84-%EB%A7%8C%EB%93%A4%EA%B8%B0-e207d975-4a51-4bfa-a356-eeec314bd276

https://en.wikipedia.org/wiki/Tower_of_Hanoi 

수학비타민, 박경미, 랜덤하우스 중앙