ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 6 경우의 수 덧셈규칙
    Discrete mathmatics and Problem Solving/6, 8 경우의 수와 그 응용(dp) 2017. 10. 11. 02:25

    이전 포스트 보기 경우의 수 

    곱셈규칙

    경우의 수 덧셈규칙 The Sum Rule


    Definition 덧셈규칙

    어떤 업무를 완료하기까지 n1 가지 수로 된 방법 그리고 n2 가지 수로 된 방법이 있을 때, 업무를 완료 하는데 총 방법수는 n1+n2 이다. 여기서 n1과 n2는 어떠한 공통된 집합(즉, 부분 또는 원소) 이 없다.


    덧셈규칙은 곱셈규칙과 전제가 다르다. 곱셈규칙은 어떤 사건이 and 연산자로 묶여있을 때 적용되며, 어떤 사건이 or 연산자로 묶여있으면 덧셈규칙이 적용된다. 아래의 그림을 확인하자. 

    나의 하루 (오늘)은 밥먹고 똥싸기로 이루어져있으며, 나의 내일은 밥먹거나 똥싸기로 이루어져있다. 작성자가 가족들한테 인정받는 주특기이다.

    곱의규칙 참고사이트 (곱의 규칙은 집합과 집합의 곱인 cartesian product 과 같다. S1 * S2 ...)

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

    합의규칙 참고사이트 (합의 규칙은 집합과 집합의 or 연산과 같다. S1 U S2 ... )

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


    예제 12

    요한이는 머리카락이 37개뿐이고, 민수는 머리카락이 83개뿐이다. 머리카락 한 개를 뽑아서 요술을 부려야하는데, 얼마 만큼의 경우의 수가 존재할까? 여기서 모든 머리카락은 서로 다르다. 즉, 고유하다.

    답 

    요한이의 머리카락에서 머리카락 하나를 뽑는 경우의 수는 37가지이고, 민수의 머리카락을 뽑는 경우의 수는 83개다. 요한이의 머리카락을 뽑는것은 민수의 머리카락 뽑는 경우와 겹치지 않는다. 요한이의 머키락이 민수의 머리카락이 될 수 없기 때문이다. 합의 규칙에 따라, 머리카락 하나를 뽑는 경우의 수는 37+83=120가지이다.


    Application 합의 규칙 응용

    안타깝지만, 합의 규칙 또한 두 가지 이상의 사건에 대해 적용가능하다. 어떤 업무가 n[1] 경우의 수를 가진 방법, n[2] 경우의 수를 가진 방법 ... n[m] 경우의 수를 가진 방법이 있다고하자. 단, m개의 방법중 어떠한 방법도 공통된 성질을 가지고 있지않다면 합의 규칙에 따라 업무를 수행하는 방법은 n[1]+n[2]+ ... +n[m] 가지가 존재한다.

    더욱 안타깝지만 이 또한 수학적 귀납법을 이용해 증명해내야한다. 그러나 다음으로 미룬다.

    <진짜 다음에 할게 ... 일단 지금은 무승부하자...>


    예제 13

    오늘 재우는 자신이 이제껏 모아논 엄선 야동작을 볼 마음에 신이 났다. 재우의 비밀 폴더는 총 세개가 있는데 각각 23, 15, 19 개의 야동이 들어있다. 재우는 폴더를 엄격히 관리했기에 폴더간 야동이 겹치는 경우는 없다. 재우가 야동 하나를 고르는 경우의 수는 얼마인가?

    재우는 각 폴더에서 23, 15, 19 개의 고유한 야동을 꺼낼 수 있다. 합의 규칙에 따라 23 +15 +19 =57 가지의 경우의 수가 존재한다.


    예제 14

    다음 코드를 보고 ans 값을 유추해보자

    초기 ans의 값은 0이다. ans에 영향을 끼치는 반복문들은 중첩되어있지 않고 개별적으로 작동한다. 반복자 i의 상태를 보자. 이전에 아래와 같은 코드와 차이를 볼 수 있을것이다. 무엇이 크게 다른가?


    바로 반복자의 상태이다. 위의 반복문의 반복자들은 i 하나당 ans 값이 하나 더해진다. 그러나 아래의 경우 반복자들{ i, j, k, l, m , n}의 조합에 따라 반복자가 하나 씩 더해진다. 이게 경우의수 곱과 합의 차이를 보여준다. 


    자 이제부터 딱 5문장만 집중해서 보자. for 문과 경우의 수를 정리한다.

    즉, 겹치지 않는 반복문이 있는 것 처럼 교집합이 없는 사건들이 있다고 하자. 각 반복자 i 하나만으로도 사건이 충분할 때에는, 합의 규칙에 따라 더하게되면 전체 사건의 경우의 수가 된다. 

    그러나 아래처럼 반복문이 겹쳐져있는 상태 즉, 사건이 어떤 행위 {i, j, k, l, m, n} 이 반드시 모두 수행되어야 성립된다고 해보자. 그러면 그 개별 행위의 경우의 수를 곱의 규칙에 따라 곱하면 전체 사건의 경우의 수가 된다.


    다음부터 응용된 경우의 수 (dp, divide and conquer) 를 볼 것 이다. 본격적으로 코드도 첨부 할것같다.

    아 ! 그 전에 순열과 조합 구현에 대해 살펴볼 것 이다. 이쯤되면 시험기간이므로 후후, 검색하시는 분들이 많이 찾으러 올수도 있겠다 라는 기대하에 ... 

    푸하하 ^^ 나도 이렇게 타겟팅만 잘하면 블로그 광고로 알부자 될거같다. 생각만해도 기쁘다 (5개월동안 3달러벌음)



    다음포스트 읽기

     브루트포스, 순열과 조합

    http://ingyeoking13.tistory.com/163

     



    댓글 0

Designed by Tistory.