순열, 조합 기본 정리

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

이 문제를 푸는데, 기본적인(?) 수학 지식이 필요하다.

우리가 일반적으로 아는 경우의 수를 계산해야 하는데, python의 순열로도 해결이 가능하지만, 기왕이면 그 기본 개념부터 보려 한다.

 

팩토리얼 이란?

어떠한 수로부터 하나씩 줄여가며 곱하는 연산.

!5의 경우 5 * 4 * 3 * 2 * 1 을 의미한다.

순열이란?

어떠한 집합에 있어서 유한개의 원소를 뽑아올 때, 그 순서 까지 고려하여 뽑는 경우의 수.

예시로 아래와 같은 공이 있다고 치자..

[빨, 주, 노, 초]

이 때, 2가지 공을 빼는 경우를 순열로 계산하자면, [빨, 주] 와 [주, 빨] 의 경우는 분명히 다르다.

 

순열의 공식은 아래와 같다. 일 때 n은 전체 갯수, r은 뽑고싶은 갯수를 의미한다

이걸 대입하면, 위의 경우에서 4개 중 2개를 뽑는 경우를 계산하자면..

(4 * 3 * 2 * 1) / (2 * 1) = 12 경우로 계산할 수 있다.

조합이란?

순열로 부터 파생되었고, 순열은 순서를 고려하지만, 조합은 순서를 고려하지 않는다.

순열 같은 경우는 N개를 뽑았다고 했을때 맨 처음 고른것에서, 순서를 섞는 경우가 포함된다.. 따라서 순열이 더 가지가 많다!

조합은 이에 따라 순열 공식을 이용해서 만들어 낼 수 있는데.. 중복이 없게끔 나눠서 제거해버리면 된다.

 

이걸 대입하면, 위의 경우에서 4개 중 2개를 뽑는 경우를 계산하자면..

(4 * 3 * 2 * 1) / (2 * 1)(2 * 1) = 6 경우로 계산할 수 있다.

 

중복순열

일반적으로 순열은 하나씩 빼가면서 중복을 없애는데, 그게 없으면 팩토리얼을 사용할 필요가 없다.

 

따라서 이 경우에는 4의2제곱.. 16경우로 계산할 수 있다.

 

원순열

특정 자리를 기준으로 원소들을 원형으로 배치하는 경우의 수 이며, 시계방향 및 반시계방향을 둘 다 계산한다.

원순열의 경우는 -> 방향, <- 방향 둘 다 계산에 넣는다 

4

5

[기준] 3

1

2

 

이렇게 배치되었다고 했을 때, 3->1->2->4->5  하고 3 -> 5 -> 4 -> 2- > 1  이걸 서로 다르게 본다는 것이다.

공식으로는 이렇게 계산할 수 있다. 기준점 하나를 뺀 나머지의 나열과 같아서...

 

염주순열

원순열은 방향에 따라 다르게 구분하는데, 염주순열은 방향을 고려하지 않는다. 즉 대칭성도 고려한다. 

(다른 설명글들은 목걸이, 뒤집는거 이렇게 표현하던데 이게 더 잘 이해가 되더라..)