불변성 원리
Invariance Principle.어떤 문제에서, 어떤 연산을 아무리 적용해도 1) 변하지 않는 값이 있거나(→불변량, I) 2) 일정한 규칙에 의해 순환하는 값이 있거나,3) 일정한 규칙(단조증가, ...)에 의해 발산하는 값이 있다이런 경우에 적용할 수 있다.특히 이런 불변량은 mod N이 통하는 경우가 많다. 그중에서도 대표적으로 홀짝성(mod 2). 예제를 보자. 1. 탁자 위에 하얀 칩, 검은 칩, 빨간 칩이 각각 a,b,c,개씩 있다. 한 번에 서로 다른 색깔의 칩 두 개를 선택해서, 그 두 개를 버리고 나머지 색깔의 칩 한 개를 어디선가 가져오자.1 - 1) 칩 하나만 남을 경우, 그 칩의 색깔은 (a,b,c)에 대해 한 가지만 존재함을 보여라.(즉 중간에 어떤 칩을 고르든 상관이 없다)..
2015. 2. 14. 21:32