acm-cicpc 수학정복

1.애드혹 수학문제(기초적인 수학 지식)

* 수학적 시뮬레이션 : 특정 혀애의 루프를 사용해서 무식하게 풀리는 유형

* 패턴이나 공식찾기 : 문제 설명을 주의 깊게 읽고 패턴이나 간략화 된 공식을 찾도록 요구하는 문제

* 격자 : 복잡한 형태의 격자도 있긴하지만 문제를 푸는 사람이 창의적으로 패턴을 찾아내야 하는 문제.

* 수 체계 및 수열 : 실존하는 수체계나 수열의 정의가 등장한다. 

일정 범위의 속하는 수(수열) 을 만들어내기, n번째 수 구하기, 주어진 수(수열)이 정의에 부합하는지 검사해보기 등이있다.

 보통은 문제 설명에 나온 정의를 주의 깊게 따라가는 것이 풀이의 핵심이나 어려운 문제는 공식을 먼저 단순화해야 하는 경우도 있다.

1) 피보나치수

2) 팩토리얼

3) 교란

4) 카탈란 수

5) 등차급수(산술급수) a,(a+d),(a+2*d),(a+3*d), ... 등이 있다. 이러한 등차수열의 첫 n개 항으로 이루어진 급수는 Sn = (n/2) *(2*a + (n-1)*d)이다.

6) 등비급수(기하급수) : 형태가 a,a*r, a*r^2, a*r^3 ,... 수열이있다. 이 등비수열의 첫 n개 항으로 이루어진 급수는 Sn = a*(1-r^n) / (1-r) 이다.

* 로그,지수,거듭제곱

log()나 exp() 함수를 영리하게 다루는 문제이다. 이러한 문제 중에 중요한 문제를 몇가지 풀어보자.

* 다항식

다항식의 계산, 미분, 곱셈, 나눗셈 등을 다루는 문제들이다. 

다항식을 표현하기 위해서는 각 항의 계수를 그 항의 차수 순으로 정렬하면 된다. 

다항식 연산을 수행할 때에는 루프를 주의깊게 사용해야 하는 경우가 많다.

* 진법과 관련된 변형 문제

진법을 다루는 수학 문제들이다.

* 그 외에 애드혹 문제

2장은 java_BigInteger를 이용하는 단원인데 java 를 안쓰니 스킵.

3. 조합론

* 이산수학의 한 분야로, 셀 수 있으며 이산적인 구조애 대해 연구하는 분야이다. 

보통 프로그래밍 대회에 조합론과 관련된 문제가 출제 된경우 그 문제에는 보통 '대상이 몇 개인가' , '대상의 개수 세기' 등의 제목이 붙는다.

 그러나 어떤 경우에는 문제 출제자가 문제 제목에 이러한 정보가 드러나지 않도록 숨기기도 한다. 

풀이 코드는 보통 짧으나, 공식(보통 재귀적인 형태를 갖는다) 를 찾기 위해서는 수학적인 재능과 인내심이 필요하다. 

ICPC 의 경우 팀원중 수학에 강한 한사람이 공식을 유도하도록 맡기고 , 나머지는 다른 문제에 집중하도록 하자.

 자주 사용되는 공식을 공부하고 외워두는 것도 좋은 아이디어이며,  예 를 들면 피보나치 관련공식, 이항계수, 그리고 카탈란수 같은 것들이 있다.

일부 조합론 공식에서는 부분 문제가 중복되기도 하며, 그러한 이유 떄문에 DP 기법이 필요한 경우도 있다. 

어떤 경우에는 계산된 값이 너무 커서 큰 정수 기법을 필요로 하기도한다.

1) 피보나치 수 

쉽게는 O(n) 의 DP 기법을 이용할 수 있다. 하지만 logn에 시간의 계산하는 방법을 알아가도록 하자.

 또 피보나치에는 몇가지 성질 들이있는데 모든 양의 정수를 한 개 이상의 서로 다른 피보나치 수의 합으로, 

그리고 그 합에 연속된 두 피보나치 수가 포함되지 않도록 하여 유일하게 나타낼 수 있다는 것이다. (제켄도르프의 정리 ) 따라서 이 정리를 만족시키는 표현법을 탐욕적 알고리즘으로 찾아 낼 수 있다. 

각 단계마다 가장 큰 피보나치 수를 택하는 것이다. 

또다른 성질로는 피사노 주기라는 게 있는데, 피보나치 마지막 한자리, 두자리 , 세자리, 네자리 숫자들이 각각 60,300,1500,15000 을 주기로 반복된다.

 

2) 이항 계수

또 다른 고전적 조합론 문제의 예로는 이항식의 거듭제곱을 대수적으로 전개 했을때 계수를 구하는 문제가 있다.

 이 때의 계수는 n개의 물품 중에서 k개를  한번에 골라내는 방법의 수이기도 하며, 이를 보통 C(n,k) 나 nCk 의 기호로 나타낸다. 

가끔 이 값이 큰경우 쓸 수 있는 몇가지 방법이 있다. nCk = nC(n-k) 를 이용하는법이다.

 또 중간 계산 과정에서 다음 수를 곱하기 전에 나눗셈을 먼 저 수행하는 방법도 있고, 큰 정수 기법을 사용하는 방법도있다. 

만일 서로 다른 n과 k값에 대해서 C(n,k)를 여러번, 그러나 일부만 계산해야 하는 경우라면  탑다운 DP 를 사용하는 것이 더 낫다.

이는 C(n,k)를 다음과 같은 방식으로 구하는 것이며, 중복 계산을 피하기 위해서는 2차원 메모 테이블을 사용하면 된다. 

C(n,0) = C(n,n) = 1 // 기저사례

C(n,k) = C(n-1,k-1) + C(n-1,k) // n > k > 0 인 경우 물품을 골라내거나 골라내지 않는다.

반면에 n==0 부터 일정한 값까지의 대해서 C(n,k)를 모두 계산해야 하는 경우라면 파스칼 삼각형을 만드는것이 더 이득이다. 

가장 왼쪽과 가장 오른쪽값은 항상 1이고, 그 사이에 들어 가는 값들은 바로 위에 두수를 합한것이다. 

3) 카탈란 수

먼저, n 번째 카탈란 수를 정의해보자. 앞서와 같이 이항 계수를 nCk란 기호를 사용하여 나타낼 때, Cat(n) =  C(2*n,n) / (n+1) 이며 Cat(0) = 1 이다.

이 값이 무엇을 나타내는지는 뒤에서 살펴보자. 

이 값을 계산해야 한다면 바텀업 DP 를 사용하는 것 이좋다.

 Cat(n) 의 값을 구해 놓았다면 Cat(n+1)의 값을 계산할 수 있다.

Cat(n+1) = (2n+2)*(2n+1) /(n+2) /(n+1)  * Cat(n) 이 된다.

카탈란 수는 다양 한 조합론 문제에 등장한다. 그중 흥미로운 몇개만 살펴보자.

1. Cat(n) 은 n개의 정점으로 이루어진 서로 다른 이진 트리의 개수를 나타낸다. 

2.Cat(n) 은 올바르게 짝지어진 n쌍의 괄호로 구성된 표현식의 개수를 나타낸다.

3.Cat(n)은 n+1 의 인자에 완전하게 괄호를 치는 서로다른 방법의 수를 나타낸다. // 잘 이해안됌. 예제참조

인자가 {a,b,c,d} 인경우 가능한 경우는 (ab)(cd), a(b(cd)), ((ab)c)d, (a(bc))d, a((bc)d) 가 있다.

4.Cat(n) 은 변이 n+2개인 볼록 다각형을 삼각 분할하는 방법의 수를 나타낸다.

5.Cat(n) 은 n*n크기의 격자에 대각선 위로 넘어가지 않는 단조 경로의 개수를 나타낸다. 

단조경로란 왼쪽 아래의 점에서 시작하여 오른쪽 위의 점에서 끝나는 경로이면서 오른쪽 방향이나 위쪽 방향으로만 이동한것을 말한다. (최단경로 갯수)

4)조합론에 대한 첨언

프로그래밍 대회에 나올법한 조합론 문제들이 여러 개 더 있지만 피보나치 수, 이항 계수, 혹은 카탈란 수 만큼 자주 나오지는 않을 것이다.

 조합론과 관련된 몇가지 흥미로운 내용을 살펴보자(9장내용) 

# 공식 및 정리 : 이 희귀한 공식 및 정리에 대한 내용이 출제된다면, 알면풀고 모르면 못풀것이다.

1. 케일리의 공식 : 번호가 붙어있는 정점 n 개로 이루어진 완전그래프는 n^(n-2) 가지의 스패닝 트리를 갖는다.

2. 교란(완전순열) : 어떤 집합에 속한 원소들로 이루어진 순열로서, 자신의 원래 위치에 놓여있는 원소가 하나도 없는 것을 말한다.

교란의 개수 der(n) 은 der(n) = (n-1)*(der(n-1) + der(n-2)) 의 관계식을 이용하여 계산할 수 있으며, 이 때 der(0) = 1, der(1) = 0이다.

3. 에르되시-갈라이 정리 : 유한한 자연수 수열이 어떤 단순 그래프의 차수를 나타내는 수열이 되는 필요충분조건을 알려준다. 

음이 아닌 정수 수열 d1 >= d2 >= ... >=dn 이 정점이 n개인 단순 그래프의 차수 수열이 될 수 있는 필요충분조건은 다음과 같다.

4.평면 그래프에 대한 오일러 공식 : V-E+F = 2가 성립하며, 이 때 F는 평면그래프의 면의 수를 의미한다.

5.모저의 원 : 어떤 원의 원주 상에 있는 n개의 점들을 현으로 연결하되, 세 현이 원 안의 한점 에서 만나지 않도록 한다.

 이 때 원이 몇 개의 조각으로 나눠지는지를 구해보자. 답은 g(n) = nC4 + nC2 + 1이다. 

6.픽의정리 : 어떤 다각형 내부의 격자점(좌표가 정수인 점) 의 개수를 I, 다각형의 면적을 A, 그리고 다각형의 경계 위에 있는 격자점의 개수를 b라고 하면 , A = I + b/2 -1 이 성립한다. 

7. 완전 이분 그래프 Kn,m 의 스패닝 트리의 개수는 m^(n-1) * n^(m-1)이다.

4.정수론

일부 수학 문제는 그 배경 이론을 알고 나면 더 쉬워지곤한다.

1. 소수 : 에라토스테네스 잘 사용할 줄알면 됌.

2.최대공약수 최소공배수 : 유클리드 잘 쓸줄 알면 됌.

3.팩토리얼 : 여기에는 O(n)에 구하는 방법만 소개됌.

4. 소인수 구하기 : 단순한 알고리즘은 모든 소수의 목록을 생성하고 정수 N이 정말 각 소수로 나누어 떨어지는 지를 검사하는 것이다.

더 나은 방법은 일종의 분할 정복 철학을 따르는 것이다. 

정수 N은 N = PF * N'의 형태로 표현 될 수 있는데, 이때 PF 는 소인수를 나타내며 N'은 N/PF에 해당하는 또 다른 정수이다.

이러한 과정을 N' =  1 이 될 때까지 반복한다.

이 과정을 더 빠르게 하려면 루트N보다 더 큰 약수는 존재하지 않는다는 성질을 이용하면 된다. 

즉 이러한 과정을 PF <= 루트N 을 만족시키는 소인수에 대해서만 진행하는 것이다.

루트N 에서 멈추게 되면 예외 케이스가 하나 발생한다. 

만일 PF^2 > N이며 N이 아직 1이 아니라면, 그때의 N은 마지막 소인수가 된다.

이것의 시간복잡도는 O(루트N * ln루트N) 이다.

5.소인수 다루기 : 간단한 문제 하나만 살펴보자 N! 이 m으로 나누어 떨어지는가 를 검사해보자.

이것은 두 수를 소인수 분해한후  m 의 소인수들이 N!에 포함되어있는지 여부를 확인하면 된다.

6.소인수를 다루는 함수 : 

(1) numPF(N) : N의 소인수의 개수를 구한다.

ll numPF(ll N){

ll PF_idx = 0, PF = primes[PF_idx], ans = 0;

while(PF * PF <= N){

while(N%PF == 0){ N /= PF; ans++; }

PF = primes[++PF_idx];

}

if(N != 1) ans++;

return ans;

}

(2) numDiffPfPF(N) :  N의 서로 다른 소인수의 개수를 구한다.

(3) sumPF(N) : N의 소인수의 합을 구한다.

(4) numDiv(N) : N의 약수의 개수를 구한다. (지수+1) 들의 곱.

(5) sumDiv(N) : N의 약수의 합을 구한다.

(6) EulePhi(N) : N보다 작은 양의 정수 중 N과 서로소인 것의 개수를 구한다. 오일러 파이함수 N*(1-1/PF)*(1-1/PF2) ... 이다.이를 이용하면 빠르게 구할 수 있다.

7. 확장된 유클리드 알고리즘 : 선형 디오판토스 방정식 풀기

동기부여를 위해 다음과 같은 문제를 생각해보자. 

어떤 사람이 사과와 오렌지를 구매했는데 그 총액이 8.39 SGD였다. 

사과 한개는 25센트이고, 오렌지 하나는 18센트이다. 그사람은 각 과일을 몇 개씩 구매했겠는가?

이 문제를 변수가 두 개인 선형 방정식 25x + 18y = 839로 모델링할 수 있다. 두 변수 x와 y가 모두 정수여야 하기 때문에, 이 선형 방정식을 선형 디오판토스 방정식이라 부른다.

두 변수에 대한 선형 디오판토스 방정식은 방정식이 한 개만 주어졌더라도 풀 수 있다! 

a와 b가 정수이며 d = gcd(a,b)라 하자. 방정식 ax + by = c는 d | c 가 성립하지 않는 경우에 정수해를 갖지 않는다.

반면에 d | c 인 경우에는 무수히 많은 정수해를 갖는다.

한쌍의 해 (x0,y0)은 다음에 나오는 확장된 유클리드 알고리즘을 이용하여 구할 수 있으며, 나머지 해는 n이 정수일 때 x = x0 + (b/d)n, y = y0 - (a/d)n 을 계산하여 구할 수 있다. 

프로그래밍 대회문제는 보통 추가적인 제약 조건을 두어 출력을 유한하게 만든다.

 25x + 18y = 839 를 풀어보자. 25x + 18y = gcd(a,b) 에 대한 해를 구한 후에 위의 식에 대입해서 일반해를 구한다.

다음은 확장된 유클리드 알고리즘이다.

void extendedEuclid(int a,int b){

if(b==0) { x = 1; y = 0; d = a ; return ;}    // 기저 사례

extendedEuclid(b, a%b) ; 

int x1 = y;

int y1 = x - (a/b) * y;

x = x1;

y = y1;

}

이를 통해서 x0,y0 를 구한 후에 일반항을 구하면 된다.

8, 프로그래밍 대회에서의 정수론에 대한 첨언

정수론과 관련된 문제가 여러 개 더있지만 그 내용을 하나하나 다룰 수는 없다.

 경험에 따르면, 특히 아시아 지역의 ICPC에 정수론 문제가 자주 출제된다.

 따라서 한 명의 팀원을 정하여 이 정수론, 그리고 그 이상의 정수론 관련 내용에 대해 공부하게 하는 것이 좋을 것이다.

5.확률론

확률론은 무작위적인 현상에 대한 분석을 다루는 수학의 한 분야이다. 

동전 던지기와 같은 개별적인 사건은 무작위적이지만, 무작위 적인 사건이 여러 번 반복되다 보면 그 수열은 특정한 통계적 패턴을 보이게 된다.

 이러한 통계적 특성에 대해 연구하고 예측해볼 수도 있다. 동전의 앞면이 나올 확률은 1/2이다.

 따라서 동전 던지기를 n번 수행 했을때 앞면이 n/2번 나오리라 기대할 수 있다.

프로그래밍 대회의 경우, 확률론과 관련된 문제는 다음 방법 중 하나로 풀 수 있다.

1) 닫힌 형태의 공식 : 이러한 문제는 필요한 공식을 유도해야 하는 문제이다.(보통 O(1) 공식) .  

2)탐색공간(표본 공간) 에 대한 탐색을 수행하여 사건의 수를 세고(보통 구하기 어렵다. 조합론, 완전 탐색, DP 를 사용해야한다) ,

 셀 수 있는 전체 표본 공간의 크기(보통 구하기 훨씬 쉽다) 로 나눈다. 

예를 들면 다음과 같은 경우가 있다.

- 사람 n명이 행사에 참석하기 위하여 그들의 모자 n개를 의류 보관실에 보관해 둔 경우에 대한 문제이다. 

행사가 끝난 후 n명의 사람들은 자신들의 모자를 돌려받는다.

 누군가는 다른 사람의 모자를 잘못 돌려받기도 한다. 

모든 사람이 모자를 잘못 돌려받을 가능성은 얼마나 되는가?

이 문제는 무식한 풀이 방법과 사전 계산을 이용하여 풀 수 있으며, 이는 모든 n!가지의 순열을 시도해보고 그 중에서 몇 번이나 원하는 사건이 일어나는지를 확인하는 것이다. 

이 풀이는 문제의 입력 범위가 n<=12 이기 때문에 가능한 것이다. 

하지만 수학을 좀 더 잘하는 대회 참가자라면 다음과 같은 교란(DP) 공식 An = (n-1) * (An-1 + An-2)를 그 대신에 사용할 것이다.

- 일반적인 정육면체 주사위를 n개 던진다. 각 주사위마다 나온 눈의 합이 x이상일 확률은 얼마인가? 

표본 공간의 크기는 아주 쉽게 계산할 수있다. 6^n 이다. 사건의 수를 구하는 것은 조금 어렵다.

 간단한 DP를 사용해야 하는데, 이는 부분 문제가 아주 많이 중복되기 때문이다. 

상태는 (dice_left,score) 로 표현할 수 있는데, dice_left 는 던질 부터 시작한다.).

 이 문제에 대한 서로 다른 상태의 개수가 24*(24*6) = 3456 가지 밖에 없기 때문에 이러한 DP를 사용할 수 있다. 

만일 dice_left = 0 이라면 score>=x 일 때 1을 반환하고, 그렇지 않을 때는 0을 반환한다. 

만일 dice_left > 0 이라면 주사위를 하나 더 던져본다.

 그 주사위에 대해 나온 눈의 개수를 v라고 해보면, v는 여섯가지 경우중에 하나의 값을 가질 수 있으며 그 다음에는 상태(dice_left -1 , score +v )로 이동하게 된다.

이러한 경우에 대한 사건의 수를 모두 합한다.

 마지막 요구사항은 최대공약수를 이용하여 확률을 나타내는 분수를 약분하라는 것이다. 

다른 어떤 문제의 경우, 확률 값을 소수점 아래 특정 자리까지 정확하게 구해야 할 수도 있다.

6.사이클 찾기

함수 f : S->S(유한집합 S에 속한 자연수를 같은 유한 집합 S에 속한 다른 자연수로 보내는 함수) 와 초깃값 N에 포함된 x0 가 주어졌을 때, 반복함수 값의 수열{x0, x1 = f(x0), ... , xi = f(xi), ... } 에는 반드시 동일한 값이 두번 나타나게 된다.

 즉 xi = xj 를 만족시키는 i < j 가 존재한다.

 이러한 경우가 한 번 발생하고 나면, 그 이후의 수열은 xi 부터 xj-1까지의 값이 반복되는 사이클의 형태가 된다.

 u(사이클의 시작점)를 인덱스 i의 최솟값으로, len(사이클의 길이) Xu = Xu+len 을 만족시키는 최소의 양의 정수로 정의하자. 

사이클 찾기 문제는 f(x) 와 x0이 주어진 상황에서 u와 len 을 찾는 문제이다.

 유사 난수 생성기 f(x) = (Z * x + I) % M과  X0 = L 이 주어졌을 때, 어떤 값이 중복되어 나오기 전까지에 대한 수열의 길이를 구하려 한다(즉 len). 

좋은 유사난수 생성기라면 len 의 값이 커야 한다. 그렇지 않으면 생성된 수들이  '무작위적인' 것처럼 보이지 않을 것이다. 

이러한 과정을 Z = 7, I = 5, M = 12, L = 4 인 작은 테스트 케이스를 예제로하여 살펴보자. 

함수는 f(x) = (7*x + 5) % 12 이고, x0 = 4이다.  반복함수 값 수열은 {4,9,8,1,0,5,4,9,8,1,0,5,...} 이다. 

u = 0, len = 6이 되는데, 이는 X0 = Xu+len = X0+6 = X6 = 4이기 때문이다. 

반복함수 값의 수열은 6번 인덱스 이후로는 사이클을 이룬다.(동일한 값이 계속 반복된다).

 Z = 3, I = 1, M = 4, L = 7 인 또 다른 테스트 케이스를 살펴보면, f(x) = (3*x+1) %4이고 x0 = 7 이다. 

반복함수 값의 수열은 {7,2,3,2,3,...}이다. 이 경우에는 u = 1이고 len = 2이다. 

1)효율적인 자료 구조를 사용하는 풀이

여러 형태의 사이클 찾기 문제에 대해 올바르게 작동하는 간단한 알고리즘이 존재하며, 그 알고리즘은 효율적인 자료 구조를 이용하여 정보의 페어를 저장한다. 

각 정보는 xi 라는 값이 반복함수 값의 수열의 i번째 단계에서 구해졌다는 내용을 담고 있다.

나중에(j>i)  xj 라는 값을 구하게 되면 그 값이 이미 자료구조안에 들어있는지 검사한다.

 만일 들어있다면, Xj = Xi , u = i, len = j-i 라는 의미가 된다.

 이 알고리즘은 수행하는 데 O((u+len) * DS_cost) 시간이 걸리며, DS_cost는 자료 구조에 대한 작업(삽입, 검색) 한번 에 드는 비용을 의미한다.

 이 알고리즘은 과거의 값을 저장하기 위해 최소한 O(u+len)만큼의 공간을 필요로 한다.

 대부분의 사이클 찾기 문제는 S의 크기가 제법 크다. (그리고 u+len가 클 가능성도 높다). 

그러한 경우에는 공간이 O(u+len) 만큼 드는 map 이나 treemap 을 사용할 수 있으며, 그렇게 하면 과거의 값이 몇번 째 단계에서 구해진 것인지를 O(log(u+len)) 시간에 저장하고 확인할 수 있게된다. 

하지만 값이  처음으로 중복되자마자 알고리즘을 종료해도 되는 경우라면 set을 사용해도 좋다.

 그 외에 사이클 찾기 문제는 S의 크기가 상대적으로 작다(그리고 u+len가 작을 가능성도 높다).  

그러한 경우에는 공간이 O(|S|) 만큼 드는 직접 주소 테이블을 사용할 수 있으며, 그렇게 하면 과거의 값이 몇 번째 단계에서 구해진 것인지를 O(1) 시간에 저장하고 확인할 수 있게 된다. 

이 경우, 메모리 공간을 희생하여 실행 속도를 향상시킨 것이다.

2) 플로이드의 사이클 찾기 알고리즘

더 나은 알고리즘도 존재하며, 그 알고리즘은 플로이드의 사이클 찾기 알고리즘이라 불린다. 

이 알고리즘을 수행하는 데는 O(u+len) 시간이 걸리며, 메모리 공간은 단지 O(1)만큼만 사용된다. 

이는 앞에서 살펴본 간단한 알고리즘보다 공간을 훨씬 덜 사용하는 것이다. 

이 알고리즘은 '거북이와 토끼' 알고리즘이라고도 불린다. 

알고리즘은 세 단계로 진행되며 , 앞의 Z = 3, I = 1, M = 4, L = 7 일 떄를 예로 삼아서 각 단계에 대한 내용을 살펴볼 것이다.

효율적으로 사이클 감지하기(klen 구하기)

k > 0일 때, 모든 i >= u에 대해 Xi = Xi+klen 임을 알 수 있다.

 우리는 따라서 klen = i 라고할 때 Xi+i = Xi 가 성립한다는 것을 알 수있다.

 따라서 거북이와 토끼 투 포인터를 X0 에서 시작해서 거북이는 한칸씩 토끼는 두 칸씩이동하다가 값이 같아지는 순간 거북이의 위치가 u0가 된다.

 그 위치를 구한 후에 값이 처음으로 같아지는 것은 len 만큼의 단계가 지난 후이다. 따라서 len 을 구할 수있고 이 알고리즘의 전체 시간 복잡도는 O(u+len) 이다.

7. 게임이론

게임 이론은 전략적 상황(반드시 일반적인 의미의 '게임' 일 필요는 없다) 에 대한 수학적 모델링이며, 참가자의 의사결정을 통한 성공이 다른 참가자의 선택에 영향을 받는 경우를 다룬다. 

게임 이론과 관련된 많은 프로그래밍 문제는 제로섬게임(zero-sum game)으로 분류할 수 있으며, 이는 한 참가자가 승리하면 다른 참가자는 패배하게 되는 경우를 가리키는 수학적 표현이다.

 예를 들어 틱택토, 체스 다양한 수. 정수게임 그리고 그외에 게임은 두 사람이 번갈아가며 진행하고(보통 완전하게) , 승자는 한 사람뿐인 게임이다.

 게임 이론과 관련된 프로그래밍 대회 문제는 대부분 두 사람이 경쟁적인 게임을 진행할 때 먼저 시작한 사람이 승리하게 되는 수가 존재하는지를 묻는다. 

이 때 두 사람이 게임을 진행하는 방식은 완전한 움직임(perfect play) 을 따른다고 가정하는데, 이는 두 사람이 항상 최적인 수만 선택한다고 가정하는 것이다.

1) 결정 트리

풀이법 중 하나는 재귀적인 코드를 작성하여 게임의 결정 트리 혹은 게임 트리라를 탐색하는 것이다. 

만일 부분 문제가 중복되지 않는다면 순수한 형태의 재귀적 퇴각검색이 적합할 것이다. 

그렇지 않다면 동적 계획법이 필요할 수도 있다. 각 정점은 현재 누구의 차례인지, 그리고 게임의 상태가 어떠한지를 나타낸다. 

각 정점은 그 정점으로부터 게임의 규칙에 따라 적법하게 도달할 수 있는 다른 모든 정점들과 연결되어 있다. 

루트정점은 먼저 시작하는 사람이 누구이며 게임의 초기 상태가 승리상태에 해당한다면, 이는 해당 참가자가 게임에서 이겼음을(그리고 다른 참가자는 게임에서 졋음을) 나타낸다.

 내부 정점에 대해서는 해당 참가자가 가장 큰 차이로 승리하는 것을 보장해주는 정점을 선택하여 움직인다.

(혹 승리할 수 없는 경우라면 최소한의 차이로 지는 정점을 선택한다). 

이를 미니맥스(minimax) 전략이라고 한다. 

유클리드의 게임을 문제로 에를 들어보자. 

두 사람이 이게임을 하고 있으며, 둘의 이름은 스탠과 올리이다. 

게임의 상태는 세 개의 정수(id,a,b)로 표현된다. 

현재 순서인 id번 사람은 나머지 두 정수 중에 값이 좀 더 작은 것(정수 b)에 대한 임의의 배수를, 값이 좀 더 큰 것(정수 a) 에서 뺄 수 있다. 

이 때 배수는 양수여야 하며, 그 결과로 얻게 되는 수가 음수가 아니어야 한다. 

또한 항상 a>=b가 만족되도록 상태를 표현한다. 스탠과 올리는 서로 번갈아가며 게임을 진행하며, 작은 수의 배수를 큰 수에서 뺌으로써  0을 얻게 되는 사람이 승리하게 된다. 

게임은 스탠의 차례부터 시작된다. 

이 게임의 대해서 초기 상태가 id = 0 , a = 34 , b= 12 인 경우에 대한 결정 트리가 다음 그림에 나와있다.(생략)

그냥 dp 로풀 수 있는 문제.

2) 풀이가 빨리지도록 하기 위한 수학적 통찰

게임의 결정 트리 전체를 탐색하는 방법으로는 모든 게임 이론 문제를 풀 수 있는 것은 아니다. 

특히 트리의 크기가 클 때 그러하다.. 만일 문제에서 다루는 대상이 수라면 약간의 수학적 통찰력을 동원하여 계산이 빨라지도록 할 수 있다. 

곱셈게임을 예로 들어보자. 두 사람이 게임을 하고있으며 스탠과 올리 라고 한다. 

게임의 상태는 정수 p로 표현된다. 현재 순서인 사람은 p에 2부터 9까지 임의의 수를 곱할 수 있다. 

스탠과 올리는 이번에도 번갈아가며 게임을 진행하며 p에 2부터 9까지의 수 를 곱하여 p>=n 이 되도록 만드는 사람이 승리하게 된다. 

게임은  p = 1 로 두고 스탠의 차례부터 시작된다.  처음에는 0번사람이 여덟가지 중의 하나를 선택할 수 있다. 

하지만 모든 여덟가지의 상태는 1번 사람에 대한 승리인데 , 이는모든 경우에 대해 1 번사람이 그때의 p값에 수를 곱하여 p >= 17 이 되도록 만들 수 있기 때문이다.  따라서 0번 사람은 반드시 패배하게 된다.

1 < n < 4294967295 이므로 , 가장 큰 테스트 케이스에 대한 결정 트리는 매우 커질 수 있다. 

이는 이 결정 트리의 각 정점마다 분기가 8배로 불어나기 떄문이다. 이러한 결정 트리를 탐색하는 것은 현실적으로 실현 불가능하다. 

하지만 문제를 분석해보면 스탠이 택할 수 있는 최적의 전략은 항상 p에 9를 곱하는 것임을, 그리고 올리가 택할 수 있는 최적의 전략은 항상 p에 2를 곱하는 것임을 알 수있다. 

이 문제에 대해 작은 크기의입력을 적용해보고 , 출력에 어떠한 패턴이 발견되는지를 관찰하면 최적화에 대한 이러한 통찰을 얻을 수 있다. 

수학에 소질이 있는 대회 참가자라면 풀이를 코딩하기에 앞서서 이러한 관찰을 증명해볼 수도 있을 것이다.

3)님게임

프로그래밍 대회에 나올법한 특수한 형태의 게임 하나를 언급해두는 것이 좋을것 같다. 

바로 님 게임이다. 님 게임은 두 사람이 차례를 번갈아가며 진행하며, 물체가 쌓여있는 서로 다른 더미에서 그 물체를 치우는 것이 그 내용이다. 

각 차례를 진행하는 사람은 같은 더미에 대해서만 물체를 치울 수 있고, 반드시 하나는 치워야 하며 한 번에 몇개씩이라도 치울 수 있다. 

게임의 초기 상태는 각 k개의 더미마다 ni개씩의 물체가 쌓여있음을 뜻하는 {n1,n2,...nk}이다. 이 게임에 대한 멋진 풀이가 존재한다. 

첫번째 사람이 게임에서 승리하려면 n1 ^ n2 ^ ... ^ nk 의 값이 반드시 0이 아니어야 한다. 이 때 ^는 비트연산 xor을 의미한다.증명은 생략.(증명은 http://blog.myungwoo.kr/27 참조)