http://min92.tistory.com/70


오일러 파이 함수를 통해서 풀면

파이는 1~n까지의 수 중에서 n과 서로소인 수의 갯수이다.




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
#include <cstdio>
#include <iostream>
#include <math.h>
 
using namespace std;
 
int prime[50];
int primeCopy[50];
 
int primeCopy2[50];
int primeCopyPower[50];
 
void function(int firstInputNumber)
{
    int i, primeIndex, inputNumber;
    int x;
    primeIndex = 0;
    inputNumber = firstInputNumber;
    
    //소인수분해
    for(i = 2; i < inputNumber; i++)
    {
        if(inputNumber % i == 0)
        {
            prime[primeIndex] = i;
            primeIndex++;
            inputNumber /= i;
            i = 1;
        }
    }
    
    x = inputNumber;
    
    i = 0;
    
    while(firstInputNumber != x)
    {
        x = x * prime[i];
        i++;
    }
    prime[i] = inputNumber;
    
    //primeCopy에는 소인수분해해서 최소공배수들이 모임
    for(int j = 0; j <= i; j++){
        primeCopy[j] = prime[j];
    }
    
    //primeCopy2에는 소인수분해해서 최소공배수가 중복되지 않게 넣음
    //primeCopyPower에는 각자의 최소공배수가 몇 개씩 있는지를 넣음
    int k = 0;
    for(int j = 0; primeCopy[j] != 0; j++){
        if(j != 0){
            if(primeCopy[j] == primeCopy[j-1]){
                primeCopyPower[k]++;
            }else{
                k++;
                primeCopyPower[k]++;
                primeCopy2[k] = primeCopy[j];
            }
        }
        else{
            primeCopyPower[k]++;
            primeCopy2[k] = primeCopy[j];
        }
    }
}
 
int main(){
    int N;
    int result = 1;
    
    while(1){
        cin >> N;
        if(N == 0) break;
        
        //initialization
        for(int k = 0; k < 50; k++){
            prime[k] = 0;
            primeCopy[k] = 0;
            primeCopy2[k] = 0;
            primeCopyPower[k] = 0;
            result = 1;
        }
        
        function(N);
        
        //오일러의 파이 함수 정리
        for(int j = 0; primeCopy2[j] != 0; j++){
            result *= pow(primeCopy2[j], primeCopyPower[j]) - pow(primeCopy2[j], primeCopyPower[j]-1);
        }
        printf("%d\n", result);
    }
    
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11650번] 좌표 정렬하기 - sort [C++]  (0) 2017.09.19
[11758번] CCW - CCW 알고리즘[C++]  (0) 2017.08.24
[1463번] 1로 만들기 - 동적계획법 [C++]  (0) 2017.05.11
[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27

https://m.blog.naver.com/PostView.nhn?blogId=thqkdrhks22&logNo=150130493315&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F


https://nuriwiki.net/wiki/index.php/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98



오일러 피 함수

누리위키, 온 누리의 백과사전

오일러 피 함수(Euler's phi function) 또는 오일러 파이 함수 ϕ(n)이란 어떤 자연수 n보다 작거나 같은 자연수 중에서 n과 서로소인 것의 개수를 나타내는 함수이다. 예를 들어, ϕ(8)=∣{1,3,5,7}∣=4이다. 이것을 수식으로 표현하면 다음과 같다: 

ϕ(n)=∣{a∈N|1≤a≤n,(a,n)=1}∣.

성질[편집]

p는 소수라고 하자.

  • ϕ(p)=p−1.
    • 역으로, ϕ(n)=n−1이라면, n은 소수이다.
  • ϕ(pa)=pa−pa−1.
  • (m,n)=1이라면, ϕ(mn)=ϕ(m)ϕ(n)이다. (오일러 피 함수는 곱셈적 함수이다.)




'Study > Algorithms' 카테고리의 다른 글

[Algorithm] 중국인의 나머지 정리 Chinese remainder theorem  (0) 2017.08.31
[Algorithm] 확장 유클리드 알고리즘 Extended Euclid Algorithm  (0) 2017.08.31
[Algorithm] Convex Hull Algorithm  (0) 2017.08.24
[Algorithm] CCW Algorithm [펌]  (0) 2017.08.24

중국인의 나머지 정리는, 어떤 수 x를 서로소인 m1, m2, m3, ..., mn으로 각각 나눴을 때 나머지가 a1, a2, a3, ..., an 이라고 할 때 x는 m1* m2 * m3 * ... * mn 의 modular 연산 안에서 해가 유일하다는 것을 말한다. 


https://librewiki.net/wiki/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98_%EB%82%98%EB%A8%B8%EC%A7%80_%EC%A0%95%EB%A6%AC


http://blog.naver.com/PostView.nhn?blogId=rym&logNo=220833505480&categoryNo=0&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView

'Study > Algorithms' 카테고리의 다른 글

[Algorithm] 오일러 파이(피) 함수 Euler's phi function  (0) 2017.08.31
[Algorithm] 확장 유클리드 알고리즘 Extended Euclid Algorithm  (0) 2017.08.31
[Algorithm] Convex Hull Algorithm  (0) 2017.08.24
[Algorithm] CCW Algorithm [펌]  (0) 2017.08.24

http://codepractice.tistory.com/79




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
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
 
using namespace std;
 
int RecursiveEuclid(int a, int b)
{
    if (a < b)
        swap(a, b);
 
    if (a%b == 0)
        return b;
    else
        return RecursiveEuclid(b, a%b);
}
 
template<typename T>
T LoopEuclid(T a, T b)
{
    if (a < b)
        swap(a, b);
 
    while (a%b != 0)
    {
        T tmp = a;
        a = b;
        b = tmp%b;
    }
    return b;
}
 
 
template<typename T>
pair<T, T> ExtendedEuclid(T a, T b)
{
    T q = (a / b);
    T r = a%b;
    T s1, s2, t1, t2;
    s1 = 0;
    t1 = 1;
    s2 = 1;
    t2 = 0;
 
 
    while (r!=0)
    {
        T temps = s2;
        s2 = s1;
        s1 = temps - s1*q;
 
        T tempt = t2;
        t2 = t1;
        t1 = tempt - t1*q;
        
        a = b;
        b = r;
        q = (a / b);
        r = a%b;
    }
    return pair<T, T>(s1, t1);
}
 
 
 
int main()
{
    int a = 69;
    int b = 23;
    pair<int, int> sol = ExtendedEuclid(a,b);
    cout << sol.first << "*" << a << "+" << b << "*" << sol.second << "=" << LoopEuclid(a, b) << endl;
    a = 67;
    b = 23;
    sol = ExtendedEuclid(a, b);
    cout << sol.first << "*" << a << "+" << b << "*" << sol.second << "=" << LoopEuclid(a, b) << endl;
}
cs


'Study > Algorithms' 카테고리의 다른 글

[Algorithm] 오일러 파이(피) 함수 Euler's phi function  (0) 2017.08.31
[Algorithm] 중국인의 나머지 정리 Chinese remainder theorem  (0) 2017.08.31
[Algorithm] Convex Hull Algorithm  (0) 2017.08.24
[Algorithm] CCW Algorithm [펌]  (0) 2017.08.24

https://en.wikipedia.org/wiki/Graham_scan


Convex Hull 알고리즘은 한국말로 볼록 껍질 알고리즘이라고도 하며


여러 점 가운데서 가장 큰 볼록 다각형을 찾는 알고리즘이다.


Graham scan(+CCW) method 를 쓴다.


https://www.acmicpc.net/problem/1708


위의 문제를 풀어보면 좋을 것 같다.

'Study > Algorithms' 카테고리의 다른 글

[Algorithm] 오일러 파이(피) 함수 Euler's phi function  (0) 2017.08.31
[Algorithm] 중국인의 나머지 정리 Chinese remainder theorem  (0) 2017.08.31
[Algorithm] 확장 유클리드 알고리즘 Extended Euclid Algorithm  (0) 2017.08.31
[Algorithm] CCW Algorithm [펌]  (0) 2017.08.24

퍼온곳: https://www.acmicpc.net/blog/view/27


Counter Clock Wise


세 점 P1(x1, y1), P2(x2, y2), P3(x3, y3)가 있을 떄, 점 3개를 이은 선분은 어떤 방향성을 나타내게 될까요? 11758번 문제: CCW

가능한 경우의 수는 총 3가지가 있습니다. 반시계 방향, 시계 방향, 일직선. 시계 방향을 -1, 일직선을 0, 반시계 방향을 1이라고 했을 때, P1은 검정색, P2는 초록색, P3을 파란색으로 나타내면 아래 그림과 같습니다.

세 점으로 이루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구할 수 있습니다. S를 점 P1, P2, P3로 이루어진 삼각형의 면적이라고 했을 때

2×S=|x1y11x2y21x3y31|=(x2−x1)(y3−y1)−(y2−y1)(x3−x1)

입니다.

여기서 S의 부호에 따라서, 다음과 같이 세 가지로 나눌 수 있습니다.

  • S > 0: 반시계 방향
  • S = 0: 일직선
  • S < 0: 시계 방향

코드로 나타내면 아래와 같습니다.

int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    int temp = x1*y2+x2*y3+x3*y1;
    temp = temp - y1*x2-y2*x3-y3*x1;
    if (temp > 0) {
        return 1;
    } else if (temp < 0) {
        return -1;
    } else {
        return 0;
    }
}



https://www.acmicpc.net/problem/11758



'Study > Algorithms' 카테고리의 다른 글

[Algorithm] 오일러 파이(피) 함수 Euler's phi function  (0) 2017.08.31
[Algorithm] 중국인의 나머지 정리 Chinese remainder theorem  (0) 2017.08.31
[Algorithm] 확장 유클리드 알고리즘 Extended Euclid Algorithm  (0) 2017.08.31
[Algorithm] Convex Hull Algorithm  (0) 2017.08.24

https://www.acmicpc.net/blog/view/27


위 자료를 참고하면 CCW 알고리즘에 대해 자세히 설명되어 있다.


간단히 설명하면 CCW 알고리즘은 점 3개의 방향이 시계방향인지 반시계방향인지 일직선인지를 판단하는 알고리즘이다.


그래서 CCW는 세 점으로 이루어진 삼각형의 면적을 통해서 판단한다.


넓이가 0보다 크면 반시계방향,

넓이가 0보다 작으면 시계방향,

넓이가 0이면 일직선


방법은 첫번째 점부터 (x1, y1)으로 두고 벡터의 외적을 통해 넓이를 구한다.


필자는 빨리 풀려고 직관적으로 풀었으나 point라는 자료형을 사용하면 좀더 깔끔해진다.





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
#include <iostream>
 
using namespace std;
 
int ccw(int x1, int y1, int x2, int y2, int x3, int y3){
    int temp = x1*y2 + x2*y3 + x3*y1;
    temp = temp - y1*x2 - y2*x3 - y3*x1;
    
    if(temp > 0){
        return 1;
    }else if(temp < 0){
        return -1;
    }else {
        return 0;
    }
}
 
int main(){
    int x1,x2,x3,y1,y2,y3;
    
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    
    cout << ccw(x1, y1, x2, y2, x3, y3) << endl;
    
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11650번] 좌표 정렬하기 - sort [C++]  (0) 2017.09.19
[4355번] 서로소 - 오일러 파이 함수[C++]  (0) 2017.08.31
[1463번] 1로 만들기 - 동적계획법 [C++]  (0) 2017.05.11
[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27

<Segment Tree>

https://www.acmicpc.net/blog/view/9


<Fenwick Tree>

http://www.crocus.co.kr/666

https://www.acmicpc.net/blog/view/21

개인적인 생각이지만 파이어베이스의 문서는 shit이다.

단계별로 설명도 좋고 설명 동영상도 있는 것도 좋지만

너무 추상적으로 설명하였고 중요한 부분에는 주석처리로 '잘 사용하면 된다.' 라고 적혀있으며

실질적인 예시가 없다. 어떤 경우는 설명 동영상에 예시를 하나하나 들어 설명해주지만

설명해주는 구글러 마음이라 어떤 구글러는 '데이터 쓰기는 이렇게 하면 된다. 하지만, 데이터 읽기는 알아서 해라.' 라는 식으로 설명해서 구글링을 하거나 하나하나 메소드를 찾아서 해야해서 처음 접근하는 입장에서는 쉽지않다.

그래서 처음에는 파이어베이스를 포기하고 Realm으로 갈아탈까라는 생각을 수도없이 했다.

하지만 결국 성공하였고 나처럼 어려움을 겪을 파이어베이스 뉴비들을 위해 글을 쓰게 되었다.(최대한 쉽게 쓰려고 노력하였다.)


파이어베이스 문서


참고로 파이어베이스를 쓰는 방법은 꼭 한가지가 아닌 경우가 많다.

이 이야기를 하는 이유는 블로그마다 다르게 썼다고 해서 헷갈리지 말았으면 하는 마음이다.

다음 예시는 Firebase Realtime Database 파이어베이스 실시간 데이터베이스를 예시로 하였다. (나머지 서비스도 비슷하게 따라하면 된다.)


1. 일단 구글 계정이 있어야 한다.



2. 안드로이드 스튜디오 프로젝트를 생성 또는 열기를 한다.



3. 위에 탭바에 Tools - Firebase를 누른다.







4. 그럼 다음과 같은 화면이 뜨는데 원하는 서비스를 클릭한다.







5. 예시로 실시간 데이터베이스를 클릭하였다. 그럼 다음과 같은 화면이 뜨는데 1번부터 순서대로 하면 된다.

  현재는 1, 2번에 있는 버튼을 클릭한 상태지만 처음이면 버튼이 활성화되어 있을것이다.

  순서대로 1번 버튼을 클릭하면 파이어베이스 프로젝트를 생성할 것인지를 물어보고 자동으로 연결을 시켜줄것이다.

  2번 버튼을 클릭하면 연동에 필요하면 gradle을 설치하도록 도와줄 것이다.








6. 다음으로 파이어 베이스 콘솔에 접속한다. 그럼 다음과 같은 프로젝트 목록이 있을것이다.









7. 테스트용으로 할 데이터베이스를 클릭한 다음 위쪽에 보면 '규칙'이 있는데 이것을 클릭하면 데이터를 읽고 쓰는 접근 권한에 대해서 정의할 수 있다. 테스트용으로 할꺼니 읽기 쓰기 둘다 true로 바꿨다.








8. 다음은 테스트용으로 데이터를 넣어보았다. JSON을 써보지 않았어도 불편함 없이 쉽게 할 수 있을 것이다. JSON자체가 표현하기 쉽게 되어있으므로. 몇번 시행착오를 해보면 할 수 있을것이다. 

tip) +버튼을 누르면 노드를 추가할 수 있다. value을 넣으면 자식노드를 추가할 수 없다.

또한 가장 최초 부모의 노드 이름은 변경할 필요 없다. 왜냐하면, 자바 코드에서 가져올 때, 이미 최초 부모 노드를 가져오므로 자식노드의 이름만 넣으면 된다.








9. 다음은 다음과 같이 코드를 작성한다. xml 파일에는 textView5 하나만 가지고 있다.

코드에 대한 자세한 설명은 생략하겠다. 넘나 귀찮.... 궁금하면 답변을 통해 해드리겠습니다.










<실행화면1>









<데이터를 변경 했을 때>


<실행화면2 - 앱을 켜놓은 상태에서 데이터를 변경하면 다음과 같이 앱에도 데이터가 변경된다>



이 문제는 동적계획법을 이용한 기본적인 문제로 처음 동적계획법을 접한다면 쉽지 않을 수 있다.

동적계획법이란 문제를 서브 문제로 나누어서 그것을 결합하여 결론에 도달하는 방법이다.

연산횟수를 줄이는 데 목표를 가지고 있다.

이 문제는 Bottom-up방법(동적계획법)을 이용하였다.

다른 방법도 무수히 존재하는 문제이다.

예외를 찾기가 힘든데 만약 어려움을 겪고 있다면

1793을 넣어보자.ㅎㅎ


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
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int output = 0;
int dp[1000001];
 
int main(){
    int N;
    cin >> N;
    
    dp[1] = 0;
    for(int i = 2; i <= N; i++){
        dp[i] = dp[i-1] + 1;
        if(i%2 == 0){
            dp[i] = min(dp[i/2]+1, dp[i-1]+1);
        }
        if(i%3 == 0){
            dp[i] = min(dp[i/3]+1, dp[i-1]+1);
        }
    }
           
    cout << dp[N];
    
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[4355번] 서로소 - 오일러 파이 함수[C++]  (0) 2017.08.31
[11758번] CCW - CCW 알고리즘[C++]  (0) 2017.08.24
[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27
[1181번] 단어 정렬 - Sorting[C++]  (0) 2017.03.27

+ Recent posts

티스토리툴바