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

 

1764번: 듣보잡

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. ��

www.acmicpc.net

 

해싱 해싱 해싱을할까요

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 <unordered_map>
#include <string>
#include <vector>
#include <algorithm>
 
int N, M;
std::unordered_map<std::string, int> unknownList;
 
std::vector<std::string> ans;
 
void input()
{
    std::cin >> N >> M;
    std::string input;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> input;
        unknownList[input] += 1;
    }
    for (int i = 0; i < M; ++i)
    {
        std::cin >> input;
        unknownList[input] += 2;
        if (unknownList[input] == 3)
        {
            ans.push_back(input);
        }
    }
}
 
int main()
{
    std::cin.tie(0);
    std::cin.sync_with_stdio(false);
    std::cout.tie(0);
    std::cout.sync_with_stdio(false);
    input();
    std::cout << ans.size() << '\n';
    std::sort(ans.begin(), ans.end());
    for (auto& it : ans)
    {
        std::cout << it << '\n';
    }
    return 0;
}
 cs

C++ unordered map의 성능은 날이 갈수록 좋아지고 있다고 한다...

저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

백준 1722 : 순열의 순서  (0) 2020.07.30
백준 8979 : 올림픽  (0) 2020.07.23
백준 9517 : 아이 러브 크로아티아  (0) 2020.07.21
백준 14890 : 경사로  (0) 2020.07.17
백준 1094 : 막대기  (0) 2020.07.16

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

 

1094번: 막대기

지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대��

www.acmicpc.net

 

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>
 
bool binaryArr[8];
int X, ans;
 
void input()
{
    std::cin >> X;
}
 
void solve(int stk, int up, int down)
{
    int mid = up + (down - up) / 2;
    if (mid == X || down == X)
    {
        ans = stk;
        return;
    }
    else if (mid < X)
    {
        solve(stk + 1, mid + 1, down);
    }
    else if (mid > X)
    {
        solve(stk + 1, up, mid - 1);
    }
}
 
void binary_solve()
{
    int i = 1;
    while (X != 0)
    {
        binaryArr[i++] = X % 2;
        X /= 2;
    }
    for (int i = 1; i < 8; ++i)
    {
        if (binaryArr[i])
        {
            ++ans;
        }
    }
}
 
void output()
{
    std::cout << ans;
}
 
int main()
{
    input();
    //solve(1, 1, 64);
    binary_solve();
    output();
    return 0;
}
 cs

 

첨엔 이분탐색 아녀?? 했다가

 

아차차

 

33같은 경우엔 32cm 막대 하나랑 1cm 막대 하나가 필요하다

 

헌데 막대를 자르는 기준은 절반으로 나누는 것이고

 

최대 막대 길이는 64이다

 

64 32 16 8 4 2 1

 

아하!

저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

백준 9517 : 아이 러브 크로아티아  (0) 2020.07.21
백준 14890 : 경사로  (0) 2020.07.17
백준 2455 : 지능형 기차  (0) 2020.07.16
백준 14889 : 스타트와 링크  (0) 2020.07.15
koi : 선물(M)  (0) 2020.07.14

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

 

2455번: 지능형 기차

최근에 개발된 지능형 기차가 1번역(출발역)부터 4번역(종착역)까지 4개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. �

www.acmicpc.net

 

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>
 
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
class train_simulator
{
public:
    void get_in(unsigned int passingers)
    {
        _passingers += passingers;
        _compMaximum();
    }
    void get_out(unsigned int passingers)
    {
        _passingers -= passingers;
    }
    unsigned int get_maximum_passingers()
    {
        return _maximumPassingersPerDay;
    }
private:
    void _compMaximum()
    {
        _maximumPassingersPerDay = _maximumPassingersPerDay < _passingers ? _passingers : _maximumPassingersPerDay;
    }
private:
    unsigned int _passingers = 0;
    unsigned int _maximumPassingersPerDay = 0;
};
 
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
void input(train_simulator& myTrain)
{
    unsigned int passingers_in, passingers_out;
    do
    {
        std::cin >> passingers_out >> passingers_in;
        myTrain.get_out(passingers_out);
        myTrain.get_in(passingers_in);
    } while (passingers_in != 0);
}
 
void output(train_simulator& ans)
{
    std::cout << ans.get_maximum_passingers();
}
 
int main()
{
    train_simulator myTrain;
    input(myTrain);
    output(myTrain);
    return 0;
}
 cs

 

뿌뿌~~~~칙칙폭폭칙칙폭폭칙칙폭폭칙칙폭폭

저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

백준 14890 : 경사로  (0) 2020.07.17
백준 1094 : 막대기  (0) 2020.07.16
백준 14889 : 스타트와 링크  (0) 2020.07.15
koi : 선물(M)  (0) 2020.07.14
koi : 경찰차(M)  (0) 2020.07.14

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

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

 

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
#include <iostream>
 
int n, ans = 987654321;
int team[21][21];
bool visited[21];
 
void input()
{
    std::cin >> n;
    for (int y = 0; y < n; ++y)
    {
        for (int x = 0; x < n; ++x)
        {
            std::cin >> team[y][x];
        }
    }
}
 
int chk(bool flag)
{
    int rest = 0;
    for (int y = 0; y < n; ++y)
    {
        if (visited[y] == flag)
        {
            for (int x = y; x < n; ++x)
            {
                if (visited[x] == flag)
                {
                    rest += team[y][x] + team[x][y];
                }
            }
        }
    }
    return rest;
}
// 0 3 4
// 2 0 4
// 2 4 0
// 19
// 0 2 5
// 1 0 5
// 1 3 0
// 17
void solve(int stk, int fSum, int pivot)
{
    if (stk == n / 2)
    {
        int temp = chk(false);
        int cmpTemp = abs(temp - fSum);
 
        if (cmpTemp < ans)
        {
            ans = cmpTemp;
        }
        return;
    }
 
    for (int i = pivot; i < n; ++i)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            int temp = 0;
            for (int j = 0; j < i; ++j)
            {
                if (visited[j])
                {
                    temp += team[i][j] + team[j][i];
                }
            }
            solve(stk + 1, fSum + temp, i);
            visited[i] = false;
        }
    }
}
 
void output()
{
    std::cout << ans;
}
 
int main()
{
    input();
    solve(0, 0, 0);
    output();
    return 0;
}
 cs

 

완전탐색이지만, 중복에 대한 검사를 어느정도는 해 줘야 풀린다.

 

사실 fSum이 크게 필요는 없었던 것이 아닐까?

 

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
int chk(bool flag)
{
    int rest = 0;
    for (int y = 0; y < n; ++y)
    {
        if (visited[y] == flag)
        {
            for (int x = y; x < n; ++x)
            {
                if (visited[x] == flag)
                {
                    rest += team[y][x] + team[x][y];
                }
            }
        }
    }
    return rest;
}
 
void solve(int stk, int fSum, int pivot)
{
    if (stk == n / 2)
    {
        int temp = chk(false);
        int fff = chk(true);            //변경!
        int cmpTemp = abs(temp - fff);    //변경!
 
        if (cmpTemp < ans)
        {
            ans = cmpTemp;
        }
        return;
    }
 
    for (int i = pivot; i < n; ++i)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            /*int temp = 0;
            for (int j = 0; j < i; ++j)
            {
                if (visited[j])
                {
                    temp += team[i][j] + team[j][i];
                }
            }*/
            solve(stk + 1, fSum, i);
            visited[i] = false;
        }
    }
}
 cs

그것은 팩트였구요

 

하지만 기존에 비해 좀 더 느리다.

 

중요한 점은 dfs 탐색 시 중복값을 얼마나 잘 걸러내느냐

 

모든 배열에 대해 탐색할 필요는 없다

 

이렇게만 탐색해도 충분하다

저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

백준 1094 : 막대기  (0) 2020.07.16
백준 2455 : 지능형 기차  (0) 2020.07.16
koi : 선물(M)  (0) 2020.07.14
koi : 경찰차(M)  (0) 2020.07.14
koi : 거스름 돈(M)  (0) 2020.07.14

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

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

 

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
#include <iostream>
#include <stack>
#include <queue>
 
bool mat[1010][1010];
bool visited[1010];
int n, m, v;
 
void input()
{
    std::cin >> n >> m >> v;
    for (int y = 0; y < m; ++y)
    {
        int from, to;
        std::cin >> from >> to;
        mat[from][to] = true;
        mat[to][from] = true;
    }
}
 
void dfs()
{
    std::stack<int> dfs;
    dfs.push(v);
    while (dfs.empty() == false)
    {
        int currPos = dfs.top();
        dfs.pop();
        if (visited[currPos] == true)
        {
            continue;
        }
        visited[currPos] = true;
        
        std::cout << currPos << ' ';
        for (int x = 1000; x > 0; --x)
        {
            if (mat[currPos][x] == true && visited[x] == false)
            {
                dfs.push(x);
            }
        }
    }
    std::cout << '\n';
}
 
void bfs()
{
    std::queue<int> bfs;
    bfs.push(v);
    while (bfs.empty() == false)
    {
        int currPos = bfs.front();
        bfs.pop();
        if (visited[currPos] == true)
        {
            continue;
        }
        visited[currPos] = true;
 
        std::cout << currPos << ' ';
        for (int x = 1; x <= 1000; ++x)
        {
            if (mat[currPos][x] == true && visited[x] == false)
            {
                bfs.push(x);
            }
        }
    }
}
 
void solve()
{
    dfs();
    for (int i = 0; i < 1010; ++i)
    {
        visited[i] = false;
    }
    bfs();
}
 
void output()
{
 
}
 
int main()
{
    input();
    solve();
    output();
    return 0;
}
 cs

 

벡터로 가지 않으면 시간초과가 날까 조마조마했지만

 

별 상관은 없었다

 

그러니 다시한번 기억하자 dfs는 스택, bfs는 큐

저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

koi : 경찰차(M)  (0) 2020.07.14
koi : 거스름 돈(M)  (0) 2020.07.14
koi : minimum sum(M)  (0) 2020.06.26
koi : 연구활동 가는 길(L)  (0) 2020.06.26
koi : 저울 추(L)  (0) 2020.06.26

+ Recent posts

티스토리툴바