수를 표기하는 방법과 0의 역할
- 10을 기수로 하는 자리수 기반 수 표기법(위치값 기수법).
- 10진법의 각 자리는 위치에 따라
10 ^ N의 자리를 나타낸다.
- 컴퓨터가 사용하는 수 표기법.
- 0과 1을 사용해 수를 나타낸다.
- 수의 각 자리는 위치에 따라
2 ^ N의 자리를 나타낸다.
- 10진법을 2진법으로 바꾸려면: 수를 2로 반복해서 나누어 나머지를 조사한다. 나머지를 반대 순서로 나열하면 2진법 표기가 된다.
- 2진법을 10진법으로 바꾸려면: 각 자리가 나타내는 자리와 자리수를 곱한 후 모두 더한다.
- 0과 1은 전압이 낮은 상태와 높은 상태, 자기장이 약한 상태와 강한 상태 등, 다양한 매체에서 구분하기 쉬운 간단한 두 가지 기계적 상태를 논리적으로 나타낸 것.
- 2진법을 이용하는 계산 회로를 설계하는 것이 10진법을 이용할 때보다 훨씬 간단하고 쉽다.
- 10진법, 2진법 등은 위치에 따라 수의 크기가 달라지는 위치값 기수법이다. 이 외에도 8진법과 16진법이 프로그래밍에 자주 사용된다.
- 로마식 숫자, 한문식 숫자는 위치에 관계없이 수의 크기를 나타내는 문자를 사용한다. 이들은 위치값 기수법이 아니다. 이들은 큰 수를 계산할 때 매우 불편하다!
- 참고: 과학 표기법(e 표기법)
- 10의 0승은 1이다.
- 10의 -1승은 10분의 1이다.
- 10의 -2승은 100분의 1이다.
- 2의 0승은 1이다.
- 2의 -1승은 2분의 1이다.
- 2의 -2승은 4분의 1이다.
- 밑을 N으로 하는 수에서, 지수가 1 줄어들 때마다 전체는 N분의 1이 된다.
- 지수법칙:
(N^a) * (N^b) = N ^ (a+b)
- 자리 확보: 위치값 기수법에서는 자리가 중요하므로 수가 없더라도 0이 자리를 지켜야 한다.
- 패턴을 만들어 규칙을 간단히 하기: 위치값 기수법에서 1을 나타낼 때 N의 0승으로 나타낼 수 있다. 이로써 지수 규칙에 일관성이 생긴다.
- 일상생활: 일상 생활에서도 일정이 없다, 약효가 없다 등 '아무겂도 없음'을 나타내야 하는 상황이 많다.
- 고대 이집트(파피루스): 5진법과 10진법을 혼용. 단, 위치값 기수법이 아니었고 0도 없었다.
- 바빌로니아(점토판): 10진법과 60진법이 혼용된 위치값 기수법을 사용. 60진법의 지금도 시간 등을 나타내는 데 사용된다.
- 그리스인: 도형, 우주, 음악 등에 수를 활용.
- 마야인: 수를 셀 때 0을 시작점으로 삼았다. 20진법을 사용.
- 로마인: 5진법과 10진법이 섞인 로마 숫자를 사용.
- 인도인: 바빌로니아에서 전해진 위치값 기수법을 채용하고, 0도 숫자라는 점을 인식. 10진법을 채용. 오늘날의 아라비아 숫자를 만듬.
- 인간은 수가 커질수록 잘 다루지 못한다.
- 위치값 기수법을 사용하면 큰 수도 작은 덩어리로 나누어 다룰 수가 있다.
- 커다란 문제는 작은 '덩어리'로 나누어 푼다는 사고방식: 프로그래밍의 진리 중 하나
- 위치값 기수법
- 0의 역할
- 지수법칙과 0승
- 간단한 규칙을 유지한 상태에서 개념을 확장하는 것의 중요성
true와 false로 양분하기
- 자연어는 모호하고 부정확하다. 논리는 자연어의 애매모호함을 없애고 정확한 상태를 나타내는 데 활용된다.
- 명제: 옳은지 아닌지를 판단할 수 있는 문장 명제가 옳으면 참, 그렇지 않으면 거짓이다. 명제는 참이면서 동시에 거짓일 수 없다. true도 false도 아닌 것은 명제가 아니다.
- 버스 요금 규칙처럼, 어떤 명제(조건)들을 기준으로 사물을 분할할 수 있다. 분할할 때는 망라/배타에 신경써야 한다.
- 망라: 모두 포함. 분할할 때 누락이 없도록 주의해야 한다.
- 배타: 동시에 성립되지 않음. 분할할 때 중복이 없도록 주의해야 한다. 중복된 조건은 '모순'이 된다.
- 수의 범위를 나타낼 때는 수직선을 그려 판단하면 도움이 된다.
- 경계가 벌어지거나 중복되지 않도록 주의해야 한다.
- 망라적이고 배타적인 분할이란, 누락도 중복도 없도록 분할하는 것으로서, 규칙이 모든 경우에 해당되고 모순이 없는 것을 말한다.
- 큰 문제를 여럿으로 나눌 때, 망라적으로 배타적으로 분할하라.
- if 문은 명제를 이용해 문제를 분할하는 명령이다. if ... else ... 문은 망라적이고 배타적인 분할이다.
- 논리의 기본은 둘로 나누기. if 문을 작성할 때마다 망라와 배타를 의식해야 한다.
- 부정(not):
~A - 부정의 부정:
~~A = A - 논리곱(and):
A∧B - 논리합(or):
A∨B - 논리곱의 부정은 부정의 논리합과 같다:
~(A∨B) = (~A) ∨ (~B)(배타적 논리합) - 배타적 논리합(xor):
A⊕B(A와 B가 다를 때만 참) - 등치(equal):
A=B - 배타적 논리합의 부정은 등치와 같다:
(~(A⊕B)) = (A=B) - 진리표와 벤 다이어그램을 이용하면 좀 더 쉽게 이해할 수 있고, 규칙을 발견하는 데도 도움이 된다.
- 항진 명제: A와 B의 참/거짓에 관계없이 언제나 참인 명제.
- 조건 명제(함의): A라면 B.
A ⇒ B - 조건 명제에서, A가 참이면 B도 참이어야만 참이다.
- 조건 명제에서, A가 거짓이면 B는 참이든 거짓이든 관계없다.
- A라면 B다. = A가 아니거나 B다.
(A ⇒ B) = ((~A) ∨ B) - 역:
A ⇒ B의 역은B ⇒ A. - 역이 참이라고 명제가 반드시 참인 것은 아니다.
(A ⇒ B) = B ⇒ A - 대우:
(~B) ⇒ (~A)B가 아니면 A도 아니다.
- A, B 두 명제가 각각 true, false를 취할 수 있으므로 가능한 경우의 수는 4.
- 두 명제의 연산으로 가능한 경우의 수도 4.
- 그러므로 두 명제의 연산으로 나타낼 수 있는 경우의 수를 조합하면
2^4 = 16 - A, B 두 연산으로 모든 연산의 진리표를 나타내면 0 - 15의 2진수의 표가 된다.
(~A) ∨ (~B) = ~(A ∧ B): A가 아니거나 B가 아닌 것은 A이면서 B가 아닌 것과 같다.(~A) ∧ (~B) = ~(A ∨ B): A가 아니고 B가 아닌 것은 A이거나 B인 것이 아닌 것과 같다.- 쌍대성: 논리식 안의 true와 false를 전환하고, ∨와 ∧를 전환하면 그 논리식 전체의 부정이 된다.
- 복잡한 논리식을 정리하는 도구
- 규칙을 정리할 때는 머리로만 생각하지 말고 논리식을 사용해라!
- 모든 명제의 참/거짓 조합을 2차원 그림으로 나타낸다.
- 그림에서 연속된 그룹을 뽑아내어, 논리식을 정리한다.
- 정의되지 않은 값. undefined
- 프로그래밍에서는 true, false 외에도 undefined 가 자주 사용된다.
- 조건 논리곱, 조건 논리합, 3값 논리 부정은 프로그래밍의 논리 연산과 동일.
- 조건 논리곱(&&)
- 조건 논리합(||)
- 부정(!)
- 드 모르간 법칙: 3값 논리에서도 적용된다.
- 논리식, 진리표, 벤 다이어그램, 카르노 맵을 이용하면 복잡한 논리를 꼼꼼하게 확인하고 간단하게 정리할 수 있다.
- 논리에서는 망라적이고 배타적인 분할이 매우 중요하다.
- 나머지는 그룹 나누기다. 그룹 나누기를 통해 어려운 문제를 손쉽게 풀 수 있는 경우가 있다.
- 몇가지 퀴즈를 통해 나머지-그룹 나누기를 알아봄.
- 100일 후의 요일은?
- 100일 후의 요일 == 7 % 100 일 후의 요일
- 7일마다 같은 요일이 반복되므로 나머지를 구해 요일을 계산할 수 있다.
- 10 ^ 100 일 후의 요일은?
- (10 ^ 100) % 7 을 계산할 수 있을까? (책의 서술상으로는 안된다는 거지만 사실 파이썬으로 계산하면 바로 계산되긴 한다.)
- 10 ^ n 일의 요일이 반복되는 규칙을 조사한 후, 10 ^ n 일 후의 요일을 계산하여 구한다. (로그를 사용한 방법이라고 한다)
- 큰 수를 다룰 때는 주기성을 알아내는 것이 중요하다. 주기성을 발견하면, 나머지를 이용해 활용할 수 있다.
- 1234567 ^ 987654321 의 1의 자리는?
- 이건 진짜 파이썬으로 계산해도 무진장 오래 걸린다.
- 풀이: 1의 자리에 영향을 주는 수는 1의 자리 수 뿐이다. 따라서 7만 거듭제곱해도 답을 구할 수 있다. 7 ^ n을 계산하여 주기성을 발견할 수 있다.
- 내 생각: 주기성을 발견한 후 나머지를 사용하는 것은 어려운 일이 아니지만, 주기성을 찾는 자체는 경험과 수학적 통찰이 필요해보인다. 잘못된 주기성을 찾는 오류를 범할 수도 있겠다.
- 추가하는 돌의 색을 이용해 정보를 전달하는 트릭. 최소한의 양의 데이터에, 미리 약속한 규칙을 이용하여 정보를 함축하여 전달했구나. 정보를 가공해 두었다고 볼수도.
- 패리티 검사: 조수(송신자)가 놓은 돌(패리티 비트)을 이용해 마술사(수신자)가 중간에 잡음(관객의 돌 뒤집음)이 발생했는지 확인. 통신오류 확인에 활용.
- 내 생각: 노이즈가 짝수회만큼 발생했다면 오류가 발생했음에도 패리티 검사를 통과할 수 있을텐데, 패리티 검사는 과연 신뢰성이 있는 검사인가? 또, 오류가 발생했다는 사실을 알 수 있을 뿐 오류내용은 알 수 없다.
- 또 페이크 문제... ㅠㅠ 졸라 확률게산에 겁먹고 있는데 알고보니!
- 확률/길이 아니라 도착한 장소를 기준으로 생각해보면 비교적 쉽게 해결. 마을을 짝수 마을 / 홀수 마을로 분류
- 그런데 이 문제가 왜 패리티 확인 문제인지는 확실히 모르겠다 (1)
- 이제 패턴도 제법 익혔겠다. 이번엔 당하지 않겠다.
- 어라. 이런건 평소에 많이 생각해본 문제인데. 당연히 못 까는건데. 이유는 어떠헥 설명해야 하지?
- 헐 풀이가 기발하다. 이번에도 스스로 못 풀었다.
- 그런데 이 문제가 왜 패리티 확인 문제인지는 확실히 모르겠다 (2)
- 이 문제를 푸는법은 이미 알고 있었다. "오일러가 알려주는 최적화 이론"이라는 책에서 봤다.
- 그래프에서 모든 간선을 중복없이 통과하려면 1) 모든 노드에 연결된 간선이 짝수개여야 한다. 또는 2) 연결된 간선이 홀수인 노드가 2개, 나머지 노드는 연결된 간선이 짝수개여야 한다.
- 오일러의 아이디어: 노드의 간선 개수 자체보다 그 홀짝에 주목. (패리티 확인)
- 주기성을 찾아내면 나머지 계산으로 문제 해결할 수 있다.
- 나머지 계산값으로 group-by 할 수 있다.
- 홀짝성(패리티) 검사를 통해 오류 검사를 하거나 문제를 훑어볼 수 있다.
- 문제 전체를 면밀히 검토하지 않고 적절히 훑어보는 것이 더 올바른 해결법인 경우도 있다.
귀납법을 통한 증명과 반복
1 .. n의 값을 더하는 방법은 그 대칭인n .. 1의 값을 더하는 것과 같다. 이제 이 대칭의 각 쌍을 각각 더한다.1 + n, 2 + n - 1, .., n + 1의 값은 모두n + 1으로 동일하다. 그러므로1 .. n의 값을 더하려면n + 1을 n/2 만큼 곱하면 된다.- 이 방법을 일반화하면
1 + 2 + .. + n = (n+1)*n/2이다. - 이 일반화한 식이 0이상의 모든 정수에 성립함을 증명하려면? 수학적 귀납법이 딱이다.
- 주장:
P(n): n은 자연수다.와 같은 식으로 0 이상의 정수 n에 대한 주장 P를 나타낸다. - 수학적 귀납법은 정수에 관한 주장을 0 이상의 모든 정수에 대해 증명할 때 이용한다.
- 기저(base,
P(0))와 귀납(indution,P(k) -> P(k + 1)) 두 단계가 성립함을 증명함으로써, 0 이상의 모든 정수에 주장이 증명함을 증명할 수 있다. - 가우스 소년의 주장, 홀수의 합, 오셀로 퀴즈의 증명은 증명과정을 직접 따라하며 확인해보는 편이 좋은 것 같다. 대충 보면 이해 안 된다.
- 내 생각에 증명을 스스로 유도하려고 할 필요는 없는 것 같다. 똑똑하면 그렇게 할 수도 있겠지만 책에 나오는 증명과정은 수학자들이 연구해서 만들어둔 것들 아닐까. 그걸 잘 따라해보고 확인해보는 것만 해도 공부다.
- 그림을 활용하면 좀더 쉽게 설명하는 것도 가능하다. 하지만 그림에는 함정이 있을 수 있다.
- 그림을 이용한 증명이 위험한 경우.
- 그림 4-5는 T(1)에서는 적용될 수 없는 그림이다.
- 답을 보지 않은 채로 10분 정도 고민해 봤지만, 답을 알 수 없었다. ^^;
- 프로그래밍의 반복 패턴이 올바르게 동작한다는 것을 증명(assert)하고 싶다면 수학적 귀납법을 사용할 수 있다.
- 이 부분도 눈으로만 보지 말고 코드를 직접 읽어봐야 이해가 됨.
- 내 주장: 반복 패턴(for, 그리고 전형적인 while 패턴)과 재귀 호출 함수는 수학적 귀납법을 프로그래밍 언어로 구현한 것이다. (재귀는 6장에서 다시 나옴)
- 수학적 귀납법은 0 이상의 모든 정수 n에 대해 어떤 주장이 성립함을 증명하는 방법. 단 2 단계의 증명만으로 무한한 범위의 주장을 증명할 수 있다.
- 수학적 귀납법은 프로그래밍의 반복 패턴의 증명이기도 하다. 수학적 귀납법을 사고방식으로 체득하면 반복 패턴을 짤 때 도움이 된다.
- 수를 세는 방법. 빠지지 않고 겹치지 않게.
- 센다는 것은 정수와 대응하는 것
- 수를 세는 법칙: 덧셈 법칙, 곱셈 법칙, 치환, 순열, 조합
- 세는 것은 셀 대상을 정수에 대응하는 행위
- 누락: 셀 것을 빠트리는 것
- 중복: 이미 센 것을 다시 세는 것
- 누락과 중복이 없어야 완벽하게 센 것이다.
- 나무 세기 문제에서 출발점(0)을 잊는 실수를 하기 쉽다. 이 실수를 예방하기 위해 종이에 그려보는 것이 좋은 방법이다.
- n개의 데이터에 0번부터 번호를 붙이면 마지막 데이터의 번호는 n-1번이 된다. k개째 데이터의 번호는 k-1번이다.
- 세려는 대상의 성질을 파악하는 것이 중요하다.
- 덧셈 법칙: 중복이 없는 두 집합의 합집합의 개수.
|A∪B| = |A|+|B|
- 집합 원소에 중복이 있으면 덧셈 법칙은 성립하지 않는다.
- 두 집합에 중복이 있는 경우에는 합집합의 개수에서 교집합의 원소 개수만큼 뺀다.
|A∪B| = |A|+|B|-|A∩B|- "중복된 것의 개수는 몇 개인가?"(셀 대상의 성질)를 파악해야 한다.
- 두 개의 집합에서 원소의 짝을 만들 때 사용
- 집합 A의 모든 원소와 집합 B의 모든 원소를 각각 짝으로 만들 때, 짝의 전체 개수는 양 집합의 원소 수를 곱한 것이 된다.
|A×B| = |A|×|B|- 파이썬에서 데카르트 곱(cartesian product) 구하기:
import itertools; itertools.product(s1, s2, ...)
- 치환(substitution): 대상을 순서를 구별하여 나열하는 것
- n개의 대상일 때, 1번째에 선택할 수 있는 것은 n가지, 2번째는 n-1가지, ..., n번째는 1가지
- 계승(factorial):
n! = n * n-1 * ... * 1 - 파이썬에서 계승 계산:
import math; math.factorial(n) - 0의 계승은 1로 정의.
0! = 1 - n개의 대상을 치환하는 방법의 수:
n!
- 순열(permutation): 대상 중 일부를 선택하여 나열하는 것
- 치환과 같이 순서를 구별하여 나열한다. (순열: 순서 있는 나열)
- n개의 대상에서 k개를 선택할 때, 1번째에 선택할 수 있는 것은 n가지, 2번째는 n-1가지, ..., k번째에 선택할 수 있는 것은 n-k+1가지
- 0 부터 k-1까지를 n에서 각각 빼서, 전체를 곱한 것. 프로그래머 입장에서는 이렇게 생각하니 좀더 이해하기 쉽다.
- n개의 대상에서 k개 선택하는 방법의 수:
nPk = n-0 * n-1 * n-2 * ... * n-(k-1)또는,n! / (n-k)! - 계승으로 표현한 일반식:
n! / (n-k)!. 일단 다 곱한 다음 불필요한 것을 나누어 없애는 방식
- 트리 방식으로 그려보면 선택지가 단계마다 줄어드는 것을 눈으로 확인할 수 있다.
- 수형도는 '세고자 하는 물건의 성질을 파악하는 데' 많은 도움을 주는 도구
- 조합(combination): 순서를 생각하지 않고 선택
- n개에서 k개를 선택하는 방법. (n개의 원소를 갖는 집합에서 k개의 원소를 갖는 부분집합의 수)
- 순열의 수를 구한 뒤 중복해서 센 부분(중복도)으로 나누어, 조합의 수를 구할 수 있다.
- n개의 대상에서 k 크기로 조합하는 방법의 수:
nCk = nPk / kPk - 순열의 수: (n개의 대상에서 k개 선택하기)
nPk = n! / (n-k)! - 중복도: n개의 대상에서 k개를 선택할 때,
kPk = k! - 일반식:
nCk = n! / ((n-k)! * k!) - 직접 계산할 때는 일반식보다는
nCk = nPk / kPk가 구하기 편하다.
- 치환: 순서 바꾸기
- 조합: k개 선택하기
- 순열: 순서를 바꾸면서 k개 선택하기(치환 * 조합)
nCk * kPk = nPk(a.k.anCk = nPk / kPk)
- 칸 나누는 문제를 연상할 수 있어야...
- 앞을 조커로 고정하거나, 뒤를 조커로 고정하는 경우의 수?
- 중복을 찾아서 빼야 함? 양쪽이 다 조커인 경우 중복되는 것 같다
- 앞을 조커로 고정하는 경우의 수: 4!
- 뒤를 조커로 고정하는 경우의 수: 4!
- 양쪽이 조커인 경우의 수: 3!
- 계산해보자:
4! + 4! - 3! = 42 - 정답! 풀이 안보고 풀었다.
- 나무 세기, 덧셈 법칙, 곰셈 법칙, 치환, 순열, 조합
- 법칙의 의미를 이해하는 것이 중요하다.
- 세고자 하는 대상의 성질을 잘 파악해야 한다.
- 세지 않고 답을 구할 수 있어야 한다.
- 자기 자신을 사용하여 자신을 정의
- 작은 하노이의 탑부터 풀어본다
- '비슷한 동작을 반복하는 것 같은데?' -> 패턴을 발견하는 감각
- 패턴 발견: 하노이 원반 하나 옮길 때마다 전 단계의 하노이 퀴즈 풀기를 수행해야 한다.
- 해법 서술: n 하노이 풀기
- n = 0: 완료
- n > 0: n-1 하노이 풀기 수행 -> 밑바닥 원반 1장을 옮김 -> n-1 하노이 풀기 수행
- 하노이 푸는 횟수:
H(n) = H(n-1) + 1 + H(n-1) - 이 식을 점화식(recursive relation, recurrence)이라고 부름
- 점화식을 이용해 구한 값을 이용해 H(n)의 수열을 구할 수 있다. 이 수열을 생성하는 식을 H(n)의 닫힌 식(closed-form expression)이라 한다.
- 닫힌 식은 파이썬의 시퀀스 해석 또는 제너레이터와 비슷하게 느껴진다.
# 책의 코드를 파이썬으로 포팅한 버전
def hanoi(n, x, y, z):
if n == 0:
pass
else:
hanoi(n-1, x, z, y)
print(x + "->" + y)
hanoi(n-1, z, y, x)
# 내가 만든 버전
def hanoi2_step(n, stacks, move_from, move_to, move_using):
if n == 0:
pass
else:
hanoi2_step(n-1, stacks, move_from, move_using, move_to)
print(stacks, end=' ') # 이동 전
print(move_from + ' => ' + move_to, end=' ')
stacks[move_from] -= 1; stacks[move_to] += 1
print(stacks) # 이동 후
hanoi2_step(n-1, stacks, move_using, move_to, move_from)
def hanoi2(n):
hanoi2_step(n, {'x': n, 'y': 0, 'z': 0}, 'x', 'y', 'z')
- 재귀를 사용한 표현: H(n)을 H(n-1)을 이용해 푸는 방법을 표현
- 점화식: H(n)의 결과값을 H(n-1)의 결과값을 이용해 표현
- 재귀적 사고방식: "한 단계 작은 문제를 이용하여 큰 문제를 표현할 수는 없을까?" 문제 안에서 재귀적 구조 찾아내기
- 재귀적 구조에서 점화식까지 찾아다면 좋다.
-
계승(factorial)을 재귀적으로 정의할 수 있다.
n! = n=0: 1 (a.k.a. 0! = 1) n>0: n * (n-1)!
-
0 .. n(0 이상의 수)의 합을 재귀적으로 정의할 수 있다.
S(n) = n=0: 0 n>0: n + S(n-1)
-
이를 닫힌 식으로 나타내면:
S(n) = n * (n+1) / 2(가우스 소년의 풀이법)
- 계승의 재귀적 정의는 수학적 귀납법과 닮았다. n=0 은 기저, n>0은 귀납에 해당.
- 재귀와 귀납은 모두 큰 문제를 같은 형태의 작은 문제로 만든다는 점에서 본질적으로 같다.
- 재귀와 귀납은 생각하는 방향이 다를 뿐이다. (재귀: 큰 문제에서 작은 문제로, 귀납: 작은 문제에서 큰 문제로)
-
피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 순으로 나열된 수열. 수열의 한 수는 바로 앞의 두 수를 더한 수.
-
피보나치 수열도 재귀적으로 정의할 수 있다. 단, '앞의 두 수'가 필요하기 때문에 fib(0)과 fib(1)을 둘 다 정의해 주어야 한다.
fib(n) = n=0: 0 n=1: 1 n>1: fib(n-1) + fib(n-2)
-
피보나치 수열은 다양한 문제에서 발견될 수 있다. 늘어나는 생물 퀴즈, 벽돌 나열하는 방법의 조합, 리듬 조합 등. (이게 피보나치 수열로 해결할 수 있는 문제란 걸 어떻게 알 수 있을까?)
- 이웃한 두 수를 더해 다음 단계(아래줄)에 쓰는 과정을 반복한 것
- 파스칼 삼각형의 각 수는 n개의 k개 조합(
nCk)으로 나타낼 수 있다. 원점에서 도착지까지 도달할 수 있는 길의 종류이기 때문.
-
파스칼의 삼각형의 수를 계산하는 식:
nCk = n-1Ck-1 + n-1Ck -
재귀적으로 정의할 수 있다.
nCk = n=0 or n=k: 1 0<k<n: n-1Ck-1 + n-1Ck
- 조합에 대한 식을 단순한 수식이 아니라, 조합론적 의미를 발견하는 것.
- nCk: n장에서 k장을 선택하는 조합
- n-1Ck-1: 특정 카드를 선택한 후, 나머지(n-1)에서 k-1장 선택하는 조합
- n-1Ck: 특정 카드를 선택하지 않고, 나머지(n-1)에서 k장 선택하는 조합
- 단계 n의 문제 일부를 떼어 낸다
- 남은 부분이 단계 n-1의 문제인지 아닌지 조사한다
- 프랙털 도형: 재귀적 구조를 가진 도형
-
단계 n의 나무는 두 개의 가지를 갖는데, 각 가지는 단계n-1인 나무다.
-
그려보기
import turtle
def init(speed='slowest'):
turtle.reset()
turtle.speed(speed)
turtle.left(90)
def drawtree(n, index=False, length=25, angle=20):
if n == 0:
pass
else:
if index:
turtle.write(str(n))
turtle.left(angle)
turtle.forward(length)
drawtree(n-1, index, length, angle)
turtle.back(length)
turtle.right(angle)
turtle.right(angle)
turtle.forward(length)
drawtree(n-1, index, length, angle)
turtle.back(length)
turtle.left(angle)
- n단계의 삼각형 안에 n-1 단계의 삼각형 세 개가 포함된 삼각형. (n+1 단계의 삼각형 세 개가 포함되었다고 봐야하는 것 아닌가?)
- 파스칼의 삼각형에서 홀짝을 구분해 색을 칠하면, 신기하게도 시어핀스키 개스킷 형태가 된다.
- 재귀적 구조를 발견해 재귀적 정의와 점화식을 유도할 수 있다.
- 재귀를 이용해 복잡한 문제를 간단한 기술로 해결할 수 있다.
- 들여쓰기 블록, 트리 구조, XML, 퀵 소트 등에서 재귀 구조를 발견할 수 있다.
형님 수학적 귀납법 사용해서 고등학교에서 발표하려고 하는데 주제 추천해 주세요...