주사위 합 경우의 수 - jusawi hab gyeong-uui su

주사위는 확률에 대한 개념을 잘 보여줍니다. 가장 일반적으로 사용되는 주사위는 6면이있는 큐브입니다. 여기서는 3 개의 표준 주사위를 굴릴 확률을 계산하는 방법을 살펴 보겠습니다. 2 개의 주사위 를 굴려서 얻은 합계의 확률을 계산하는 것은 상대적으로 표준적인 문제입니다. 2 개의 주사위가있는 총 36 개의 다른 롤이 있으며 2에서 12까지의 합계가 가능합니다. 주사위를 더 추가하면 문제는 어떻게 변합니까?

가능한 결과 및 합계

하나의 주사위에 6 개의 주사위가 있고 2 개의 주사위에 6 개의 2 = 36 개의 주사위가있는 것처럼 주사위 3 개를 굴릴 확률 실험에는 6 3 = 216 개의 결과가 있습니다. 이 아이디어는 더 많은 주사위를 더 일반화합니다. 우리가 n 개의 주사위를 굴리는 경우 6 개의 결과가 있습니다.

가능한 주사위가 여러 개의 주사위를 굴릴 수도 있습니다. 가능한 가장 작은 합계는 모든 주사위가 가장 작거나 각각 하나씩있을 때 발생합니다. 3 개의 주사위를 굴릴 때 3의 합을줍니다. 주사위에서 가장 큰 숫자는 6이며, 이는 주사위 3 개 모두가 6 인 경우 가장 큰 합계가 발생 함을 의미합니다. 이 상황에 대한 합계는 18입니다.

n 개의 주사위가 굴러 올 때 가능한 최소 합은 n 이고 가장 큰 합은 6n 입니다.

• 세 가지 주사위가 합계 3 개가 될 수있는 한 가지 방법이 있습니다.
• 4 가지 방법 3 가지
• 5 명 중 6 명
• 10 명 중 6 명
• 7 월 15 일
• 8 월 21 일
• 9 월 25 일
• 10 월 27 일
• 11 월 27 일
• 12 ~ 25
• 21 ~ 13
• 15시 14 분
• 10 명 중 15 명
• 16 명 중 6 명
• 17 세
• 1에 대해 18

합계 형성

전술 한 바와 같이, 3 개의 주사위에 대해, 가능한 합계는 3 내지 18의 모든 수를 포함한다.

확률은 계수 전략을 사용하고 숫자를 정확히 3 개의 정수로 분할하는 방법을 찾는 것으로 계산할 수 있습니다. 예를 들어, 3의 합을 얻는 유일한 방법은 3 = 1 + 1 + 1입니다. 각 다이가 다른 다이와 독립적이므로 4와 같은 합계를 세 가지 방법으로 얻을 수 있습니다.

• 1 + 1 + 2
• 1 + 2 + 1
• 2 + 1 + 1

더 많은 계수 인수는 다른 합계를 형성하는 방법의 수를 찾는 데 사용될 수 있습니다. 각 합계의 파티션은 다음과 같습니다.

• 3 = 1 + 1 + 1
• 4 = 1 + 1 + 2
• 5 = 1 + 1 + 3 = 2 + 2 + 1
• 6 = 1 + 1 + 4 = 1 + 2 + 3 = 2 + 2 + 2
• 7 = 1 + 1 + 5 = 2 + 2 + 3 = 3 + 3 + 1 = 1 + 2 + 4
• 8 = 1 + 1 + 6 = 2 + 3 + 3 = 4 + 3 + 1 = 1 + 2 + 5 = 2 + 2 + 4
• 9 = 6 + 2 + 1 = 4 + 3 + 2 = 3 + 3 + 3 = 2 + 2 + 5 = 1 + 3 + 5 = 1 + 4 + 4
• 10 = 6 + 3 + 1 = 6 + 2 + 2 = 5 + 3 + 2 = 4 + 4 + 2 = 4 + 3 + 3 = 1 + 4 + 5
• 11 = 6 + 4 + 1 = 1 + 5 + 5 = 5 + 4 + 2 = 3 + 3 + 5 = 4 + 3 + 4 = 6 + 3 + 2
• 12 = 6 + 5 + 1 = 4 + 3 + 5 = 4 + 4 + 4 = 5 + 2 + 5 = 6 + 4 + 2 = 6 + 3 + 3
• 13 = 6 + 6 + 1 = 5 + 4 + 4 = 3 + 4 + 6 = 6 + 5 + 2 = 5 + 5 + 3
• 14 = 6 + 6 + 2 = 5 + 5 + 4 = 4 + 4 + 6 = 6 + 5 + 3
• 15 = 6 + 6 + 3 = 6 + 5 + 4 = 5 + 5 + 5
• 16 = 6 + 6 + 4 = 5 + 5 + 6
• 17 = 6 + 6 + 5
• 18 = 6 + 6 + 6

세 개의 다른 숫자가 파티션을 형성 할 때, 예를 들어 7 = 1 + 2 + 4 일 때, 3! (3x2x1) 개의 다른 숫자로 치환 할 수 있습니다. 따라서 이것은 샘플 공간에서 세 가지 결과로 계산됩니다. 두 개의 서로 다른 숫자가 파티션을 형성 할 때,이 숫자를 치환하는 세 가지 다른 방법이 있습니다.

특정 확률

각 합계를 얻는 방법의 총 수를 표본 공간 의 총 결과 수 또는 216로 나눕니다.

결과는 다음과 같습니다.

• 확률 3 : 1/216 = 0.5 %
• 확률 4 : 3/216 = 1.4 %
• 확률은 5 : 6/216 = 2.8 %
• 확률은 6 : 10/216 = 4.6 %
• 확률은 7 : 15/216 = 7.0 %
• 확률은 8 : 21/216 = 9.7 %
• 확률 9 : 25/216 = 11.6 %
• 확률은 10 : 27/216 = 12.5 %
• 확률 11 : 27/216 = 12.5 %
• 확률은 12 : 25/216 = 11.6 %
• 확률 13 : 21/216 = 9.7 %
• 확률 14 : 15/216 = 7.0 %
• 확률은 15 : 10/216 = 4.6 %
• 16 : 6/216 = 2.8 %의 확률
• 확률은 17 : 3/216 = 1.4 %
• 확률의 합이 18 : 1/216 = 0.5 %

알 수 있듯이 3과 18의 극한값은 가장 적습니다. 중간에있는 합계가 가장 가능성이 큽니다. 이것은 두 개의 주사위가 굴 렸을 때 관찰 된 것과 같습니다.

경우의 수에 대한 기본 개념에 대해 다시 정리하여 알고리즘을 풀때 활용을 하고자 기록해놓는다.

합하기 +

독립사건 A 또는 B가 일어나는 경우의 수를 구할 때에는 합의 법칙이 이용된다. 예로, 주사위 2개를 던져서 나온 눈의 수의 합이 7 또는 8인 경우의 수를 구하기 위해서는 두 독립사건 '주사위의 합이 7이 될 경우의 수'와 '주사위의 합이 8이 될 경우의 수'의 경우의 수를 합하면 된다.

• 두 사건 A, B가 일어나는 경우의 수가 각각 m, n일 때,
  • 두 사건이 동시에 일어나지 않음 -> m + n 가지
  • 두 사건이 겹치는 경우의 수가 i가지 일 때, 사건 A 또는 사건 B가 일어나는 경우의 수는 m + n - i 가지

곱하기 x

독립사건 A와 B가 동시에 일어나는 경우의 수를 구할 때에는 곱의 법칙이 이용된다. 예로, 주사위 3개를 동시에 던져서 나올 수 있는 모든 경우의 수는 세 독립사건 '주사위를 던져서 1~6 중 하나의 숫자가 나옴'의 경우의 수를 곱하여 구할 수 있다.

Dynamic Programming : 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결

DP관련 문제를 풀다가

 for(let i = 1; i <= target; i++) 
    bag[i] = 0;    // 경우의 수를 저장하기 위해 초기값은 모두 0으로 만들어 준다
 for(let i = 0; i < type.length; i++) {
    for(let j = 1; j <= target; j++)
       if(type[i] <= j)
          bag[j] += bag[j-type[i]];

bag의 인덱스에는 화폐값이 저장되고 type 배열에는 화폐의 종류가 저장되 있다.
특정 target 값을 만들 수 있는 경우의 수를 구할때
ex) target = 50, type = [10, 20, 50]

위 for문으로 type[i]를 돌림
-> 즉 화폐의 종류가 10일때, 20일때, 50일때
아래 for문에서
-> j만큼의 화폐값을 만들 수 있는 경우의 수를 ----------> bag[j]에 저장한다.

반복문을 진행하며 같은 j만큼의 화폐값에 화폐의 종류에 따라 경우의 수들이 축적된다.

// type[0] = 10, j = 50이면 
 bag[50] += bag[50-10] // bag[50] + bag[40]

// type[1] = 20
 bag[50] += bag[50-20] //bag[50] + bag[30]

// type[2] = 50
 bag[50] += bag[50-50] //bag[50] + bag[0]

/******************* < 50만큼의 화폐값에 만들 수 있는 경우의 수가 쌓인다 > ****************/

기존 경우의 수에 type[i]를 뺀 금액을 만들 수 있는 경우의 수를 더해준다.
j - type[i] = 0 인것부터 점차 쌓이게됨(bag[0]의 초기값 1 이용)
ex) j가 10일때 j - type[0] = 0 --> bag[j] += bag[0] ---> bag[j]에 1축적
-> 즉 type 배열 요소들로 만들 수 있는 화폐값에만 경우의 수가 쌓인다.

bag 의 target 인덱스에 target 금액을 훔칠 수 있는 경우의 수가 쌓임

그 외 n개중 일부의 갯수 선택하는 경우의 수

순열, 조합을 이용할 수 있다.
순열,조합(이전 포스팅)