|
이산수학 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. 개요
경우의 수(境遇-數, number of cases)는 조합론과 확률론의 개념으로, 1회의 시행에서 미래에 일어날 수 있는 사건의 가짓수([math( n )])를 가리킨다. 합의 법칙과 곱의 법칙은 여러 개의 사건이 일어날 때 경우의 수를 따지는 방법으로 여러 유형으로 나뉜 순열, 조합 등도 사실 이 두 기본 원리를 바탕으로 하고 있다.2. 사건의 동시성
‘동시성’이라는 용어는, 현실적으로 동시에 일어나는 사건은 아니므로 용어 그 자체로 받아들여야 한다. 예를 들어 3개의 갈림길을 지나 다시 2개의 갈림길중 하나를 선택하라고 요구할 경우, 분명 동시에 일어나지 않지만 동시성의 아이디어를 써야 한다. 동시성이 발견되면 아래에 설명된 곱의 법칙을 사용해야 한다.3. 합의 법칙
서로 동시에 일어나지 않는 두 사건 [math( A )], [math( B )]에 대하여 사건 [math( A )]가 일어나는 경우의 수가 [math( m )]가지, 사건 [math( B )]가 일어나는 경우의 수는 [math( n )]가지라면 [math( A )] 또는 [math( B )] 중 어느 쪽이라도 일어나는 경우의 수는 [math( m+n )] 가지다.집합으로 표현하면 [math(A\cap B = \varnothing)]인 경우 두 사건 [math( A )], [math( B )]는 동시에 일어나지 않으므로 합집합 [math(A\cup B)]의 전체 원소의 개수는 [math(n(A) + n(B))]임으로 나타낼 수 있다.
예를 들자면, 주사위의 눈이 2 또는 5가 나올 경우의 수를 생각하면 된다. 주사위의 눈이 2 또는 5가 나오면 되므로 2가 나올 경우의 수 1가지와 5가 나올 경우의 수 1가지를 더하여 2가지가 나온다. [math( 1 + 1 = 2 )]
여러 사건들이 영향을 주거나 일어나는 상황 구조가 닮지 않고 다른 경우, 경우의 수를 쪼개서 계산하게 된다. '또는', '~이거나', ‘or’라는 표현을 사용한다면 합의 법칙 문제이다. 사건의 수에 따라 산술급수적으로 커진다.
아래의 곱의 법칙은 익숙해지다 보면 오히려 눈에 보이는 경우가 잦은데, 이 합의 법칙은 곱의 법칙이 아님을 눈치채야 하는 영역에 가깝기 때문에 사실 곱의 법칙보다 파악하기가 만만치가 않다.
합의 법칙이 적용되는 상태는 주어진 조건들이 ’완료‘된 사건을 모은다고 생각하면 된다. 정확한 개념은 아니지만 끝난 사건끼리는 더한다고 생각하자.
4. 곱의 법칙
서로 동시에 일어날 수 있는 두 사건 [math( A )], [math( B )]에 대하여 사건 [math( A )]가 일어나는 경우의 수가 [math( m )]가지, 사건 [math( B )]가 일어나는 경우의 수는 [math( n )]가지라면 [math( A )]와 [math( B )]가 동시에 일어나는 경우의 수는 [math( m \times n )] 가지다.집합으로 표현하면 집합 [math(A)]의 각 원소마다 집합 [math(B)]의 원소 각각에 하나씩 대응시켜 짝을 짓는 순서쌍의 개수는 [math(n(A) × n(B))]임으로 나타낼 수 있다.
예를 들자면, 곱의 법칙은 주사위를 두 번 던져 처음엔 짝수가 나오고 그 다음 홀수가 나올 경우의 수를 생각하면 된다. 처음에 짝수가 나올 경우의 수 3가지(2, 4, 6)에 두번째 홀수가 나올 경우의 수 3가지(1, 3, 5)를 곱하면 9가지이다. [math( 3\times 3 = 9 )]
여러 사건들이 서로 영향을 주지 않거나 일어나는 상황 구조가 닮은 경우, 경우의 수를 뭉쳐서 계산하게 된다. ‘and’가 곱의 법칙이다. 사건의 수에 따라 기하급수적으로 커진다.
곱의 법칙은 “진행 중”인 사건들을 할 때 쓴다. 순서가 있어서 한 사건이 끝나려면 여러가지 단계를 거쳐야 할 때 각 단계에서 나오는 경우의 수를 전부 곱한다.
4.1. 순열
4.2. 조합
4.3. 분할
5. 관련 공식
6. 교과 관련
대한민국 수학 교육과정에서는 2022 개정 교육과정 기준으로 중학교 2학년에서 처음으로 배운다. 이후 고등학교 과정에서 고등학교 1학년 공통수학1과 고2·3 일반 선택 과목 확률과 통계에서 다룬다. 한편, 과학계열 진로 선택 과목에서는 이산 수학에서 ‘선택과 배열’이라는 단원명으로 다룬다.‘경우의 수’ 단원은 교과서 내용 자체만 보면 별 거 없어서 일별 넘기기 일쑤지만, 다양한 문제를 통해 학습해야 그 진가가 드러난다. 특히 생각하는 힘을 키워 주는 데 용이하기 때문에 교육공학적인 목적과 사실상 가장 많이 부합한다. 수능 및 모의평가/모의고사에서 출제되는 22번, 30번 등의 고난도 문항에서는 경우를 분류하여 문제의 조건을 모두 만족시키는 경우만을 골라내는 추론 능력이 중요시되는데, 특정 기준에 따라서 경우를 분류하는 능력, 그 기준을 무엇으로 할 것인지에 대한 감각 등을 이 경우의 수 단원을 통해 기를 수 있다.
한때 2022 수능부터 선택 체제로 바뀐 후로는 자연계 진학자들의 동향이 미적분 선택으로 편향되는 바람에, 안 그래도 약했던 분야[1]가 더 약화되지 않겠냐는 수학계의 우려도 있었다.
합의 법칙, 곱의 법칙에는 법칙이라는 이름을 붙이기 어색할 수도 있지만 결정적으로 중요한 내용이라는 것을 깨달을 수 있다. 순수 경우의 수 문제가 아니더라도 수능 수학, 과장 보태면 과학에서도 용이하게 활용될 때가 있다. 특수한 상황이 제시되면 결국 상황을 많이 복잡하게 만들 뿐이기 때문인데, 이때 상황을 최대한 단순화시킨 후 각각의 케이스에 대해서 곱의 법칙으로 뭉친 항들을 곱하는 것이나, 상황이 여의치 않거나 단순하게 해결할 수 있다면 합의 법칙으로 해결하는 것도 나쁘지 않다.
7. 실생활 예시
- 동전 던지기: 앞면, 뒷면 2가지 가운데 하나가 나올 수 있으므로 경우의 수는 2이다.
- 가위 바위 보
- 가위, 바위, 보 가운데 1가지가 나오게 된다. 경우의 수는 3이다.
- 2명이 가위 바위 보를 한다면, 곱의 법칙이 적용되어 [math( 3\times 3 = 9 )] 가지의 경우의 수가 나오게 된다.
-
윷놀이:
결과를 기준으로 생각한다면 도, 개, 걸, 윷, 모 5가지 가운데 1가지가 나올 수 있으므로 경우의 수는 5이다.
확률 계산 시에는 4개의 윷가락을 사용하고 각각의 윷가락이 앞뒤가 존재하는 것을 감안하여 [math( 2^{4} = 16 )]가지의 경우의 수가 존재한다. 도/개/걸/윷/모가 나올 수 있는 확률은 다음과 같다. 단, 윷가락이 뒤집어질 확률과 엎어질 확률은 1:1로 같다고 가정한다.
도, 걸 [math( \displaystyle \frac{1}{4} )]
도(백도 제외) [math( \displaystyle \frac{3}{16} )]
개 [math( \displaystyle \frac{3}{8} )]
윷, 모, (백도) [math( \displaystyle \frac{1}{16} )]
다만 물리학적으로 실제 윷가락은 곡면이 아래로 오기 힘드므로 모→백도→윷으로 갈수록 확률이 낮아진다고 보면 된다. - 주사위: 6면체 주사위는 1~6의 자연수로 된 눈 가운데 1가지가 나오게 되며, 경우의 수는 6이다.
- 야구의 사이클링 히트: 단타, 2루타, 3루타, 홈런 모두를 쳐야 나올 수 있는데, 중복을 제외하고 경우의 수는 24(4!)이다.
- 수능 탐구 영역: 사회탐구 영역은 36가지 (과목이 9개이므로), 과학탐구 영역은 28가지 (과목이 8개이므로), 직업탐구 영역은 45가지 (과목이 10개이므로)의 경우의 수가 나온다. 2014년에는 국어 영역, 수학 영역, 영어 영역의 A/B형 고르기에서도 경우의 수가 사용되었으며, 이 경우는 6가지. 원래대로라면 [math( 2^{3} )]이므로 8가지가 맞겠지만 국어와 수학은 동시에 B형을 선택할 수 없으므로 국어와 수학을 모두 B형으로 고른 경우 (BBA, BBB)를 제외해서 6가지(AAA, AAB, ABA, ABB, BAA, BAB)가 되었으며, 2015년과 2016년에는 영어가 폐지된 이후에는 3가지로 줄어들었으며, 2021년까지는 수학만 가/나형, B/A형(수학은 가형과 B형이 자연계열, 나형과 A형이 인문계열이다.)으로 나누므로 2가지다. 2022년 이후에는 국어와 수학에 선택과목이 생겨 6가지로 늘어나고 사회, 과학탐구 영역의 계열 구분이 사라져 136가지로 대폭 늘어나지만 직업탐구는 5가지로 줄어든다. 현재 수능 과목 조합의 경우의 수는 하나만 있는 영어 영역, 한국사 영역을 제외하고 14,688가지나 된다.[2]
- 대학수학능력시험에서 받을 수 있는 등급: 모든 영역에서 1~9등급이므로 9⁷=4,782,969가지나 된다.
- 로또의 경우 45개의 공 중 6개가 특정한 순서로 나올 경우의 수는 [math( 45\times 44\times 43\times 42\times 41\times 40 = 5,864,443,200 )]다. 예를 들어, 공 6개가 17→3→43→38→26→6의 순서로 나올 가능성은 대략 [math( 1 / (59 )]억[math( ) )]이다. 45개의 공 중 특정 공 6개가 나올 경우의 수는 [math( \displaystyle \frac{45\times 44\times 43\times 42\times 41\times 40}{6\times 5\times 4\times 3\times 2\times 1} = 8,145,060 )]이다. 예를 들어, 3, 6, 17, 26, 38, 43의 공이 나올 확률은 대략 [math( 1 / (815 )]만[math( ) )]이다.
- TAS(Tool-assisted Speedrun)는 경우의 수를 조합하여, 최적의 경우를 만들어내는 프로그램이다. 철권 시리즈에서 이를 사용하여, 영화와도 같은 격투를 보여줄 수 있다.
- 현대 한글 한 글자 자모의 조합은 19×21×(1+27) = 11172 가지다. 초성 = (14 + 쌍자음 5), 중성 = 21, 종성 = (27 + 종성 없음 1). 실제 발음될 수 있는 음절의 조합은 그보단 적어서[3], 19×21×(7+1) = 3192 가지다.
8. 관련 문서
- 아키네이터[4]
- 이산수학
- 순열
- 조합
- 트리(그래프)
- 탐색 알고리즘 - 알파고 같은 종류의 인공지능은 결국 트리형태로 표현되는 경우의 수를 A* 알고리즘 같은 다양한 탐색 알고리즘으로 빠르게 줄여주는 프로그램이다.
- 확률
- 확률론
- 논리 회로
- 수학
- 수학 관련 정보