180610.md

June 25, 2018 · View on GitHub

수학2-1(제곱, 행렬, 피보나치의 수, 이항계수, 파스칼의 삼각형)

관련 문제들

[issue]에 대한 정리

[#issue1] 분할정복을 이용하여 제곱을 구하는 방법

* a^b 구하기
* 직관적으로 제곱을 구하는 방법은 많은 시간이 걸린다.
    * for(int i=1; i<=b; i++){ result *= a }
    * 시간 복잡도: O(b)
    
* a^b에서 b가 매우 큰 경우 1) 이진수, 2) 분할정복을 이용하여 푼다.

* 분할정복을 이용하여 제곱을 구하는 방법
    1) b=0 이면, 1
    2) b=1 이면, a
    3) a^2b = a^b * a^b
    4) a^(2b+1) = a^2b * a
    * 위와 같이 경우를 나누어 제곱을 구한다.

int calc(int a, int b) {
    if (b == 0) {
        return 1;
    } else if (b == 1) {
        return a;
    } else if (b % 2 == 0) {
        int temp = calc(a, b/2);
        return temp * temp;
    } else { // b % 2 == 1
        return a * calc(a, b-1);
    }
}

[#issue2] 이진수의 원리를 이용하여 제곱을 구하는 방법

* a^b 구하기
* 이진수의 원리를 이용하여 제곱을 구하는 방법
    * 예를 들어, $3^{27}$인 경우 
    * 27 = 11011(2) = 1 + 2 + 8 + 16
        * b의 이진수의 자릿수가 1일 때의 값을 곱한다.
    * $3^{27}$ = 3^(1 + 2 + 8 + 16)
    * $3^{27}$ = $3^{1}$ * $3^{2}$ * $3^{8}$ * $3^{16}$
        * a를 계속해서 a*a로 곱해가면서 제곱을 구한다.

int calc(int a, int b) {
    int ans = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            ans *= a; 
        }
        a = a * a;
        b /= 2; 
    }
    return ans; 
}

[#issue3] 행렬의 곱 구하기

private static int[][] mul(int[][] a, int[][] b) {
    int n = a.length;
    int resultMatrix[][] = new int[n][n];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                resultMatrix[i][j] += a[i][k] * b[k][j];
            }
            resultMatrix[i][j];
        }
    }
    return resultMatrix;
}

[#issue4] 피사노 주기의 개념과 구하는 방법

* 피사노 주기의 개념
    * 피보나치 수열을 M으로 나눈 나머지는 주기를 이룬다.
    * 이 주기를 피사노 주기라고 한다.
    * 즉, n번째 피보나치 수를 M으로 나눈 나머지 == N % (피사노의 주기)번째의 피보나치의 수를 M으로 나눈 나머지
* 피사노의 주기의 특징
    * 나눌 수 M = 10^k 일 때, K > 2 이면 피사노 주기는 항상 15 * 10^(k-1)
    * 피보나치 수열은 "1, 1, "로 시작하므로 피보나치 수열을 M으로 나눈 나머지가 또 다시 1이 연속("1, 1, ")으로 나올 때, 또 다른 주기가 시작된다.
  • 피사노 주기 구하는 방법
int mod = s.nextInt();
int f1 = 1, f2 = 1, f3;
int period = 0;

while (true) {
    f3 = (f1 + f2) % mod;

    f1 = f2;
    f2 = f3;
    period++;

    if (f1 == 1 && f2 == 1) {
        return period;
    }
}

[#issue5] 음수 번째의 피보나치의 수에 대한 규칙성

1. n = -k, n = k에 대한 피보나치의 절댓값은 같다.
    * Ex) fibo[-4]의 절댓값 == fibo[4]의 절댓값
2. n = -k(음수)일 때, k가 짝수이면 음의 피보나치 값을 갖는다.
    * Ex) fibo[-4] < 0, fibo[-5] > 0

[#issue6] 이항계수 구하는 방법

* 이항계수란
    * 주어진 크기의 (순서 없는) 조합의 가짓수이다.
* 이항계수의 표현
    * C(n, k) = nCk = [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1] 
* 이항계수의 값을 삼각형 모양으로 나열한 표를 파스칼의 삼각형이라고 한다.
* 이때, 12! < int의 범위 < 13!를 주의하자.

long res = 1;

// C(n, k) = C(n, n-k)
if (k > n - k)
    k = n - k;

// nCk = [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
for (int i = 0; i < k; i++) {
    res *= (n - i);
    res /= (i + 1);
}

return res;

Reference

:house: Go Home