백준 <브루트 포스 - N과 M> 순열과 조합 정리

백준의 code.plus 문제집 <브루트 포스 - N과 M>을 풀면서 순열과 조합을 이해하고, 문제를 더 쉽게 해결할 수 있게 되서 그 내용을 정리했습니다. 순열(Permutation) 순서대로 나열한다는 것을 의미하며 순서가 중요합니다. 예를 들어 1 2 3과 3 2 1은 서로 다른 순열입니다. 예시 다섯개의 문자열 A B C D E에서 3개의 문자열을 고른다고 가정해봅시다. 첫 번째 문자로 B를 선택했다면 두 번째로 올 수 있는 문자열은 B를 제외한 A C D E 중에서 선택됩니다. 마찬가지로 3번째 올 수 있는 문자열의 개수는 3개입니다. 5부터 1개씩 줄어들면서 곱하는데 3개를 고르는것이기 때문에 3에서 멈춥니다. 연속해서 진행되기 때문에 총 경우의 수는 5 x 4 x 3이 됩니다. 수식 이를 수식으로 나타내면 n개 중에서 r개를 고르는 순열은 다음과 같이 표현할 수 있습니다. \[_nP_r = n(n-1)(n-2)\cdots(n-r+1)\] 위의 예시를 이 식에 대입...

Submit