SEB_BE_43 / 23.01.25 회고

오늘

• 순열
• 조합
• GCD
• 멱집합

순열과 조합

순열 : 순서를 생각하며 요소 n개의 수를 m개 선택하여 뽑는 경우의 수.
조합 : 순서를 생각하지 않고 요소 n개의 수를 m개 뽑는 경우의 수.

예시로 카드 뽑기를 들어보자.

5장의 카드 중 3장의 카드를 나열하려고 할 때

• 순서를 생각하며 3장을 선택하는 경우. = 순열
• 순서를 생각하지 않고 3장을 선택하는 경우. = 조합

순열

모든 카드를 한 장씩 두면서 3장이 되면 멈춘다.

조건을 만족하려면 이 조건으로 경우의 수를 구해보자.

1. 첫번째 카드를 구하는 방법은 5가지의 방법이 있다. (A,B,C,D,E) 중 A를 골랐다고 한다면
2. 두번째 카드를 구하는 방법은 4가지의 방법이 있다. (B,C,D,E) 중 B를 골랐다면
3. 세번째 카드를 구하는 방법은 3가지의 방법이 있다. (C,D,E) 중 C를 골랐다면

A,B,C 한번의 경우의 수가 완성된다.

이 방법으로 구한다면 5*4*3 = 60 가지의 경우의 수가 나올 것이다.

순열은

A,B,C와 A,C,B 두개 다 A,B,C를 선택했지만 나열 순서가 다르므로 다른 경우로 인식된다.
그러므로
A,B,C / A,C,B / B,A,C / B,C,A / C,A,B / C,B,A 다 다른 경우의 수가 됨.

또, 순열은 일반화 과정을 거쳐, Permutation의 약자 P로 표현한다.
표현해보자면

• 5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60

조합

조합 역시 모든 카드를 한 장씩 두면서 3장이 되면 멈춘다.

조합은 순열과 다르게 순서에 의미를 두지 않기 때문에

A,B,C / A,C,B / B,A,C / B,C,A / C,A,B / C,B,A 이게 하나의 경우의 수가 됨.
요소에 의미를 둠. 
A,B,C가 이미 쓰였다면 끝. A와 B와 C가 들어있는 덱이 이미 있기 때문.

그래서 순열에 비하면 코드를 짜기가 살짝 쉽다.

GCD

최대공약수를 의미한다.
공약수 = 두 가지 수의 약수가 같은 경우.
최대 공약수 = 공약수 중 값이 큰 것.

최대 공약수의 경우 코드를 직접 짜도 되지만 유클리드 호제법 이라고 이미 메서드가 있다.

이걸로 쉽게 구할 수 있는데,
사실 나는 유클리드 호제법을 써서 문제를 풀지는 않았다...

• 유클리드 호제법
  

멱집합

모든 요소의 집합의 갯수.

ex ) {0,1}
{}, {0}, {1}, {0,1} = 4개가 된다.

2^n 이라고 생각하면 되겠다..