Notice
Recent Posts
Recent Comments
목록2016/12 (1)
Graphics Programming
포함-배제의 원리
포함-배제의 원리는 합집합의 크기 ($ n(A_1 \cup A_2 \; \cup \; ... \; \cup \; A_k) $) 를 세는 데 활용할 수 있는 기법이다. 다음은 수학 정규교육에서 집합을 배울 때 나오는 간단한 공식이다. $$ n(A \cup B) = n(A) + n(B) - n(A \cap B) $$ 위키피디아를 보면 위 공식을 k개 집합에 대해 일반화한 공식이 나온다. 출처: 위키피디아 하지만 위 공식을 코드로 구현하라면 가능할지 모르겠다. 대신 재귀적인 형태를 살펴보자. ($ A = A_1 $) , ($ B = A_2 \; ... \; A_k $) 를 대입하면 $$ n(A_1 \cup A_2 \; \cup \; ... \; \cup \; A_k) = n(A_1) + n(A_2 \cup \..
Season 1/Problem solving
2016. 12. 24. 11:45