반응형

문제 링크: https://www.acmicpc.net/problem/2749

 

2749번: 피보나치 수 3

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

<문제 풀이> 수학, 선형대수학, 행렬 거듭제곱

n이 매우 크기 때문에 dp를 이용한 점화식 풀이는 O(N)이므로 해결할 수 없다 따라서 점화식을 행렬로 변환해서 O(M^3 * logN) 시간 복잡도의 빠른 행렬 거듭제곱 알고리즘을 사용해야 한다. 
(이 문제는 피사노 주기도 사용 가능)

 

<피보나치 수 점화식을 행렬로 표현하기>

 

위와 같은 피보나치 수 점화식을 아래와 같이 행렬로 표현할 수 있다.

 

 

이렇게 행렬을 구하면 다음 아래의 행렬을 계산해서 c + d를 하면 Fn+1을 구할 수 있다. 

Fn을 구하기 위해서 다음식의 양변에 n - 1을 대입한다.

그러면 다음과 같은 식을 얻을 수 있다

이제 {{1, 1}, {1, 0}} 행렬의 n-1 거듭제곱을 빠르게 구하면 된다.

(행렬 거듭제곱 알고리즘은 정수 거듭제곱 알고리즘과 똑같이 구현하면 됩니다.)

 

<C++ 소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef vector<vector<ll> > matrix;
 
matrix operator * (const matrix &a, const matrix &b) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            for (ll k = 0; k < size; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= 1000000;
        }
    }
    return res;
}
 
matrix power(matrix a, ll n) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) { // 단위 행렬
        res[i][i] = 1;
    }
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * a;
        }
        n /= 2;
        a = a * a;
    }
    return res;
 
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin >> n;
    matrix a = { {1, 1}, {1, 0} };
    matrix res = (power(a, n - 1));
    cout << (res[1][0] + res[1][1]) % 1000000;
    
 
    return 0;
}
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 12728번] n제곱 계산  (0) 2020.03.01
[백준 11444번] 피보나치 수 6  (0) 2020.02.29
[백준 10830번] 행렬 제곱 - (빠른 거듭제곱 알고리즘)  (2) 2020.02.28
[백준 10854번] Divisions  (0) 2020.02.25
[백준 5615번] 아파트 임대  (0) 2020.02.22
반응형

문제 링크: https://www.acmicpc.net/problem/10830

 

10830번: 행렬 제곱

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

<문제 풀이> 행렬, 선형대수학

 

이 문제에서 A ^ N을 A* A* A*.... A*N 이렇게 구하면 O(N)의 시간 복잡도가 걸리므로 시간 초과가 나게 됩니다. 따라서 O(logN)의 시간 복잡도에 거듭제곱을 할 수 있는 알고리즘을 사용해야 됩니다.

 

<빠른 거듭제곱 알고리즘> O(logN)

-----------------------------------------------------------------------------

N이 홀수이면 A^N을 A * A^(N-1)로 바꾸고 A를 결과값에 곱한다

 

N이 짝수이면 A^N을 (A^2)^(N/2) 즉 A를 제곱하고 N을 2로 나눈다

 

N = 0 이면 종료

-----------------------------------------------------------------------------

 

2^5를 구하는걸 예로 들어보겠습니다.

n = 5

res = 1

 

2^5 = 2 * 2^4  (n이 홀수일 때 밑을 하나 꺼내서 n을 짝수로 만든다) -> n = 4

res = res * 2; (꺼낸 수를 결과값에 저장한다) res = 2

 

2^4 = (2^2)^2 = 4^2 (n이 짝수일 때 밑을 제곱하고 n을 2로 나눈다) -> n = 2

 

4^2 = 16^1 (n이 짝수일때 밑을 제곱하고 n을 2로 나눈다) -> n = 1

 

16^1 = 16 * 16^0 = 16 (n이 홀수일 때 밑을 하나 꺼내서 n을 짝수로 만든다) -> n = 0

res = res * 16; (꺼낸 수를 결과값에 저장한다) res = 32

 

n == 0이면 종료

 

 

행렬을 제곱할 때도 이 알고리즘을 사용하면 됩니다.

 

<c++ 소스 코드> 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef vector<vector<ll> > matrix;
 
matrix operator * (const matrix &a, const matrix &b) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            for (ll k = 0; k < size; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= 1000;
        }
    }
    return res;
}
 
matrix power(matrix a, ll n) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) { // 단위 행렬
        res[i][i] = 1;
    }
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * a;
        }
        n /= 2;
        a = a * a;
    }
    return res;
 
}
 
void PrintMatrix(const matrix& a) {
    ll size = a.size();
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            cout << a[i][j] << " ";
        }
        cout << '\n';
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, b;
    cin >> n >> b;
    matrix a(n, vector<ll>(n));
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    PrintMatrix(power(a,b));
 
    return 0;
}
 
 cs
 

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 11444번] 피보나치 수 6  (0) 2020.02.29
[백준 2749번] 피보나치 수 3  (0) 2020.02.29
[백준 10854번] Divisions  (0) 2020.02.25
[백준 5615번] 아파트 임대  (0) 2020.02.22
[백준 4149번] 큰 수 소인수분해 - 폴라드로(PollardRho) + 밀러라빈(MillerRabin)  (0) 2020.02.21
반응형

문제 링크: https://www.acmicpc.net/problem/10854

 

10854번: Divisions

David is a young boy and he loves numbers. Recently he learned how to divide two numbers. David divides the whole day. He is happy if the result of the division is an integer, but he is not very amused if this is not the case. After quite a while he decide

www.acmicpc.net

 

<참조>

https://seokjin2.tistory.com/5

 

<문제 풀이> 수학, 정수론, 폴라드로(Pollard-Rho), 밀러라빈(Miler-Rabin)

폴라드로 알고리즘으로 O(N^(1/4))에 소인수 분해하고 약수의 개수를 구하면 된다.

n == 1일 때 따로 처리

 

<소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import sys
import random
sys.setrecursionlimit(10 ** 6)
n = int(input())
 
 
def power(x, y, p):
    res = 1
    x = x % p
    while y > 0:
        if y & 1:
            res = (res * x) % p
        y = y >> 1
        x = (x*x) % p
    return res
 
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        r = a % b
        a = b
        b = r
    return a
 
def miller_rabin(n, a):
        r = 0
        d = n-1
        while d % 2 == 0:
            r += 1
            d = d//2
 
        x = power(a, d, n)
        if x == 1 or x == n-1:
            return True
 
        for i in range(r-1):
            x = power(x, 2, n)
            if x == n - 1:
                return True
        return False
 
def is_prime(n):
    alist = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
    if n == 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    for a in alist:
        if n == a:
            return True
        if not miller_rabin(n, a):
            return False
    return True
 
 
def pollardRho(n):
    if is_prime(n):
        return n
    if n == 1:
        return 1
    if n % 2 == 0:
        return 2
    x = random.randrange(2, n)
    y = x
    c = random.randrange(1, n)
    d = 1
    while d == 1:
        x = ((x ** 2 % n) + c + n) % n
        y = ((y ** 2 % n) + c + n) % n
        y = ((y ** 2 % n) + c + n) % n
        d = gcd(abs(x - y), n)
        if d == n:
            return pollardRho(n)
    if is_prime(d):
        return d
    else:
        return pollardRho(d)
 
list = []
while n > 1:
    divisor = pollardRho(n)
    list.append(divisor)
    n = n // divisor
 
if len(list) > 0:
    list.sort()
    prev = list[0]
    cnt = 0
    res = 1
    for i in list:
        if i == prev:
            cnt += 1
        else:
            res *= (cnt + 1)
            cnt = 1
            prev = i
    res *= (cnt + 1)
    print(res)
else:
    print(1)
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2749번] 피보나치 수 3  (0) 2020.02.29
[백준 10830번] 행렬 제곱 - (빠른 거듭제곱 알고리즘)  (2) 2020.02.28
[백준 5615번] 아파트 임대  (0) 2020.02.22
[백준 4149번] 큰 수 소인수분해 - 폴라드로(PollardRho) + 밀러라빈(MillerRabin)  (0) 2020.02.21
[백준 9938번] 방 청소  (0) 2020.02.15
반응형

문제 링크: https://www.acmicpc.net/problem/5615

 

5615번: 아파트 임대

문제 동규부동산에서 아파트를 임대하고 있다. 아파트의 방은 아래 그림과 같이 면적이 2xy + x + y이다. (x와 y는 양의 정수) 동규부동산의 카탈로그에는 아파트의 면적이 오름차순으로 적혀져 있지만, 이 중 일부는 있을 수 없는 크기의 아파트이다. 만약, 이런 크기의 아파트를 임대하겠다고 말하면, 동규는 꽝! 이라고 외치면서, 수수료만 떼어간다. 동규부동산의 카탈로그에 적힌 아파트의 면적이 주어졌을 때, 있을 수 없는 크기의 아파트의 수를 구하는 프

www.acmicpc.net

<참조>

Miller-Rabin

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

 

<문제 풀이> 수학, 정수론, Miller-Rabin(밀러-라빈) 소수 판별법

2xy + x + y = s라고 하고 인수분해 꼴로 만들면 (2x+1)(2y +1) = (2s + 1)이라고 쓸 수 있습니다.

-> (x+1)(y+1)에서 접근

 

x, y가 각각 양의 정수라고 했으므로 (2x+1) >= 3, (2y + 1) >= 3을 만족하므로 2s+1은 3이상의 두 홀수의 곱으로 표현이 되므로 소수의 정의에 의해서 절대 소수가 나올 수 없습니다.

 

따라서 2s + 1이 소수임을 판별하면 됩니다. (소수이면 있을 수 없는 아파트)

 

문제에서 s의 범위가 2^31 -1 이하이므로 2 * s + 1을 일반적인 소수 판별을 하면 시간 초과이므로 Miller-Rabin(밀러-라빈) 소수 판별법을 사용해야 됩니다.

 

<소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
using namespace std;
 
typedef unsigned long long ull;
 
ull power(ull x, ull y, ull p) {
    ull res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1) {
            res = (res * x) % p;
        }
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
bool miller_rabin(ull n, ull a) {
    ull r = 0;
    ull d = n - 1;
    while (d % 2 == 0) {
        r++;
        d = d >> 1;
    }
    ull x = power(a, d, n);
    if (x == 1 || x == n - 1) return true;
    for (int i = 0; i < r - 1; i++) {
        x = power(x, 2, n);
        if (x == n - 1) return true;
    }
    return false;
    
 
}
 
bool isPrime(ull n) {
    ull alist[5] = { 2, 3, 5, 7, 11 };
    if (n <= 1) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    for (int i = 0; i < 5; i++) {
        ull a = alist[i];
        if (n == a) return true;
        if (!miller_rabin(n, a)) return false;
    }
    return true;
 
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, cnt = 0;
    cin >> n;
    while (n--) {
        ull s;
        cin >> s;
        if(isPrime(2*s+1)) cnt++;
    }
    cout <<cnt;
    return 0;
}
 
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2749번] 피보나치 수 3  (0) 2020.02.29
[백준 10830번] 행렬 제곱 - (빠른 거듭제곱 알고리즘)  (2) 2020.02.28
[백준 10854번] Divisions  (0) 2020.02.25
[백준 4149번] 큰 수 소인수분해 - 폴라드로(PollardRho) + 밀러라빈(MillerRabin)  (0) 2020.02.21
[백준 9938번] 방 청소  (0) 2020.02.15
반응형

문제 링크: https://www.acmicpc.net/problem/4149

 

4149번: 큰 수 소인수분해

문제 큰 수를 소인수 분해 해보자. 입력 입력은 한 줄로 이루어져 있고, 소인수 분해 해야 하는 수가 주어진다. 이 수는 0보다 크고, 262보다 작다. 출력 입력으로 주어진 양의 정수를 소인수 분해 한 뒤, 모든 인수를 한 줄에 하나씩 증가하는 순서로 출력한다.  예제 입력 1 복사 18991325453139 예제 출력 1 복사 3 3 13 179 271 1381 2423...

www.acmicpc.net

<참조>

Pollrad's Rho Algorithm

https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm#The_results

https://www.geeksforgeeks.org/pollards-rho-algorithm-prime-factorization

Miller-Rabin

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Miller%E2%80%93Rabin_test

 

<문제 풀이> 수학, 정수론, 폴라드로(Pollard-Rho), 밀러라빈(Miler-Rabin)

O(N^(1/4))에 소인수 분해를 할 수 있는 폴라드로 알고리즘을 사용하면 되는데 특정 소수에 대해서는 무한루프가 생긴다. 따라서 소수임을 O(k * log^3n) 다항 시간에 판별할 수 있는 밀러라빈 알고리즘을 함께 써야 한다.

밀러라빈을 구현할 때 빠른 거듭제곱 알고리즘 사용

 

<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import sys
import random
sys.setrecursionlimit(10 ** 6)
n = int(input())
 
 
def power(x, y, p):
    res = 1
    x = x % p
    while y > 0:
        if y & 1:
            res = (res * x) % p
        y = y >> 1
        x = (x*x) % p
    return res
 
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        r = a % b
        a = b
        b = r
    return a
 
def miller_rabin(n, a):
        r = 0
        d = n-1
        while d % 2 == 0:
            r += 1
            d = d//2
 
        x = power(a, d, n)
        if x == 1 or x == n-1:
            return True
 
        for i in range(r-1):
            x = power(x, 2, n)
            if x == n - 1:
                return True
        return False
 
def is_prime(n):
    alist = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
    if n == 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    for a in alist:
        if n == a:
            return True
        if not miller_rabin(n, a):
            return False
    return True
 
 
def pollardRho(n):
    if is_prime(n):
        return n
    if n == 1:
        return 1
    if n % 2 == 0:
        return 2
    x = random.randrange(2, n)
    y = x
    c = random.randrange(1, n)
    d = 1
    while d == 1:
        x = ((x ** 2 % n) + c + n) % n
        y = ((y ** 2 % n) + c + n) % n
        y = ((y ** 2 % n) + c + n) % n
        d = gcd(abs(x - y), n)
        if d == n:
            return pollardRho(n)
    if is_prime(d):
        return d
    else:
        return pollardRho(d)
 
list = []
while n > 1:
    divisor = pollardRho(n)
    list.append(divisor)
    n = n // divisor
 
list.sort()
 
for i in list:
    print(i)
 cs

 

 

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2749번] 피보나치 수 3  (0) 2020.02.29
[백준 10830번] 행렬 제곱 - (빠른 거듭제곱 알고리즘)  (2) 2020.02.28
[백준 10854번] Divisions  (0) 2020.02.25
[백준 5615번] 아파트 임대  (0) 2020.02.22
[백준 9938번] 방 청소  (0) 2020.02.15
반응형

문제 링크: https://www.acmicpc.net/problem/9938

 

9938번: 방 청소

문제 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다.  서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다. 은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대

www.acmicpc.net

<문제 풀이> Union-Find(유니온-파인드), Disjoint-Set(서로소집합)

 

 

각 병에 대해서 A서랍, B서랍을 노드로 생각하고 그래프를 만듭니다. 여기서 부모 노드를 비어있는 서랍, 자식 노드를 병이 들어가 있는 서랍이라고 하면 그래프로 쉽게 문제를 해결할 수 있습니다.

 

서랍에 병을 넣을 때마다 넣었는지 여부를 체크해줍니다.

 

1. 서랍 A가 비어있다면 A를 자식 노드로 하고 B를 부모 노드로 한다. 

 

2. 서랍 B가 비어있다면 B를 자식 노드로 하고 A를 부모 노드로 한다.

 

3. 서랍 A에 부모 노드가 방문이 안됐으면(병을 옮길 수 있으면) 서랍 A에 부모 노드를 자식 노드로 하고 B를 부모 노드로 한다.

 

4. 서랍 B에 부모 노드가 방문이 안됐으면(병을 옮길 수 있으면) 서랍 B에 부모 노드를 자식 노드로 하고 A를 부모 노드로 한다.

 

서랍에 병이 들어있을 때 병을 다른 서랍으로 옮기는 과정들을 Union 연산으로 한 그래프를 만든다고 생각하고 빈 서랍을 찾는 데는 Find 연산으로 부모 노드를 찾는다고 생각하면 됩니다.

 

 

 

<C++ 소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
using namespace std;
 
int node[300001];
bool visited[300001];
 
int Find(int x) {
    if (x == node[x]) return x;
    return node[x] = Find(node[x]);
}
 
void Union(int x, int y) {
    int xParents = Find(x);
    int yParents = Find(y);
    node[xParents] = yParents;
}
 
int main(void) {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, L;
    
    cin >> N >> L;
    
    for (int i = 1; i <= L; i++) {
        node[i] = i;
    }
 
    while (N--) {
        int a, b;
        cin >> a >> b;
        if (!visited[a]) {
            visited[a] = true;
            Union(a, b); //a의 부모를 b로
            cout << "LADICA\n";
        }
        else if (!visited[b]) {
            visited[b] = true;
            Union(b, a); //b의 부모를 a로
            cout << "LADICA\n";
        }
        else if (!visited[Find(node[a])]) {
            visited[Find(node[a])] = true; 
            Union(a, b); //a의 부모를 b로
            cout << "LADICA\n";
        }
        else if (!visited[Find(node[b])]) {
            visited[Find(node[b])] = true;
            Union(b, a); //b의 부모를 a로
            cout << "LADICA\n";
        }
        else {
            cout << "SMECE\n";
        }
    }
 
    return 0;
}
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2749번] 피보나치 수 3  (0) 2020.02.29
[백준 10830번] 행렬 제곱 - (빠른 거듭제곱 알고리즘)  (2) 2020.02.28
[백준 10854번] Divisions  (0) 2020.02.25
[백준 5615번] 아파트 임대  (0) 2020.02.22
[백준 4149번] 큰 수 소인수분해 - 폴라드로(PollardRho) + 밀러라빈(MillerRabin)  (0) 2020.02.21

+ Recent posts

티스토리툴바