180617.md

June 26, 2018 · View on GitHub

수학2-2(카탈란 수, 오일러 피 함수, 유클리드 알고리즘, 나머지 연산, 순열)

관련 문제들

[issue]에 대한 정리

[#issue1] 카탈란 수의 개념과 적용 사례

* 카탈란 수(Catalan number)는 이진 트리의 수 따위를 셀 때 등장하는 수열이다.
* 기호로는 Cn로 나타낸다.

* 적용 사례
    1. 잘 짜인 괄호
        * n쌍의 ()를 잘 짜인 모양으로 늘어놓는 방법의 수
    2. 산 만들기 
        * 괄호와 마찬가지로 오르막과 내리막을 n쌍으로 산을 만들 수 있는 방법의 수
    3. 대각선 피해가기
        * 정사각형들로 이루어진 (n x n)개의 커다란 정사각형들의 변을 따라 이동할 때 대각선과 만나지 않고 이동하는 방법의 수
    4. 다각형을 삼각형으로 나누기
        * (n + 2)개의 변으로 이루어진 볼록 다각형을 서로 만나지 않는 대각선을 사용하여 n개의 삼각형으로 나누는 방법의 수
        
* 공식
    * n쌍의 괄호를 잘 짜인 모양으로 늘어놓는 방법의 수: Cn
    * C0, C1, C2, ... , Cn-1 -> Cn을 찾아보자.
    * (n-1)쌍의 괄호가 잘 짜여진 상태에서 ()를 알맞은 곳에 넣어주는 방법을 세면 된다.
    * (A)B와 같이 넣을 때, 
        * A와 B도 잘 짜여져 있어야 하고,
        * A에 괄호가 k쌍이 있으면 B에는 (n-1-k)쌍이 있어야 한다.
    * 점화식:
        * C1 = C0⋅C0
        * C2 = C0⋅C1 + C1⋅C0
        * C3 = C0⋅C2 + C1⋅C1 + C2⋅C0 
        * C4 = C0⋅C3 + C1⋅C2 + C2⋅C1 + C3⋅C0
        * Cn = C0⋅Cn−1 + C1⋅Cn−2 + C2⋅Cn−3 + ⋯ + Cn−2⋅C1 + Cn−1⋅C0
            * Cn = sum{i=0~(n-1)} (Ci ⋅ Cn-i-1)
    * 일반항: 
        * 2nCn - 2nCn+1 <=> (2nCn) / (n+1)

[#issue1-1] 카탈란 수 구하는 방법

  • [방법1] 재귀함수를 통한 카탈란의 수 구하기
    • 카탈란의 수의 점화식 이용: Cn = sum{i=0~(n-1)} (Ci * Cn-i-1)
    • n이 커지면 시간복잡도가 매우 커진다. -> [방법2] 이용
public long getCatalan(int n){
    int res = 0;

    if (n <= 1) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        res += getCatalan(i) * getCatalan(n - i - 1);
    }
    return res;
}
  • [방법2] 반복문을 통한 카탈란의 수 구하기
    • 카탈란의 수의 점화식 이용: Cn = sum{i=0~(n-1)} (Ci * Cn-i-1)
    • 여는 괄호와 닫는 괄호가 n이고, n의 최댓값이 MAX 일 때
static long getCatalan2(int n){
    long d[] = new long[MAX + 1];
    d[0] = 1; // C0 = 1

    // EX) C4 = C0C3 + C1C2 + C2C1 + C3C0
    for (int i = 1; i <= MAX; i++){
        d[i] = 0;

        for(int j = 0; j < i; j++){
            d[i] += d[j] * d[i-1-j];
            d[i] %= MOD;
        }
        d[i] %= MOD;
    }
    return d[n];
}

[#issue2] 오일러 피 함수의 개념과 활용

* 오일러 피 함수란
    * 1 ~ n 까지의 양의 정수 중 n과 서소로인 수의 개수를 구하는 것
    * 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 중에, 11 이외에는 모두 11과 서로소이다. 그러므로 11-1=10 따라서, φ(11)=10
* 오일러 피 함수의 성질
    * 소수 p의 경우 오일러 파이 함수의 값은 φ(p)=p-1 이다. 
    * 일반적으로 φ는 곱셈적 함수다. 즉, m, m이 서로소인 정수일 때, φ(mn) = φ(m)φ(n)이다.
* 오일러 피 함수의 활용
    * 정n각형이 작도 가능한 다각형인지, 즉 눈금없는 자와 컴퍼스만으로 작도할 수 있는지는 φ(n)이 2의 거듭제곱수인지와 동치이다.
    * 또한 오일러 피 함수는 암호학의 RSA 암호에서도 핵심적인 역할을 한다.

[#issue2-1] 오일러 피 함수 구하는 방법

long res = n;

for (long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
        while (n % i == 0) {
            n /= i;
        }
        res -= res / i;
    }
}

if (n > 1) {
    res -= res / n;
}

return res;

[#issue3] 사전순으로 다음에 오는 순열

1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다. (즉, 순열의 마지막 수에서 끝나는 가장 긴 감소수열을 찾는다.)
2. j>=i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다.
3. A[i-1]과 A[j]를 swap한다.
4. A[i]부터 순열을 뒤집는다.
  • 사전순으로 다음에 오는 순열을 구하는 방법
 // 1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
// (즉, 순열의 마지막 수에서 끝나는 가장 긴 감소수열을 찾는다.)
int i = arrays.length - 1;
while (i > 0 && arrays[i-1] >= arrays[i])
    i--;

// 마지막 순열 (이미 사전순으로 정렬된 상태, 전체가 감소수열)
if (i <= 0)
    return false;

// 2. j>=i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다.
int j = arrays.length - 1;
while (arrays[j] <= arrays[i-1])
    j--;

// 3. A[i-1]과 A[j]를 swap한다.
int tmp;
tmp = arrays[i-1];
arrays[i-1] = arrays[j];
arrays[j] = tmp;

// 4. A[i]부터 순열을 뒤집는다.
int k = arrays.length - 1;
while (i < k) {
    tmp = arrays[i];
    arrays[i] = arrays[k];
    arrays[k] = tmp;
    i++;
    k--;
}
return true;

Reference

:house: Go Home