불변성 원리

2015. 2. 14. 21:32알고리즘 문제풀기/기타 주제

Invariance Principle.

어떤 문제에서, 어떤 연산을 아무리 적용해도

1) 변하지 않는 값이 있거나(→불변량, I)

2) 일정한 규칙에 의해 순환하는 값이 있거나,

3) 일정한 규칙(단조증가, ...)에 의해 발산하는 값이 있다

이런 경우에 적용할 수 있다.

특히 이런 불변량은 mod N이 통하는 경우가 많다. 그중에서도 대표적으로 홀짝성(mod 2).

예제를 보자.


1. 탁자 위에 하얀 칩, 검은 칩, 빨간 칩이 각각 a,b,c,개씩 있다. 한 번에 서로 다른 색깔의 칩 두 개를 선택해서, 그 두 개를 버리고 나머지 색깔의 칩 한 개를 어디선가 가져오자.

1 - 1) 칩 하나만 남을 경우, 그 칩의 색깔은 (a,b,c)에 대해 한 가지만 존재함을 보여라.(즉 중간에 어떤 칩을 고르든 상관이 없다)

1 - 2) 이번에는 가져올 때 한 개 대신 두 개를 가져와보자. 즉 칩의 총량은 변하지 않는다. 이때 같은 색의 칩들만 남게 할 수 있는 (a,b,c)는?



1-1을 보면...

칩 두 개를 없애고, 나머지 하나는 늘어난다. 칩의 총량은 하나 줄어든다. 또 뭘 알 수 있을까?

사실 위에서 스포일러를 해버렸지만, (a, b, c) 세 수의 홀짝성은 무조건 변한다. 따라서 한 칩만 남을 경우, 갯수는 (1,0,0)개가 된다.(순서에 신경쓰지 않고)

(a,b,c) 중에는 비둘기집의 원리에 의해 홀짝이 같은 두 수가 존재한다.

만약 세 수 모두 같다면 칩 하나만 남는 것이 불가능하다. (홀홀홀) / (짝짝짝)만 가능하므로...

그렇지 않다면, 반드시 (짝짝홀)이나 (홀홀짝) 만 가능하다. 그러면 세 개중 다른 것(짝짝홀 중 홀, 홀홀짝 중 짝)의 색깔이 반드시 남게 된다.


예)


4

 3

 2

 (짝짝)

3

 2

3

 (홀짝홀)

2

 3

2

 (짝홀짝)

1

2

3

 (홀짝홀)

2

1

2

 (짝홀짝)

1

2

1

 (홀짝홀)

2

1

0

 (짝홀짝)

1

0

1

 (홀짝홀)

0

1

0

 (짝홀짝)


1-2를 보면...

잘 모르겠다. 이번에는 위와 같은 홀짝 불변량도 적용되지 않고, 일단은 총합이 일정하다는 의미없는 불변량 하나만 보인다.

두 개는 -1이 되고, 하나는 +2가 된다.

이제 조금만 더 생각해보자! 위에서 이미 힌트가 나와있다.


mod 3으로 생각해보면 세 숫자 모두가 -1(+2)가 된다는 걸 알 수 있다! 그러면 마지막에 남는 세 수는 각각 (0,0,x)인데,

세 숫자 중 3으로 나눈 나머지가 같은 두 숫자가 있으면 되겠지.


(나중에)


'알고리즘 문제풀기 > 기타 주제' 카테고리의 다른 글

Code::Blocks에서의 편한 설정  (0) 2016.01.13
CMS Green  (0) 2015.08.20
FFT in competitive programming  (0) 2015.07.18
unique한 bipartite matching의 성질  (0) 2015.07.05
불변성 원리  (1) 2015.02.14
Prefix sum  (0) 2013.07.29