1. 개요
1. 개요
| 이산수학 Discrete Mathematics | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" | 이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수(공식) · 순열(완전순열 · 염주순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 (예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
대한민국 수학 교육과정에서는, 시행착오법을 명시적으로 다루는 경우는 예상과 확인이 있다. 초등학교 수준에서 연립일차방정식 문제를 예상과 확인을 통해 접근하도록 교육하는 것이다. 이는 초등학생들이 대수적인 방식으로 연립일차방정식을 풀 수준이 되지 않으므로 시행착오를 통해 풀도록 하는 것이다. 물론 대놓고 연립일차방정식 문제를 주는 게 아니라, 문장제 형식으로 문제를 낸다. 동물의 다리 개수 래퍼토리는 거의 클리셰에 가깝다. 예상과 확인 참고.
그 외에는, 각종 기하학 문제,[1] 인수분해,[2] 수열의 귀납적 정의,[3] 허수 [math(i)]의 순환,[4] 나눗셈에서의 소수점 자리 순환,[5] 여러 경우를 생각한 후 모순되지 않는 경우를 찾아가는 '문제해결',[6] 자기상사도형을 이용한 무한등비급수의 합 구하기 문제[7] 따위에서 시행착오법을 사용하게 된다.
명시적으로 '시행착오로 접근하라'고 교과서에 나와 있는 경우도 있고 그렇지 않은 경우도 있다. 수학 공식과 같이, 시행착오가 아닌 접근법에 익숙해진 나머지 학습자는 시행착오를 통한 문제 해결을 간과하기도 한다. 시행착오법을 생각하지 못하여 이런 문제를 틀리고 풀이법을 알게 되면, '뭐야, 그냥 일일이 찔러 보는 거였어?'라는 허탈한 반응이 나오는 바로 그것이다. 이 때문에 시행착오법을 명시적으로 강조하는 교육을 해야 한다는 의견도 있다.
암호학에서는 브루트 포스, 사전 공격, 레인보우 테이블 등이 친숙할 것이다.
의외로 학문적으로도 통용되는 방법이며, 엄밀히 말하면 이산수학에서 말하는 방법론 중 하나이다. 이산수학인 이유는 연속[8]이 아닌 이산적인 대상을 다루기 때문이다.
이런 노가다는 주로 대학수학능력시험에서의 수열문제처럼 일정한 규칙은 있는데 그 규칙을 일반화하지는 못한 경우[9] 발생하게 된다. 또한 수학적인 사고와 정상적인 문제풀이 과정을 통해 규칙을 유추하고 답을 도출했다 하더라도 검산을 통해 그 답을 확신하기 위해서는 결국 노가다 내지는 역대입이 가장 확실하긴 하다. 실제로 가우스도 훗날 소수 정리라고 불리는 수학적 성질을 밝혀내기 위해서 매일 1,000개씩 소수를 찾아내서 자연로그에 집어넣기도 하였다.
또한 경우에 따라서는 공식에 대입해서 푸는 것보다 노가다를 약간 하는 것이 더 효율적일 수도 있다. 실제로 7차 교육과정 수학 1의 수능출제 매뉴얼에선 10항까지 축차대입해서 규칙성을 알 수 있는 문제가 출제범위다. 애초에 수능에서는 수험생이 태어나서 처음 보는 수열이 나오기 때문에, 정말 규칙을 모르겠다면 5~6항 정도까지는 계산을 반복하는 것도 나쁘지 않다.[10] 이때 자기가 숫자 계산 잘한다고 결과의 값만 옮겨 적을 게 아니라 식의 형태를 남겨 두는 게 포인트. 노가다 결과가 1+3+6+10+...이라면 규칙성을 발견하기 어렵지만 1+(1+2)+(1+2+3)+(1+2+3+4)+...와 같은 식으로 노가다를 해 나가다 보면 규칙성을 쉽게 발견할 수 있다.
사실 문제당 시간 제한이 촉박한 내신보다는 KMO 등의 수학경시(특히 조합영역)나 수능에서 굉장히 파워풀한 방법이다. 가장 효율적으로 경우의 누락 없이 노가다를 뛰는 방법을 중요하게 가르치기도 한다. 특히 정수 문제의 경우 어떤 방정식의 해가 정수로 한정되어 있기에 그 해의 범위를 구하고 그 안의 수들에 대해 전부 대입해보는 방법이 많이 사용되며, 조합도 각각의 경우를 효율적으로 찾는 방법을 가르치는 경우가 많다.
한 경험자의 말에 따르면, "더블 카운팅? 트리? 점화식? 스털링 수? 다 필요없어. NGD 하나면 된다." 라고 한다.[11][12]
쉽게 말하자면 [math(5\times 8=40)]이라는 공식을 [math(5+5+5+5+5+5+5+5=40)] 이런 식으로 계산하는 방식이다.
또한 수능 수학 영역에서도 이따끔 볼 수 있는데, 대개 주관식 첫 문항인 21번이나 마지막 문항인 30번에서 종종 보인다. 예로는 2014년 9평 B형 21번[13], 2019년 6평 나형 30번[14], 2019년 6월 전국연합학력평가 고2 수학 가형 30번[15]등이 있다.
물론 위의 그림처럼 하느니 그냥 공부 좀 해서 규칙을 파악할 수 있는 능력을 습득하는 게 훨씬 좋다. 저렇게 일일이 계산해서 확인해 보는 것도 필요하다면 필요한 짓이겠지만 그러려면 뭐 때문에 수열이니 뭐니 하는 것을 공부하겠는가. 사람은 컴퓨터가 아니니 저 미친 듯한 양의 노가다를 안 하려고 공부하는 거다.
컴퓨터의 등장 이후 컴퓨터가 실제로 노가다로 계산을 해서 미해결문제를 증명하는 일이 나타나고 있다. 최초로 컴퓨터의 노가다 증명이 인정 받은 것은 4색정리이며, 이를 계기로 계속 증가하고 있다. 골드바흐의 약한 추측도 1030보다 큰 수에서 성립한다는 것이 확인되자, 7부터 1030까지는 그냥 컴퓨터 돌려서 해결했다. 물론 이것도 엄연히 수학적인 증명으로 인정받는다. 다른 조건 없이 계속해서 점점 큰 수를 넣는 것이었다면 그 범위가 무한하니 절대로 인정받지 못하겠지만[16], 이 경우는 1030부터는 연역적 방법을 통해 증명이 끝난 상황이라 대입이 필요한 수의 범위가 유한하기 때문에 인정이 된 것이다.
한편 이것을 해킹 기법으로 발전시킨 것이 무차별 대입 공격(Brute Force Attack)으로, 정답이 나올 때까지 모든 수를 다 찍는 것이다. 주로 복호화가 되지 않는 해시 함수가 공격 목표가 되는 편이며 불행히도 MD5는 이미 뚫린 지 오래며, SHA도 현 시점에서는 SHA-3을 제외하면 모두 털린 상태라고 한다.
다만 이런 "노가다"조차도 무의미한 수학적 대상이 있는데, 바쁜 비버가 대표적이다.
[1] 보조선을 그어야만 해결할 수 있는 문제가 대표적이다. '왜 꼭 거기에 그런 식으로 보조선을 그어야 하는가?'라고 물어보면 '그렇게 해야 답이 나오니까!'라고밖에 말할 수 없다. '그래서 보조선을 그렇게 그으면 답이 나온다는 건 어떻게 아느냐?'라고 물어보면 '그냥 그건 감으로 때려맞히는 것'이라는 궁색한 대답이 불가피하다. 르네 데카르트는 바로 이런 점 때문에 기하학에 흥미를 잃고 대수학에 관심을 기울였다.[2] 인수분해를 하기 위해서는 다항식의 인수를 찾아야 하는데, 이것은 직감과 시행착오를 거칠 수밖에 없다.[3] 어떤 수열의 귀납적 정의를 보고, 식의 형태에 따라 수열의 일반항을 도출하는 테크닉이 조금씩 다르기 때문에, 어떤 방법을 써야 할지는 시행착오를 통해 알게 된다.[4] 어떤 수에 [math(i)]를 네 번 곱하면 원래 수로 돌아오는 것 따위가 있다. 꼭 [math(i)]가 아니어도 주기가 4가 아니라 8인 복소수가 문제로 나오기도 한다. 주기가 몇인지 알기 위해서는 시행착오를 거쳐야 한다.[5] 예를 들어 1÷7을 하면 0.142857142857...이 되는데, 142857이 순환한다는 것을 알기 위해서는 시행착오를 거쳐야만 한다. 즉, 계속해서 직접 계산을 해보며 어떤 순환이 일어나는지 알아내야 한다. 직접 나눗셈을 해보지 않고 1÷7의 순환마디를 알아내는 별도의 방법이란 없다.[6] 이를테면 어떤 문제에서 '[math(k<3)]([math(k)]는 자연수)'이라는 사실을 알아낸 다음, [math(k=1)]인 경우와 [math(k=2)]인 경우로 나눈 후, 전자는 모종의 모순이 발생하고 후자는 그렇지 않다는 점에서 [math(k=2)]로 결정하고 문제를 풀어 가는 것 등이 있다. 대학수학능력시험의 '문제해결' 문제에서 자주 보이는 유형. 이런 경우 [math(k=1)]일지 [math(k=2)]일지는 직접 따져봐야만 알 수 있다.[7] 다름 아닌 모의고사나 대학수학능력시험 수학 나형에서 17~19번쯤에 꼭 나오는 4점짜리 문제. 어떻게 해야 색칠된 부분의 넓이나 지정된 길이를 구할 수 있을지는 순전히 직감과 시행착오로 알게 된다.[8] 연속함수에서 말하는 그 연속이다.[9] 이런 것들을 평가원 용어로 발견적 추론이라고 한다.[10] 대부분 수열파트는 4항까지 해보면 등차수열인지 등비수열인지 계차수열인지는 극명해진다. 조화수열은 아예 생김새가 달라서 잘 나오지 않는다.[11] 그런데 저런 방법을 사용하기엔, 특히 스털링 수의 경우 나오는 경우가 너무 적어서 차라리 노가다를 연습하는게 효율적일 수도 있다. 이쪽은 노가다를 너무 등한시하고 기피하면 오히려 더 문제가 되는 케이스다.[12] 심지어 학력평가 기출문제 중에는 방정식 [math(2^a=a+12)]의 양수해를 구하는 문제가 나온 적이 있는데, 이 꼴의 방정식은 필연적으로 람베르트 W 함수를 이용해야 한다. 그런데 이 함수는 고등학교 과정에서는 아예 가르치지 않는 초월함수다. 그래서 고등학생은 노가다 말고는 선택지가 없다. 참고로 답은 꼴랑 4. 1부터 때려넣어가면 4번만에 나온다.[13] 뭔가 특별한 발상이 필요한 게 아니라 매개변수 도함수에 3,4,5,6을 각각 대입해서 그래프를 전부 다 그리고 극점을 전부 다 찾아야 한다. 그래도 그렇게만 하면 답이 어렵지 않게 나오기 때문에 정답률은 40%대로 꽤 높다.[14] 문과수학 최강의 노가다 문제로 꼽힌다. 그나마 발상을 잘 해서 f(x)의 함숫값을 몇 개 구해 놓으면 8번 정도만 시도해 보면 되지만, 그렇지 않다면 60개가 넘는 케이스를 하나 빼고 전부 다 모순을 밝혀내야 한다. 정답률은 무려 1.5%. 사실 이마저도 모든 경우의수에 대한 정확한 모순검증없이 답이 되는 케이스를 찾아서 해결한 경우가 많다.[15] 모든 수능문제를 통틀어 최악의 난이도를 자랑하며 2017~2018학년도 수능 가형 30번, 2019학년도 6월 모의평가 가형 21번 등 그 어떤 킬러문제를 가져와도 이보단 훨씬 쉽다. 그냥 문제를 직접 보도록 하자. 오답률은 100%이다. 99.5%가 넘어가서 저렇게 된 것. 정답은 359(최초 답안), 152(답안 변경 후)로, 어지간해선 찍어서 맞추기도 힘든 숫자다.(만점자 5명) 여기에 해설지에 풀이 과정과 답이 실제 경우의 수보다 적게 적힌 바람에 뒤늦게 정답과 해설을 변경하고 채점을 다시 진행했다. 해설 강의를 보면 경우의 수가 사람의 손으로는 도저히 계산할 수 없어서 컴퓨터 매크로를 돌려서 해결하는 등 그야말로 총체적 난국이다. 더 끔찍한 사실은 이 문제는 고2용 문제였다!! 고3도 시간안에 못 풀 문제를 고2에게 던졌다! 고2 시험이라 덜 알려졌을 뿐. 여담으로 저 문제도 기출이랍시고 고2용 학평기출문제집에 들어있는 경우가 많으니 저 문제를 보면 필히 넘기길 권한다. 못 풀었다고 좌절할 필요도 없다. 애초에 사람이 100분 안에 못 푸는 문제이다.[16] 리만 가설과 스큐스 수에서도 확인할 수 있듯이, 큰 수의 세계에서는 상상도 할 수 없는 일이 일어나곤 한다. 종래에는 로그 적분 함수(로그함수의 역수를 적분한 함수)가 소수 계량 함수보다 항상 클 것이라고 예상했었고, 사람들이 계산할 수 있는 정도로 큰 수에서는 그것이 사실이었으나, 스큐스 수를 기준으로 로그 적분 함수와 소수 계량 함수의 대소 관계가 역전되며, 심지어 대소 관계가 무한히 역전을 거듭한다! 최초로 계산된 스큐스 수는 [math(10^{10^{10^{34}}})] 정도. 매우 큰 값의 수에서는 어떠한 일이 일어날지 확인할 수 없으며, 귀납법의 가장 치명적이고 원시적인 약점이기도 하다. 초월수 인정이 어려운 이유 중 하나이기도 하다.