반응형

1934번 문제 : 최소공배수


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
#include <iostream>
using namespace std;
 
int GetGCD(int a, int b)
{
    int c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
 
int main() {
    int inp;
    cin >> inp;
    
    while (inp > 0)
    {
        int x, y;
        cin >> x >> y;
 
        int gcd = GetGCD(x, y);
        int lcm = x * y / gcd;
        
        cout << lcm << endl;
 
        inp--;
    }
 
    return 0;
}
cs


13241번 문제 : 최소공배수
https://www.acmicpc.net/problem/13241

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
#include <iostream>
using namespace std;
 
int GetGCD(long long int a, long long int b)
{
    long long int c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
 
int main() {
    long long int x, y;
    cin >> x >> y;
 
    long long int gcd = GetGCD(x, y);
    long long int lcm = x * y / gcd;
 
    cout << lcm << endl;
 
    return 0;
}
cs

2609번 문제 : 최대공약수와 최소공배수

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 GetGCD(long long int a, long long int b)
{
    long long int c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
 
int main() {
    long long int x, y;
    cin >> x >> y;
 
    long long int gcd = GetGCD(x, y);
    long long int lcm = x * y / gcd;
 
    cout << gcd << endl;
    cout << lcm << endl;
 
    return 0;
}
cs

3036번 문제 : 링

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
#include <iostream>
#include <vector>
using namespace std;
 
int GetGCD(int a, int b)
{
    int c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
 
int main() {
    int num;
    vector<int> v;
    cin >> num;
 
    while (num > 0) 
    {
        int inp;
        cin >> inp;
        v.push_back(inp);
        num--;
    }
 
    for (int i = 1; i < v.size(); i++)
    {
        int gcd = GetGCD(v.at(0), v.at(i));
        cout << v.at(0) / gcd << "/" << v.at(i) / gcd << endl;
    }
 
    return 0;
}
cs



반응형
저작자표시

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

수학  (0) 2019.03.20
시뮬레이션  (0) 2019.03.20
이항 계수  (0) 2019.03.13
피보나치 수  (0) 2019.03.11
큐 사용하기  (0) 2019.02.26
반응형

11050번 문제 : 이항 계수 1

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


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>
using namespace std;
 
int main() {
    int x, y;
    cin >> x >> y;
    
    int temp1 = 1;
    for (int i = x; i > x - y; i--)
    {
        temp1 *= i;
    }
 
    int temp2 = 1;
    for (int i = 1; i <= y; i++)
    {
        temp2 *= i;
    }
 
    int result = temp1 / temp2;
 
    if (y != 0)
        cout << result << endl;
    else
        cout << "1" << endl;
 
    return 0;
}
cs


10872번 문제 : 팩토리얼
https://www.acmicpc.net/problem/10872

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
 
int main() {
    int inp, result = 1;
    cin >> inp;
 
    for (int i = 1; i <= inp; i++)
    {
        result *= i;
    }
    
    cout << result << endl;
 
    return 0;
}
cs


1676번 문제 : 팩토리얼 0의 개수

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


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
#include <iostream>
using namespace std;
 
int main() {
    int inp;
    int counter = 0;
    cin >> inp;
 
    int counterA = 0, counterB = 0;
    for (int i = 1; i <= inp; i++)
    {
        int temp = i;
        while (temp % 2 == 0)
        {
            counterA++;
            temp /= 2;
        }
        
        while (temp % 5 == 0)
        {
            counterB++;
            temp /= 5;
        }
    }
 
    cout << "a: " << counterA << "   b: " << counterB << endl;
    counterA >= counterB ? counter = counterB : counter = counterA;
 
    cout << counter << endl;
 
    return 0;
}
cs


메모:

- 팩토리얼 결과값을 구한 후에 나눠서 계산하는 방법은 효율적이지 못함 + 데이터형의 범위를 벗어나기 때문에 제대로된 답을 구할 수 없음.

- 2와 5가 한쌍 씩있으면 10의 배수이기 때문에 뒷자리가 0이다. 따라서 2와 5가 몇개의 쌍이 있는 지 확인만 하면 뒷자리의 0개수를 확인 할 수 있다. 




반응형
저작자표시

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

시뮬레이션  (0) 2019.03.20
최대공약수/최소공배수  (0) 2019.03.18
피보나치 수  (0) 2019.03.11
큐 사용하기  (0) 2019.02.26
스택 사용하기 (기초)  (0) 2019.02.14
반응형

2747번 문제 : 피보나치 수
https://www.acmicpc.net/problem/2747

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
#include <iostream>
using namespace std;
 
int Fibo(int n)
{
    if (n < 0)
        return 0;
    else if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return Fibo(n - 1) + Fibo(n - 2);
 
}
 
int Fibo2(int n)
{
    if (n < 0)
        return 0;
    else if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
    {
        int fib[1000] = { 0 };
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i < 1000; i++)
        {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib[n];
    }
}
 
int Fib[50] = { 0 };
int Fibo3(int n)
{
    if (n <= 2)
        return 1;
 
    if (Fib[n] != 0)
        return Fib[n];
    else 
    {
        Fib[n] = Fibo3(n - 1) + Fibo3(n - 2);
        return Fib[n];
    }
}
 
int main() {
    int inp;
    cin >> inp;
//    cout << Fibo(inp); //Time Out
//    cout << Fibo2(inp); 
    cout << Fibo3(inp);
 
    return 0;
}
 
cs


메모:

-3가지 방식으로 피보나치 수를 구할수 있다.

-첫번째 재귀방식으로 가장 직관적이나 효율성에 문제가 있음

-세번째 방법은 메모이제이션(Memoization) 방식




반응형
저작자표시

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

최대공약수/최소공배수  (0) 2019.03.18
이항 계수  (0) 2019.03.13
큐 사용하기  (0) 2019.02.26
스택 사용하기 (기초)  (0) 2019.02.14
소수 구하기  (0) 2019.02.13
반응형
10845번 문제 : 큐
https://www.acmicpc.net/problem/10845


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
#include <iostream>
#include <queue>
#include <string>
using namespace std;
 
int main() {
    int num;
    cin >> num;
    queue<int> q;
 
    while (num > 0)
    {
        string inp;
        cin >> inp;
        
        if (inp == "push")
        {
            int inp2;
                cin >> inp2;
                q.push(inp2);
        }
        else if (inp == "pop")
        {
            if (!q.empty()) {
                cout << q.front() << endl;
                q.pop();
            }
            else {
                cout << "-1" << endl;
            }
        }
        else if (inp == "size")
        {
            cout << q.size() << endl;
        }
        else if (inp == "empty")
        {
            if (!q.empty()) {
                cout << "0" << endl;
            }
            else {
                cout << "1" << endl;
            }
        }
        else if (inp == "front")
        {
            if (!q.empty()) {
                cout << q.front() << endl;
            }
            else {
                cout << "-1" << endl;
            }
        }
        else if (inp == "back")
        {
            if (!q.empty()) {
                cout << q.back() << endl;
            }
            else {
                cout << "-1" << endl;
            }
        }
        else
        {
            cout << "command error: " << inp << endl;
        }
 
        num--;
    }
 
    return 0;
}
cs


1260 문제 : DFS와 BFS

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


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>
using namespace std;
 
const int MAXSIZE = 1001;
int matrix[MAXSIZE][MAXSIZE];
bool visitedDFS[MAXSIZE];
bool visitedBFS[MAXSIZE];
int N, M, V;
vector<int> DFSresult;
vector<int> BFSresult;
 
void DFS(int v)
{
    if (visitedDFS[v] == true)
        return;
 
    visitedDFS[v] = true;
 
    DFSresult.push_back(v);
 
    for (int i = 1; i <= N; i++)
    {
        if (visitedDFS[i] == true || matrix[i][v] == 0)
            continue;
 
        DFS(i);
    }
}
 
void BFS(int v)
{
    queue<int> q;
    q.push(v);
    visitedBFS[v] = true;
 
    while (!q.empty())
    {
        v = q.front();
        BFSresult.push_back(v);
        q.pop();
        for (int i = 1; i <= N; i++)
        {
            if (visitedBFS[i] == true || matrix[i][v] == 0)
                continue;
            q.push(i);
            visitedBFS[i] = true;
        }
    }
}
 
 
int main() {
 
    cin >> N >> M >> V;
    
    for (int i = 0; i < M; i++)
    {
        int inpA, inpB;
        cin >> inpA >> inpB;
        matrix[inpA][inpB] = matrix[inpB][inpA] = 1;
    }
 
    DFS(V);
    BFS(V);
 
 
    for (auto i : DFSresult)
        cout << i << " ";
 
    cout << endl;
 
    for (auto j : BFSresult)
        cout << j << " ";
 
    return 0;
}
cs


메모:
-DFS(Depth Frist Search) 깊이 우선 탐색            BFS(Breadth First Search) 너비 우선 탐색


11866번 문제 : 조세퍼스 문제0

1158번 문제 : 조세퍼스 문제


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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int main()
{
    queue<int> q;
    vector<int> answer;
 
    int inputA, inputB;
    cin >> inputA >> inputB;
    
    for (int i = 1; i <= inputA; i++)
        q.push(i);
 
    int counter = 1;
    while (!q.empty())
    {
        int temp = q.front();
        
        if (counter == inputB)
        {
            answer.push_back(temp);
            q.pop();
            counter = 1;
        }
        else
        {
            q.pop();
            q.push(temp);
            counter++;
        }
    }
    
 
    cout << "<";
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer.at(i);
 
        if(i < answer.size() - 1)
            cout << ", ";
    }
    cout << ">";
    return 0;
}
cs


반응형
저작자표시

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

이항 계수  (0) 2019.03.13
피보나치 수  (0) 2019.03.11
스택 사용하기 (기초)  (0) 2019.02.14
소수 구하기  (0) 2019.02.13
정렬해보기  (0) 2019.02.10
반응형

네트워크 RPG게임 'Raid' 개발일지 7


오랜만에 개발일지를 올린다! 아예 손놓고 있었던건 아닌데 이것저것 하다보니까 이 프레젝트에 신경을 덜 쓰게 되었다...

지난번과 가장 크게 달라진 점은 맵 변경 및 스테이지 추가이다. 기존에는 보스와 대전이 바로 시작되는 방식이었지만 프로젝트 루와 비슷한 부분도 있고 네트워크 게임 치고 단조롭게 느껴져 기존 방식을 바꾸기로 했다.


1. 스테이지 형식의 맵

하나의 단순한 맵에서 스테이지 형식의 맵으로 바꾸었다. 서브구역을 다 통과하면 보스 구역으로 가는 방식으로 할 예정이다.


2. 서브 몬스터 추가

스테이지 형식이다보니까 각각의 구역에 서브 몬스터를 추가할 예정이다. 구역에 있는 모든 서브 몬스터를 다 처지하면 다음 구역으로 가는 방식으로 구성할 생각이다






반응형
저작자표시

'Game Development > 프로젝트: 레이드' 카테고리의 다른 글

네트워크 RPG게임 'Raid' 개발일지 8  (0) 2019.03.27
네트워크 RPG게임 'Raid' 개발일지 6  (0) 2019.01.09
네트워크 RPG게임 'Raid' 개발일지 5  (0) 2018.12.23
네트워크 RPG게임 'Raid' 개발일지 4  (0) 2018.12.08
네트워크 RPG게임 'Raid' 개발일지 3  (1) 2018.12.04
반응형

10828번 문제 : 스택

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


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
#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
int main() {
    int num;
    cin >> num;
    stack<int> s;
 
    while (num > 0)
    {
        string inp;
        cin >> inp;
 
        if (inp == "push")
        {
            int inp2;
            cin >> inp2;
            s.push(inp2);
        }
        else if (inp == "pop")
        {
            if (!s.empty()) {
                cout << s.top() << endl;
                s.pop();
            }
            else{
                cout << "-1" << endl;
            }
        }
        else if (inp == "size")
        {
            cout << s.size() << endl;
        }
        else if (inp == "empty")
        {
            if (!s.empty()) {
                cout << "0" << endl;
            }
            else{
                cout << "1" << endl;
            }
        }
        else if (inp == "top")
        {
            if (!s.empty()) {
                cout << s.top() << endl;
            }
            else{
                cout << "-1" << endl;
            }
        }
        else
        {
            cout <<"command error: "<< inp << endl;
        }
 
        num--;
    }
 
    return 0;
}
cs

메모
-c++에서는 string을 switch문에 활용할 수 없음 int만 가능 (c#은 가능)

1874번 문제 : 스택 수열
https://www.acmicpc.net/problem/1874

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
#include <iostream>
#include <stack>
#include <vector>
#include <string>
using namespace std;
 
int main()
{
    int num;
    cin >> num;
    vector<int> v;
    vector<string> result;
 
    while (num > 0)
    {
        int inp;
        cin >> inp;
        v.push_back(inp);
        num--;
    }
 
    stack<int> s;
    int value = 1;
    int index = 0;
    int popCounter = 0;
    while (true)
    {
        if (s.empty())
        {
            if (popCounter != v.size())
            {
                s.push(value);
                result.push_back("+");
                value++;
            }
            else
                break;
        }
        else
        {
            if (s.top() == v.at(index))
            {
                s.pop();
                popCounter++;
                result.push_back("-");
 
                if (v.size() > index)
                    index++;
                else
                {
                    result.clear();
                    result.push_back("NO");
                    break;
                }
            }
            else
            {
                if (value > v.size())
                {
                    result.clear();
                    result.push_back("NO");
                    break;
                }
 
                s.push(value);
                result.push_back("+");
                value++;
            }
        }
    }
 
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << "\n";
 
    return 0;
}
 
cs

메모:
-for(auto i: result) 사용하면 시간초과 발생

9012번 문제 : 괄호
https://www.acmicpc.net/problem/9012

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
#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;
 
string CheckVPS(string& str)
{
    stack<int> s;
    for (int i = 0; i < str.size(); i++)
    {
        if (s.empty())
        {
            if (str[i] == ')')
                return "NO";
            else if (str[i] == '(')
                s.push(1);
        }
        else
        {
            if (str[i] == ')')
                s.pop();
            else if (str[i] == '(')
                s.push(1);
        }
    }
 
    if (s.empty())
        return "YES";
    else
        return "NO";
}
 
int main() {
    
    int num;
    cin >> num;
    vector<string> result;
    
    while (num > 0)
    {
        string inp;
        cin >> inp;
 
        result.push_back(CheckVPS(inp));
        
        num--;
    }
 
    for (auto i : result)
        cout << i << endl;
 
    return 0;
}
cs


반응형
저작자표시

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

피보나치 수  (0) 2019.03.11
큐 사용하기  (0) 2019.02.26
소수 구하기  (0) 2019.02.13
정렬해보기  (0) 2019.02.10
규칙 찾기  (0) 2019.02.05
반응형

1987번 문제 : 소수 찾기

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


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
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int num;
    cin >> num;
    int counter = 0;
    vector<int> v;
 
    while (num > 0)
    {
        int inp;
        cin >> inp;
        v.push_back(inp);
        num--;
    }
 
    for (auto i:v)
    {
        if (i != 1)
        {
            int j = i - 1;
            while (true)
            {
                if (i % j != 0) {
                    j--;
                }
                else {
                    if (j == 1)
                        counter++;
                    break;
                }
            }
        }
    }
 
    cout << counter;
 
    return 0;
}
cs


2581번 문제 : 소수
https://www.acmicpc.net/problem/2581

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;
 
void FindPrimeNumber(int n, vector<int>& v)
{
    if (n != 1)
    {
        int j = n - 1;
        while (true)
        {
            if (n % j != 0) {
                j--;
            }
            else {
                if (j == 1)
                    v.push_back(n);
                break;
            }
        }
    }
}
 
int main() {
    int a, b;
    cin >> a >> b;
    vector<int> v;
 
    for (int i = a; i <= b; i++)
    {
        FindPrimeNumber(i, v);
    }
 
    if (!v.empty()) 
    {
        int sum = 0;
        int min = v.front();
        for (auto i : v)
        {
            sum += i;
            if (i < min)
                min = i;
        }
    
        cout << sum << endl << min;
    }
    else
        cout << "-1";
 
    return 0;
}
cs


1929번 문제 : 소수 구하기
https://www.acmicpc.net/problem/1929


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
#include <iostream>
#include <vector>
using namespace std;
 
void CheckPrimeNumber(int n, int s, vector<int>& v)
{
    //Count Prime Number using SieveOfEratosthenes
    bool *prime = new bool[n + 1];
    for (int i = 0; i < n + 1; i++)
    {
        prime[i] = true;
    }
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p*p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    for (int p = s; p <= n; p++)
    {
        if (prime[p] == true)
            v.push_back(p);
    }
 
    delete[] prime;
}
 
int main() {
 
    int start, end;
    cin >> start >> end;
    vector<int> v;
 
    CheckPrimeNumber(end, start, v);
 
    for (auto i : v)
        cout << i << "\n";
 
    return 0;
}
cs


메모:
-에라토스테네스의 체 활용, 시간 복잡도: O(n*log(log(n)))
참고사이트: https://www.geeksforgeeks.org/sieve-of-eratosthenes/



4948번 문제 : 베르트랑 공준


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>
#include <vector>
using namespace std;
 
void CheckPrimeNumber(int n, int s, vector<int>& v)
{
    //Count Prime Number using SieveOfEratosthenes
    bool *prime = new bool[n + 1];
    for (int i = 0; i < n + 1; i++)
    {
        prime[i] = true;
    }
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p*p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    for (int p = s; p <= n; p++)
    {
        if (prime[p] == true)
            v.push_back(p);
    }
 
    delete[] prime;
}
 
int main() {
 
    vector<int> answer;
 
    while (true)
    {
        vector<int> v;
        int input;
        cin >> input;
        
        if (input != 0)
        {
            if (input != 1)
            {
                CheckPrimeNumber(input * 2 - 1, input + 1, v);
                answer.push_back(v.size());
            }
            else
            {
                answer.push_back(1);
            }
            
        }
        else
            break;
    }
 
    for (auto i : answer)
        cout << i << endl;
 
    return 0;
}
cs




9020번 문제 : 골드바흐의 추측


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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
void CheckPrimeNumber(int n, vector<int>& v)
{
    //Count Prime Number using SieveOfEratosthenes
    bool *prime = new bool[n + 1];
    for (int i = 0; i < n + 1; i++)
    {
        prime[i] = true;
    }
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p*p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    for (int p = 2; p <= n; p++)
    {
        if (prime[p] == true)
            v.push_back(p);
    }
 
    delete[] prime;
}
 
int main() {
 
    vector<int> answer;
    int num;
    cin >> num;
 
    for (int i = 0; i < num; i++)
    {
        vector<int> v;
        int input;
        cin >> input;
        CheckPrimeNumber(input, v);
        int temp = input / 2;
 
        while (temp > 1)
        {
            if (find(v.begin(), v.end(), temp) != v.end())
            {
                if (find(v.begin(), v.end(), input - temp) != v.end())
                {
                    answer.push_back(temp);
                    answer.push_back(input - temp);
                    break;
                }
            }
 
            temp--;
        }
    }
 
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer.at(i) << " ";
        if (i % 2 == 1)
            cout << endl;
    }
 
 
    return 0;
}
cs





반응형
저작자표시

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

큐 사용하기  (0) 2019.02.26
스택 사용하기 (기초)  (0) 2019.02.14
정렬해보기  (0) 2019.02.10
규칙 찾기  (0) 2019.02.05
문자열 사용하기 3  (0) 2019.02.05
반응형

2750번 문제 : 수 정렬하기

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


2751번 문제 : 수 정렬하기 2

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


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>
#include <vector>
using namespace std;
 
int main() {
 
    int num;
    cin >> num;
    vector<int> v;
 
    while (num > 0)
    {
        int inp;
        cin >> inp;
        v.push_back(inp);
        num--;
    }
 
    sort(v.begin(), v.end());
    
    for (auto i : v)
    {
        cout << i << "\n";
    }
 
    return 0;
}
cs


2108번 문제 : 통계학
https://www.acmicpc.net/problem/2108

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
 
vector<int> v;
int arr[8001] = {0};
 
int GetMean();
int GetMedian();
int GetMode();
int GetRange();
 
int main()
{
    int inp;
    cin >> inp;
 
    while (inp > 0)
    {
        int num;
        cin >> num;
        v.push_back(num);
        inp--;
    }
 
    cout << GetMean() << endl;
    cout << GetMedian() << endl;
    cout << GetMode() << endl;
    cout << GetRange() << endl;
 
    return 0;
}
 
int GetMean()
{
    int sum = 0;
    for (auto i : v)
        sum += i;
    
    double result = (double)sum / (double)v.size();
 
    return round(result);
}
 
int GetMedian()
{
    sort(v.begin(), v.end());
    int medianIndex = v.size() / 2; //v size is always odd number according to the question
 
    return v.at(medianIndex);
}
 
int GetMode()
{
    for (auto i : v)
    {
        if (i >= 0)
            arr[i]++;
        else
            arr[abs(i) + 4000]++;
    }
 
    int max = 0;
    int maxIndex = 0;
    bool isTheOnlyMax = false;
    for (int i = 0; i < sizeof(arr)/sizeof(*arr); i++) // sizeof(arr)/sizeof(*arr) = 8001
    {
        if (arr[i] == max)
            isTheOnlyMax = false;
 
        if (arr[i] > max)
        {
            max = arr[i];
            maxIndex = i;
            isTheOnlyMax = true;
        }
    }
 
    if (isTheOnlyMax)
    {
        int originalIndex;
        if (maxIndex > 4000)
            originalIndex = (maxIndex - 4000) * (-1);
        else
            originalIndex = maxIndex;
 
        return originalIndex;
    }
    else
    {
        vector<int> tempV;
        for (int i = 0; i < sizeof(arr) / sizeof(*arr); i++) // sizeof(arr)/sizeof(*arr) = 8001
        {
            if (arr[i] == max)
            {
                if(i < 4000)
                    tempV.push_back(i);
                else
                {
                    int value = (i - 4000) * (-1);
                    tempV.push_back(value);
                }
            }
        }
 
        sort(tempV.begin(), tempV.end());
 
        if (tempV.size() > 1) //TODO is this needed?
            return tempV[1];
        else
            return tempV[0];
    }
 
}
 
int GetRange()
{
    sort(v.begin(), v.end());
 
    return v.back() - v.front();
}
cs

1427번 문제 : 소트인사이드
https://www.acmicpc.net/problem/1427

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>
#include <vector>
#include <functional>
using namespace std;
 
int main() {
 
    int num;
    cin >> num;
    vector<int> v;
 
    while (num > 0)
    {
        int leftover = num % 10;
        v.push_back(leftover);
        num /= 10;
    }
 
    sort(v.begin(), v.end(), greater<int>());
 
    for (auto i : v)
    {
        cout << i;
    }
 
    return 0;
}
cs

메모: 

-greater<int>() 내림차순으로 정렬,   #include <functional> 헤더파일 필요



1181번 문제 : 단어정렬
https://www.acmicpc.net/problem/1181

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
 
bool Compare(const string& a, const string&b)
{
    //CompareStringAlphabetically
    if (a.size() == b.size()) {
 
        int i = 0;
        while (a[i] == b[i]) {
            i++;
            if (i >= a.size())
                break;
        }
        return(a[i] < b[i]);
    }
    //CompareStringByLength
    else
        return(a.size() < b.size());
}
 
int main() {
 
    int num;
    cin >> num;
    vector<string> v;
 
    while (num > 0)
    {
        string inp;
        cin >> inp;
        v.push_back(inp);        
        num--;
    }
 
    sort(v.begin(), v.end(), Compare); //vector sorting
    v.erase(unique(v.begin(), v.end()), v.end()); //erase duplication
 
    for (auto i : v)
    {
        cout << i << "\n";
    }
 
    return 0;
}
cs


메모: 

-vector의 중복제거 함수는 unique사용

-unigue후에 뒷부분을 erase처리해야함





반응형
저작자표시

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

스택 사용하기 (기초)  (0) 2019.02.14
소수 구하기  (0) 2019.02.13
규칙 찾기  (0) 2019.02.05
문자열 사용하기 3  (0) 2019.02.05
문자열 사용하기 2  (0) 2019.02.03

+ Recent posts

티스토리툴바