210706_DP 및 경우의 수에 대해

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

합하기 +

독립사건 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개중 일부의 갯수 선택하는 경우의 수

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