경우의 수에 대한 머릿속 시각화, 명료해지는 활용

경우의 수에 대한 머릿속 시각화, 명료해지는 활용

---

경우 1에 대한 종속된 경우 2가지, 또 그 각각의 경우에 대한 경우 2가지라면, 어떻게 표현해야할까?

1*2*2 로써, 아래와 같은 그림으로 표현할 수 있다.

자, 그렇다면 모든 경우를 한눈에 볼 수 있다. 이것을 트리구조(tree structure), 그리고 개별을 노드(node)라고 한다.

0부터 1 또는 2를 거쳐서 도달한 그 밑의 작은 1 또는 2의 연속된 연결고리를 노드라고 하는데, 이것의 갯수가 바로 경우의 수 이다.

상위 요소와 하위 요소의 개념을 안다면, 경우의 수를 구함에 있어서 매우 빠르게 진행할 수 있다. 

What's difference between 상위 요소 and 하위 요소?

상, 하위는 상대적인 것이다. 그렇다.노드에서 빨간색 요소는 파란색 요소의 상위 요소이고, 파란색 요소는 초록색 요소에 대하여 상위 요소이다.

반대로, 초록색 노드는 파란색 요소에 대하여 하위 요소이며, 파란색 요소 또한 빨간색 요소에 대하여 하위 요소이다.

아까전 1 * 2 * 2의 식을 기억하는가? 각각의 상수들은 이 서로 다른 노드들에 대한 같은 선상에 놓인 요소들의 숫자이다!. 바꾸어 말하면, 그 상위 요소에 관하여 생성되는 요소의 갯수인 것이다.

이제 간단한 수의 변경으로 방대한 수의 경우의 수를 조작할 수 있게되었다.

---

하위 노드의 갯수를 임의적으로, 원하는 것만 있다고 치부해버린다면, 지워진(가려진) 그 요소에 속한 모든 하위 요소는 없어지는 것이다!

1*2*2의 식을 1*1*2의 식으로 바꾼다면, 아래와 같은 트리 구조가 생성이 된다.

위 개념과 그 사용은 여러 문제 유형에 사용될 수 있다. 가령, 두자리수를 만들때 특정 수 이상의 것만 골라내거나, 특수 조건 하에 어떤 다른 것을 무시하는 문제 말이다.