반응형

6679번 문제 : 싱기한 네자리 숫자

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


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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
 
using namespace std;
 
bool Check(int num)
{
    int a = 0, b = 0, c = 0;
    int a_sum = 0, b_sum = 0, c_sum = 0;
    a = num;
    b = num;
    c = num;
    
    while (a > 0)
    {
        a_sum += a % 10;
        a /= 10;
    }
 
    while (b > 0)
    {
        b_sum += b % 12;
        b /= 12;
    }
 
    while (c > 0)
    {
        c_sum += c % 16;
        c /= 16;
    }
 
    if (a_sum == b_sum && a_sum == c_sum && a_sum == b_sum)
        return true;
    else
        return false;
}
 
int main()
{
    for (int i = 1000; i < 10000; i++)
    {
        if (Check(i))
            cout << i << endl;
    }
 
    return 0;
}
cs



1051번 문제 : 숫자 정사각형

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


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
#include <iostream>
#include <string>
 
using namespace std;
 
int max_x, max_y;
int matrix[100][100] = { 0, };
int index = 0;
 
bool CheckSquare(int x, int y)
{
    if (x >= 0 && x < max_x - index && y >= 0 && y < max_y - index)
    {
        if (matrix[x][y] == matrix[x][y + index] && matrix[x][y] == matrix[x + index][y] && matrix[x][y] == matrix[x + index][y + index])
        {
            return true;
        }
    }
 
    return false;
}
 
 
int main()
{
    cin >> max_x >> max_y;
 
    for (int i = 0; i < max_x; i++)
    {
        string input;
        cin >> input;
        for (int j = 0; j < max_y; j++)
        {
            matrix[i][j] = input[j] - '0';
        }
    }
 
    int index_max = min(max_x, max_y);
    int max_squareSize = 0;
 
    while (index < index_max)
    {
        for (int i = 0; i < max_x; i++)
        {
            for (int j = 0; j < max_y; j++)
            {
                if (CheckSquare(i, j))
                {
                    max_squareSize = (index + 1) * (index + 1);
                    break;
                }
            }
        }
 
        index++;
    }
 
    cout << max_squareSize << endl;
 
    return 0;
}
cs


메모:

-index =0부터 시작해야함 그러지 않으면

1 1

1

예외 발생 정답:1 (오답: 0)

반응형
저작자표시 (새창열림)

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

우선순위 큐  (0) 2019.08.27
트리 사용하기  (0) 2019.04.29
그리디 알고리즘  (0) 2019.04.28
동적 계획법 기초  (0) 2019.04.08
그래프(DFS, BFS)  (0) 2019.04.04
반응형
11279번 문제 : 최대 힙
https://www.acmicpc.net/problem/11279


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 <vector>
#include <string>
 
using namespace std;
 
int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    vector<int> v;
 
    int num;
    cin >> num;
 
    while (num > 0)
    {
        int input;
        cin >> input;
        if (input == 0)
        {
            if (v.empty())
            {
                cout << "0" << "\n";
            }
            else
            {
                int max = v.front();
                int index = 0;
                for (int i = 0; i < v.size(); i++)
                {
                    if (v[i] > max)
                    {
                        max = v[i];
                        index = i;
                    }
                }
 
                cout << max << "\n";
                v.erase(v.begin() + index);
            }
        }
        else
        {
            v.push_back(input);
        }
    
        num--;
    }
 
 
    return 0;
}
cs

메모
-처음엔 시간초과 발생
-endl 그리고
ios::sync_with_stdio(0);
    cin.tie(0);

추가하면 시간초과 해결됨




1927번 문제 : 최소 힙

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


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 <vector>
#include <string>
 
using namespace std;
 
int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    vector<int> v;
 
    int num;
    cin >> num;
 
    while (num > 0)
    {
        int input;
        cin >> input;
        if (input == 0)
        {
            if (v.empty())
            {
                cout << "0" << "\n";
            }
            else
            {
                int min = v.front();
                int index = 0;
                for (int i = 0; i < v.size(); i++)
                {
                    if (v[i] < min)
                    {
                        min = v[i];
                        index = i;
                    }
                }
 
                cout << min << "\n";
                v.erase(v.begin() + index);
            }
        }
        else
        {
            v.push_back(input);
        }
    
        num--;
    }
 
 
    return 0;
}
cs


반응형
저작자표시 (새창열림)

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

추가 문제 풀이  (0) 2019.09.28
트리 사용하기  (0) 2019.04.29
그리디 알고리즘  (0) 2019.04.28
동적 계획법 기초  (0) 2019.04.08
그래프(DFS, BFS)  (0) 2019.04.04
반응형

트리 순회 개념 

출처 - 위키백과 :https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

-전위 순회

전위 순회(preorder)는 다음과 같은 방법으로 진행한다.

  1. 노드를 방문한다.
  2. 왼쪽 서브 트리를 전위 순회한다.
  3. 오른쪽 서브 트리를 전위 순회한다.

전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.

-중위 순회

중위 순회(Inorder)은 다음의 순서로 진행된다.

  1. 왼쪽 서브 트리를 중위 순회한다.
  2. 노드를 방문한다.
  3. 오른쪽 서브 트리를 중위 순회한다.

중위 순회는 대칭 순회(symmetric)라고도 한다.

-후위 순회

후위 순회(postorder)는 다음과 같은 방법으로 진행한다.

  1. 왼쪽 서브 트리를 후위 순회한다.
  2. 오른쪽 서브 트리를 후위 순회한다.
  3. 노드를 방문한다.

-레벨 순서 순회

레벨 순서 순회(level-order)는 모든 노드를 낮은 레벨부터 차례대로 순회한다. 레벨 순서 순회는 너비 우선 순회(breadth-first traversal)라고도 한다.

  • 전위 순회: F, B, A, D, C, E, G, I, H (root, left, right)
  • 중위 순회: A, B, C, D, E, F, G, H, I (left, root, right)
  • 후위 순회: A, C, E, D, B, H, I, G, F (left, right, root)
  • 레벨 순서 순회: F, B, G, A, D, I, C, E, H

1991번 문제 : 트리 순회

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


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
#include <iostream>
#include <string>
using namespace std;
 
string resultA, resultB, resultC;
 
class TreeNode
{
public:
    char value;
    TreeNode *right = NULL;
    TreeNode *left = NULL;
 
    TreeNode()
    {
        value = ' ';
        right = NULL;
        left = NULL;
    }
 
    void SetNode(char v, TreeNode *l, TreeNode *r)
    {
        value = v;
        right = r;
        left = l;
    }
 
 
    void PreorderTraversal(TreeNode *n)
    {
        if (n != NULL)
        {
            resultA += n->value;
            PreorderTraversal(n->left);
            PreorderTraversal(n->right);
        }
 
    }
 
    void InorderTraversal(TreeNode *n)
    {
        if (n != NULL)
        {
            InorderTraversal(n->left);
            resultB += n->value;
            InorderTraversal(n->right);
        }
    }
 
    void PostorderTraversal(TreeNode *n)
    {
        if (n != NULL)
        {
            PostorderTraversal(n->left);
            PostorderTraversal(n->right);
            resultC += n->value;
        }
    }
};
 
TreeNode* node = new TreeNode[27];
 
int main()
{
    int num;
    cin >> num;
 
    while (num > 0)
    {
        char v, l, r;
        cin >> v >> l >> r;
 
        if(l != '.' && r!= '.')
            node[(int)(v - 'A')].SetNode(v, &node[(int)(l - 'A')], &node[(int)(r - 'A')]);
 
        if (l != '.' && r == '.')
            node[(int)(v - 'A')].SetNode(v, &node[(int)(l - 'A')], NULL);
 
        if (l == '.' && r != '.')
            node[(int)(v - 'A')].SetNode(v, NULL, &node[(int)(r - 'A')]);
 
        if (l == '.' && r == '.')
            node[(int)(v - 'A')].SetNode(v, NULL, NULL);
 
        num--;
    }
 
    TreeNode *startNode = &node[0];
    startNode->PreorderTraversal(startNode);
    cout << resultA << endl;
    startNode->InorderTraversal(startNode);
    cout << resultB << endl;
    startNode->PostorderTraversal(startNode);
    cout << resultC << endl;
 
    delete[] node;
 
    return 0;
}
cs


반응형
저작자표시 (새창열림)

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

추가 문제 풀이  (0) 2019.09.28
우선순위 큐  (0) 2019.08.27
그리디 알고리즘  (0) 2019.04.28
동적 계획법 기초  (0) 2019.04.08
그래프(DFS, BFS)  (0) 2019.04.04
반응형
11399번 문제 : ATM
https://www.acmicpc.net/problem/11399

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v;
 
int main() 
{
    int num;
    cin >> num;
    
    for (int i = 1; i <= num; i++)
    {
        int inp;
        cin >> inp;
        v.push_back(inp);
    }
 
    sort(v.begin(), v.end());
 
    for (int i = 1; i < v.size(); i++)
    {
        v.at(i) += v.at(i - 1);    
    }
 
    int sum = 0;
    for (auto i : v)
        sum += i;
 
    cout << sum << endl;
 
 
    return 0;
}
cs



11047번 문제 : 동전0
https://www.acmicpc.net/problem/11047

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v;
 
int main() 
{
    int num, sum;
    cin >> num >> sum;
 
    for (int i = 0; i < num; i++)
    {
        int inp;
        cin >> inp;
 
        v.push_back(inp);
    }
    
    int counter = 0;
    
    for (int i = v.size() - 1; i >= 0; i--)
    {
        while (true)
        {
            int temp = sum - v.at(i);
            if (temp >= 0)
            {
                sum -= v.at(i);
                counter++;
            }
            else
                break;
        }
        if (sum == 0)
            break;
    }
 
 
    cout << counter << endl;
 
    return 0;
}
cs



2217번 문제 : 로프

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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v;
 
int main()
{
    int num;
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        int input;
        cin >> input;
        v.push_back(input);
    }
 
    sort(v.begin(), v.end(), greater<int>());
 
    int maxWeight = 0;
    if (v.size() >= 2)
    {
        for (int i = 0; i < v.size() - 1; i++)
        {
            int weight = 0;
            if (v.at(i) > v.at(i + 1) * (2 + i))
            {
                weight = v.at(i);
            }
            else
            {
                weight = v.at(i + 1) * (2 + i);
            }
 
            if (weight > maxWeight)
                maxWeight = weight;
        }
    }
    else
    {
        maxWeight = v.at(0);
    }
 
    cout << maxWeight << endl;
 
    return 0;
}
cs



4307번 문제 : 개미
https://www.acmicpc.net/problem/4307

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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> result;
 
int main()
{
    int cases;
    cin >> cases;
 
    for (int i = 0; i < cases; i++)
    {
        int length, numOfAnts;
        cin >> length >> numOfAnts;
 
        vector<int> v;
 
        for (int j = 0; j < numOfAnts; j++)
        {
            int startPosition;
            cin >> startPosition;
 
            if (startPosition <= length / 2)
            {
                v.push_back(startPosition);
            }
            else
            {
                v.push_back(length - startPosition);
            
            }
        }
        
        sort(v.begin(), v.end(), greater<int>());
        
        result.push_back(v.at(0));
        result.push_back(length - v.at(v.size() - 1));
    }
 
    for (int i = 0; i < result.size(); i++)
    {
        cout << result.at(i) << " ";
        if (i % 2 == 1)
            cout << endl;
    }
    
    
    return 0;
}
cs


메모:

- 가장 늦은 시간을 구할때 개미가 충돌할 때 방향을 바꾸는 것이 그냥 지나치는 것과 결국 같다 -> 이 부분이 핵심




반응형
저작자표시 (새창열림)

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

우선순위 큐  (0) 2019.08.27
트리 사용하기  (0) 2019.04.29
동적 계획법 기초  (0) 2019.04.08
그래프(DFS, BFS)  (0) 2019.04.04
브루트 포스  (0) 2019.04.01
반응형


1932번 문제 : 피보나치 함수


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
#include <iostream>
using namespace std;
 
struct MyFibo
{
    int value;
    int zeroCount;
    int oneCount;
};
 
MyFibo fib[50];
int GetFibo(int n)
{
    if (n == 0)
    {
        fib[0].value = 0;
        fib[0].zeroCount = 1;
        return 0;
    }
 
    else if (n == 1)
    {
        fib[1].value = 1;
        fib[1].oneCount = 1;
        return 1;
    }
    
    if (fib[n].value != 0)
    {
        return fib[n].value;
    }
    else
    {
        fib[n].value = GetFibo(n - 1) + GetFibo(n - 2);
        fib[n].zeroCount = fib[n - 1].zeroCount + fib[n - 2].zeroCount;
        fib[n].oneCount = fib[n - 1].oneCount + fib[n - 2].oneCount;
    }
}
 
int main() {
    int inp;
    cin >> inp;
 
    while (inp > 0)
    {
        int a;
        cin >> a;
        zeroCounter = 0;
        oneCounter = 0;
        GetFibo(a);
        cout << fib[a].zeroCount << " " << fib[a].oneCount << endl;
 
        inp--;
    }
 
    return 0;
}
cs



1149번 문제 : RGB거리

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


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
#include <iostream>
#include <algorithm>  
using namespace std;
 
int DP[1001][4] = { 0 };
 
int main() {
    int inp;
    cin >> inp;
 
    for (int i = 1; i <= inp; i++)
    {
        int r, g, b;
        cin >> r >> g >> b;
 
        DP[i][1] = r;
        DP[i][2] = g;
        DP[i][3] = b;
    }
 
    for (int i = 2; i <= inp; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            if (j == 1)
                DP[i][j] += min(DP[i - 1][2], DP[i - 1][3]);
            else if (j == 2)
                DP[i][j] += min(DP[i - 1][1], DP[i - 1][3]);
            else if (j == 3)
                DP[i][j] += min(DP[i - 1][1], DP[i - 1][2]);
        }
    }
 
    int min = DP[inp][1];
    for (int j = 1; j <= 3; j++)
    {
        if (DP[inp][j] < min)
            min = DP[inp][j];
    }
 
    cout << min << endl;
 
 
    return 0;
}
cs


1932번 문제 : 정수 삼각형

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


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
#include <iostream>
#include <algorithm>
using namespace std;
 
int DP[501][501] = { 0 };
 
int main()
{
    int size;
    cin >> size;
    for (int i = 1; i <= size; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            int inp;
            cin >> inp;
            DP[i][j] = inp;
        }
    }
 
    for (int i = 2; i <= size; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (j == 1)
            {
                DP[i][j] += DP[i - 1][j];
            }
            else if (j == i)
            {
                DP[i][j] += DP[i - 1][j - 1];
            }
            else
            {
                DP[i][j] += max(DP[i - 1][j - 1], DP[i - 1][j]);
            }
        }
    }
 
    int max = 0;
    for (int j = 1; j <= size; j++)
    {
        if (DP[size][j] > max)
            max = DP[size][j];
    }
 
    cout << max << endl;
 
    return 0;
}
 
cs

메모:
-위쪽부터 누적 최대값을 취하는 방식으로 풀어야함
-양쪽끝 (위 코드에서는 j =1 또는 j =i)일때는 받을 수 있는 값은 하나 밖에 없음
-가운데에 있는 숫자들은 양쪽에서 값을 받을 수 있음



1463번 문제 : 1로 만들기
https://www.acmicpc.net/problem/1463

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int arr[1000001] = { 0 };
 
int GetValue(int num)
{
    if (num == 0 || num == 1)
    {
        arr[num] = 0;
        return 0;
    }
    else if (num == 2 || num == 3)
    {
        arr[num] = 1;
        return 1;
    }
 
    if (arr[num] != 0)
        return arr[num];
    else
    {
        arr[num] = arr[num - 1] + 1;
 
        if (num % 2 == 0)
        {
            arr[num] = min(arr[num], arr[num / 2] + 1);
        }
 
        if (num % 3 == 0)
        {
            arr[num] = min(arr[num], arr[num / 3] + 1);
        }
        
 
        return arr[num];
    }
}
 
int main()
{
    int inp;
    cin >> inp;
 
    for (int i = 1; i <= inp; i++)
    {
        GetValue(i);
    }
 
    cout << arr[inp] << endl;
 
    return 0;
}
cs

메모:
-3부터 나뉘어지면 무조건 취소값이라고 생각하면 안됨
-그래서 그 전의 수와 비교하면서 루프를 돌아야함


9461번 문제 : 파도반 수열


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
#include <iostream>
#include <vector>
using namespace std;
 
signed long long value[101] = { 0,1,1,1,2,2,3,4,5,7 };
vector<signed long long> result;
 
int GetValue(int num)
{
    if (num <= 8)
        return value[num];
    else
    {
        if (value[num] != 0)
            return value[num];
        else
        {
            value[num] = value[num - 1] + value[num - 5];
            return value[num];
        }
    }
}
 
 
int main() {
    
    int t;
    cin >> t;
 
    for (int i = 0; i <= 100; i++)
    {
        GetValue(i);
    }
 
    while (t > 0)
    {
        int inp;
        cin >> inp;
 
        result.push_back(value[inp]);
 
        t--;
    }
 
    for (auto i : result)
        cout << i << endl;
 
 
    return 0;
}
cs




메모:
-i가 80정도 이상이면 long long 범위를 벗어나 답을 못구함...



반응형
저작자표시 (새창열림)

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

트리 사용하기  (0) 2019.04.29
그리디 알고리즘  (0) 2019.04.28
그래프(DFS, BFS)  (0) 2019.04.04
브루트 포스  (0) 2019.04.01
수학  (0) 2019.03.20
반응형

DFS(Deep First Search) 깊이 우선 탐색    BFS(Breadth First Search) 너비 우선 탐색                인접행렬


      





2606번 문제 : 바이러스


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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int const MAX_VALUE = 101;
int matrix[MAX_VALUE][MAX_VALUE] = { 0 };
bool visit[MAX_VALUE] = { false };
int counter = 0;
 
void DFS(int v, int N) {
    if(visit[v] != true)
        counter++;
 
    visit[v] = true;
    
    for (int i = 1; i <= N; i++)
    {
        if (matrix[i][v] == 0 || visit[i] == true)
            continue;
 
        DFS(i, N);
    }
}
 
int main()
{
    int N, M;
    cin >> N >> M;
 
    for (int i = 1; i <= M; i++)
    {
        int x, y;
        cin >> x >> y;
        matrix[x][y] = matrix[y][x] = 1;
    }
 
    DFS(1, N);
 
    cout << counter - 1 << endl;
 
    return 0;
}
 
cs

메모:
-중복체크를 하면서 count해야함


2309번 문제 : 순열 사이클

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


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>
#include <queue>
#include <vector>
using namespace std;
 
int const MAX_VALUE = 1001;
int matrix[MAX_VALUE][MAX_VALUE] = { 0 };
int visit[MAX_VALUE] = { 0 };
int index = 0;
vector<int> result;
 
void DFS(int v, int N, int index) {
    visit[v] = index;
    for (int i = 1; i <= N; i++)
    {
        if (matrix[i][v] != index || visit[i] == index)
            continue;
 
        DFS(i, N, index);
    }
}
 
int main()
{
    int num;
    cin >> num;
 
    while (num > 0)
    {
        int M; 
        cin >> M;
        int counter = 0;
        index++;
 
        for (int i = 1; i <= M; i++)
        {
            int x = i;
            int y;
            cin >> y;
            matrix[x][y] = matrix[y][x] = index;
        }
 
        for (int i = 1; i <= M; i++)
        {
            if (visit[i] != index)
            {
                DFS(i, M, index);
                counter++;
            }
        }
        result.push_back(counter);
        num--;
    }
 
    for (auto i : result)
        cout << i << endl;
 
    return 0;
}
cs



메모:
-matrix를 사용 후에 초기화 하는 방식으로 하면 시간 초과 발생 -> index를 활용하여 기존의 matrix를 재활용

-아래 코드는 코드를 이해하는데 더 직관적이나 initializing하는 과정(시간복잡도: O (n 2)) 때문에 시간초과 발생
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 <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int const MAX_VALUE = 1001;
int matrix[MAX_VALUE][MAX_VALUE] = { 0 };
bool visit[MAX_VALUE] = { 0 };
vector<int> result;
int counter = 0;
 
void DFS(int v, int N) {
    //    cout << v << " "; //for debug
    visit[v] = true;
    for (int i = 1; i <= N; i++)
    {
        if (matrix[i][v] == 0 || visit[i] == true)
            continue;
 
        DFS(i, N);
    }
}
 
void InitializeMatrix()
{
    for (int i = 0; i < MAX_VALUE; i++)
    {
        for (int j = 0; j < MAX_VALUE; j++)
        {
            matrix[i][j] = 0;
        }
    }
 
    for (int i = 0; i < MAX_VALUE; i++)
    {
        visit[i] = false;
    }
 
    counter = 0;
}
 
int main() //시간초과 발생하는 코드
{
    int num;
    cin >> num;
 
    while (num > 0)
    {
        int M;
        cin >> M;
 
        InitializeMatrix();
 
        for (int i = 1; i <= M; i++)
        {
            int x = i;
            int y;
            cin >> y;
            matrix[x][y] = matrix[y][x] = 1;
        }
 
        /*
        //Matrix Debug
        cout << endl;
        for (int i = 1; i <= M; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                cout << matrix[i][j] << "  ";
            }
            cout << endl;
        }
        cout << endl;
        */
 
        for (int i = 1; i <= M; i++)
        {
            if (visit[i] != true)
            {
                DFS(i, M);
                counter++;
            }
        }
 
        result.push_back(counter);
        num--;
    }
 
    for (auto i : result)
        cout << i << endl;
 
    return 0;
}
 
cs


반응형
저작자표시 (새창열림)

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

그리디 알고리즘  (0) 2019.04.28
동적 계획법 기초  (0) 2019.04.08
브루트 포스  (0) 2019.04.01
수학  (0) 2019.03.20
시뮬레이션  (0) 2019.03.20
반응형

2309번 문제 : 일곱 난쟁이
https://www.acmicpc.net/problem/2309

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int num = 9;
    int sum = 0;
    vector<int> v;
    int a, b;
 
    while (num > 0)
    {
        int inp;
        cin >> inp;
        v.push_back(inp);
        sum += inp;
        num -- ;
    }
 
    sort(v.begin(), v.end());
 
    bool flag = false;
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = 0; j < v.size(); j++)
        {
            if (sum - (v.at(i) + v.at(j)) == 100)
            {
                a = i;
                b = j;
                flag = true;
                break;
            }
        }
        if (flag)
            break;
    }
    
    for (int i = 0; i < v.size(); i++)
    {
        if (i == a || i == b)
            continue;
        cout << v.at(i) << endl;
    }
    
    
    return 0;
}
cs


메모:
- 모든 숫자의 합 - 2개의 합 = 100인 숫자 찾음 -> 이 생각을 못하면 문제가 상당히 어려워짐...
- 2개의 합 모든 경우의 수를 for문에 돌려서 찾음
- iterator를 이용해 깔끔하게 erase하고 싶었지만 첫번째 index를 erase하는 순간 값들이 shift하면서 두번째 index값이 바뀜... 그래서 erase하지 못함. 특정 index 여러개를 동시에 erase하는 방법은 없는듯 (remove로는 범위밖에 못함)

2231번 문제 : 분해합

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

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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int GetContrustor(int num)
{
    int sum = num;
    while (num > 0)
    {
        sum += num % 10;
        num /= 10;
    }
 
    return sum;
}
 
int main()
{
    int inp;
    cin >> inp;
 
    for (int i = 0; i < inp; i++)
    {
        if (inp == GetContrustor(i))
        {
            cout << i << endl;
            break;
        }
        
        if (i == inp - 1)
            cout << 0 << endl;
    }
 
    return 0;
}
cs


1065번 문제 : 한수
https://www.acmicpc.net/problem/1065

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
#include <iostream>
#include <vector>
 
using namespace std;
 
bool CheckIfSansoo(int n)
{
    if (n < 100)
    {
        return true;
    }
 
    vector<int> v;
 
    while (n > 0)
    {
        int num = n % 10;
        v.push_back(num);
        n /= 10;
    }
    
    int diff = v.at(0) - v.at(1);
    for (int i = 0; i < v.size() - 1; i++)
    {
        int temp = v.at(i) - v.at(i + 1);
        if (diff != temp)
            return false;
    }
    return true;
 
}
 
int main()
{
    int inp;
    cin >> inp;
    int num = 0;
 
    for (int i = 1; i <= inp; i++)
    {
        if (CheckIfSansoo(i))
            num++;
    }
 
    cout << num;
 
    return 0;
}
 
cs


1038번 문제 : 감소하는 수
https://www.acmicpc.net/problem/7568

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;
 
struct PersonInfo
{
    int weight;
    int height;
    int ranking;
};
 
int main()
{
    int num;
    cin >> num;
 
    vector<PersonInfo> v;
 
    while (num > 0)
    {
        int inpA, inpB;
        cin >> inpA >> inpB;
        v.push_back({ inpA, inpB, 1 });
        num--;
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = 0; j < v.size(); j++)
        {
            if (v.at(i).height < v.at(j).height && v.at(i).weight < v.at(j).weight)
                v.at(i).ranking++;
        }
    }
 
    for (auto i : v)
        cout << i.ranking << " ";
 
    return 0;
}
 
cs

1038번 문제 : 감소하는 수
https://www.acmicpc.net/problem/1038

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>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int main()
{
    int inp;
    cin >> inp;
    vector<long long> v;
 
    for (int i = 0; i <= 9; i++)
    {
        int vSize = v.size();
        //v.size() should not be used due to the change of the size changing after pushing back the result inside a loop
        for (int j = 0; j < vSize; j++) 
        {
            string result = to_string(i) + to_string(v.at(j));
            v.push_back(stoll(result)); //stoi -> int       stol -> long       stoll -> long long
        }
        v.push_back(i);
    }
    sort(v.begin(), v.end());
 
    if (v.size() > inp)
        cout << v.at(inp) << endl;
    else
        cout << -1 << endl;
 
    return 0;
}
cs


메모:
-규칙을 찾으면 0 / 10, 1, 0 / 210 21, 20, 2, 10, 1, 0 / 3210, 321, 320 ,32, 310 , 31, 30, 3 ....
-루프문에 동적배열인 vector.size() (벡터 크기) 기준으로 루프가 돌때 루프안에서 vector를 push하거나 erase, remove하면 size()가 변하기 때문에 이를 감안하면서 코드를 짜야함
-문자열을 int, long, long long로 변환할때: stoi -> int       stol -> long       stoll -> long long (c++11이상)






반응형
저작자표시 (새창열림)

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

동적 계획법 기초  (0) 2019.04.08
그래프(DFS, BFS)  (0) 2019.04.04
수학  (0) 2019.03.20
시뮬레이션  (0) 2019.03.20
최대공약수/최소공배수  (0) 2019.03.18
반응형

1977번 문제 : 완전제곱수

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


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
#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
 
    double a, b;
    cin >> a >> b;
    int min = ceil(sqrt(a));
    int max = floor(sqrt(b));
 
    if (min <= max)
    {
        int sum = 0;
        for (int i = min; i <= max; i++)
        {
            sum += pow(i, 2);
        }
 
        cout << sum << endl;
        cout << pow(min, 2) << endl;
 
    }
    else
    {
        cout << "-1" << endl;
    }
 
    return 0;
}
cs




반응형
저작자표시 (새창열림)

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

그래프(DFS, BFS)  (0) 2019.04.04
브루트 포스  (0) 2019.04.01
시뮬레이션  (0) 2019.03.20
최대공약수/최소공배수  (0) 2019.03.18
이항 계수  (0) 2019.03.13

+ Recent posts

티스토리툴바