경우의 수 - 합의 법칙, 곱의 법칙

경우의 수 - 합의 법칙, 곱의 법칙

경우의 수란?

어떤 사건(일)이 일어날 수 있는 경우의 가짓수를 수로 표현한 것이다.

• 위키백과

• 경우의 수를 구하는 방법이 여러개가 있지만, 이번에는 곱의 법칙과 합의 법칙에 대해서만 알아보도록 하겠습니다.

• 알고리즘 문제를 풀때 알아둔다면 쉽게 공식을 통해 풀수 있습니다.

• 순열과 조합은 아래의 링크에서 확인해주세요.

Permutation Algorithm(순열 알고리즘) & Combination Algorithm(조합 알고리즘)

합의 법칙

• 두 사건 A,B가 동시에 일어나지 않을 때, 사건 A와 사건 B가 일어나는 경우의 수는 각각 m, n이면 사건 A 또는 사건 B가 일어나는 경우는 m+n이다.

예시

• 예를들어 캡모자가 3개가 있고 비니모자가 3개가 있을때 착용할 수 있는 총 모자의 경우의수는 몇개인가라고 한다면 3 + 3 = 6이 될것이다.

곱의 법칙

• 두 사건 A,B에 대하여 사건 A가 일어나는 경우의 수가 m이고, 그 각각에 대하여 사건 B가 일어나는 경우의 수가 n이면 두 사건 A, B가 연이어 일어나는 경우의 수는 m*n이다.

예시

• 햄버거의 종류는 데리버거, 치즈버거, 한우버거가 있다.
• 사이드 메뉴는 치즈스틱, 양념감자가 있다.
• 음료수는 사이다, 환타, 콜라가 있다.
• 이 3개를 가지고 세트메뉴를 만들려고 할때 경우의 수는?

데리버거 + 치즈스틱 + 사이다
데리버거 + 치즈스틱 + 환타
데리버거 + 치즈스틱 + 콜라
데리버거 + 양념감자 + 사이다
데리버거 + 양념감자 + 환타
데리버거 + 양남감자 + 콜라

• 버거 하나로 예시를 들어도 총 6개가 나오며 버거 * 사이드메뉴 갯수 * 음료수 개수가 나오게 된다.
• 즉, 곱의 법칙을 이용하면 버거 갯수(3) * 사이드 메뉴 갯수(2) * 음료수 갯수(3)을 한 결과인 18이 경우의 수가 된다.

알고리즘 예시

코딩테스트 연습 - 위장

• 모자 2개 안경 1개가 있다고 하면 일단 각 한개씩에 대해서 낄수 있으니, 합의 법칙을 이용해 3을 유추해낼수 잇으며, 모자와 안경을 같이 사용하는 경유는 곱의 법칙을 이용해 2를 구할 수 있다.
• 따라서 5가 정답이 된다.
• 아울러 굳이 합의 법칙을 사용하지 않고 각 의류에 입지 않는 경우의 값을 추가해서 곱의 법칙만 사용해도 쉽게 풀리게 됩니다. (이때는 아무것도 안입는 경우는 없기 때문에 -1을 해주셔야 합니다.)