티스토리 뷰
6 경우의 수 (곱셈 규칙)
gaelim 2017. 10. 9. 03:03경우의 수
조합론은 무엇인가?
경우의 수 기초
상대방의 비밀번호를 알아내고 싶다고 하자. 내가 코딩한 비밀번호 생성기가 어떤 시간 복잡도를 가질까? 거기다 이론상 반드시 필요한 연산 수(경우의 수)도 있으니.. 유효한 시간내에 알아내는게 가능할까?
어쩌면 비밀번호 생성기로 해킹하는 것보다 다른 방법이 더 효율적이지 않을까? 재밌는 문제다.
경우의 수의 기초 원리 (곱의 규칙과 덧셈의 규칙)
Definition: 곱의 규칙
어떤 수행 절차가 두 개의 업무가 연속되어서 수행된다고 하자. 그러니까 C라는 업무가 있는데, C라는 것은 A와 B가 모두 수행되어야 완성된다고 하자. 그리고 A를 수행하는데 n1 만큼의 방법이 있고, B를 수행하는데 n2 만큼의 방법이 있다. 그러면 C를 완료하기 위해서는 n1*n2 만큼의 방법이 있는 것이다.
예제 1
답
예제 3
답
포트의 갯수를 찾는데에는 두 가지 요소로 break down 할 수 있다.
첫 번째로는 초소형 컴퓨터를 선택하고, 그 뒤 그녀석이 가지고 있는 포트를 선택하는 것이다. 따라서, 초소형 컴퓨터를 선택하는 32가지 방법과, 해당 컴퓨터에서 포트를 선택하는 방법 24가지 방법이 있다. 곱의 규칙에 따라 32*24= 768 포트가 존재한다.
Application 곱의 규칙 응용
곱의 규칙의 확장판은 다음과 같다. 수행절차가 2개 이상으로 이루어져 있는 것이다. 즉, 어떤 수행 절차가 다음의 업무들로 이루어져있다고 생각해보자. T1, T2, T3, .... , Tm 여기서 T는 Task이다. 그리고 각 업무 Ti 는 다음의 수행 방법을 가지고 있다고 하자. n1, n2, n3 ... nm. 그렇다면 해당 수행절차를 수행하는데 n1*n2*n3 ... * nm 의 방법의 수가 있다.
곱의 규칙은 수학적 귀납법을 이용하여 증명할 수 있다. (다음에 꼭.. 증명... ㅠ..ㅠ )
<이런 자세에서 부터 난 늦은 것일수 있어...ㅠ.ㅠ
챕터 5할때 꼭 할게요 ㅠ.ㅠ>
예제 4
답
비트는 각 문자당 2가지의 경우의 수가 존재한다. 길이가 7인 비트 문자열은 7개의 문자로 이루어진다. 즉, c1, c2, c3 ... c7 은 각 두 가지의 방법으로 완성될 수 있으므로, 곱의 규칙에 따라 2*2* ... *2 ,2^7=128 가지의 경우의 수가 존재한다.
예제 5
<군필자들이 잘 아는 번호판>
위와 같은 번호판이 있다고하자. 얼마나 많은 고유한 번호판을 만들 수 있는가? 단, 여기서 3번째의 한글은 알파벳 소문자로 대체한다고 하자. 즉, @@A@@@@ 를 만족하는 번호판의 개수는?
답
예제 6
<각자 한개씩만 보급품을 선택가능한 경우의 수를 생각해보자.
그럴듯한 함수다. 일반적인 함수의 원소들은 그냥 숫자이겠지만 이해를 돕기위해 바꿔보았다>
예제 7
답
다음 포스트 읽기
경우의수 덧셈 규칙
http://ingyeoking13.tistory.com/162
'Discrete mathmatics and Problem Solving > 6, 8 경우의 수와 그 응용(dp)' 카테고리의 다른 글
6 순열과 조합 : 조합의 구현 (0) | 2017.10.16 |
---|---|
6 순열과 조합의 구현 - 순열편 (0) | 2017.10.15 |
6 순열과 조합 (0) | 2017.10.14 |
6 브루트포스 (0) | 2017.10.13 |
6 경우의 수 덧셈규칙 (0) | 2017.10.11 |
- Total
- Today
- Yesterday
- 아레나
- 대규모 시스템 설계 기초
- Trie
- 그라파나
- arena simulation
- 아레나 시뮬레이션
- 아레나시뮬레이션
- 명제논리
- javascript
- Propositional and Predicate Logic
- rosen
- 최단경로 알고리즘
- Discrete Mathematics
- 자바스크립트
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 조합 코딩
- 백준
- 데이터 중심 애플리케이션 설계
- Arena
- grafana cloud
- 자바스크립트 예제
- paul wilton
- 로젠
- flutter
- 이산 수학
- 시뮬레이션
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- beginning javascript
- 이산수학
- Simulation
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |