경우의 수, 순열, 조합

조합론(Combinatorics) - 물건들을 여러 가지 형태로 그룹짓는 방법을 연구하는 학문이다.

경우의 수 - 어떤 시도(trial)를 통해 일어날 수 있는 사건(event)의 가짓수이다.

 

곱의 법칙 - 다중 for문이 예이다. 경우의 수가 늘어나서 시간 복잡도가 늘어난다.

합의 법칙 - for문이 여러 개인 코드가 예이다.

포함-배제 원리 - 중복되는 부분이 있다면 중복된 만큼의 수를 뺀다.

 

트리 - 노드와 가지로 구성되어 있는 자료구조이다. 데이터 저장 순서는 뿌리에서 시작해 가지를 따라 다른 노드로 진행된다.

노드(Node) - 어떤 데이터를 저장한다.

가지(Branch) - 어떤 노드에서 뻗어 나온 다른 노드를 연결시키는 줄기이다.

뿌리(Root) - 처음 시작하는 노드를 말한다.

 

순열(Permutation) - n개의 물체 중에 r개를 뽑을 때의 경우의 수를 말한다. 순서가 중요하다. like 배열

조합(Combination) - n개의 물체 중에 r개를 뽑을 때의 경우의 수를 말한다. 순서는 중요하지 않다. like 집합