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


단순 구현? 일 것 같습니다.


횡단보도를 한 번만 할 수 있다?


즉. 왼쪽길로 쭉 가다가 횡단보도 한번 건너서 오른쪽 길로 쭉 갈 수 밖에 없습니다.

여기서 두가지 예외는 왼쪽 길로 아예 안가고 횡단 보도를 바로 건너서 오른쪽 길로 쭉 가는 방법과

왼쪽 길로 쭉 가서 횡단 보도를 건너서 정보대에 도착하는 방법이 있는데

사실 예외라고 하기엔.. 예외처리를 안해줘도 되기 때문에....ㅎㅎ...



그림으로 표현하면 이렇습니다!

빨간색길과 검은색길 초록색 길!


다 같은 말이죠


그렇다면 i번째에서 횡단보도를 건너는 거리의 식은


거리i = i번째 까지의 왼쪽 길 연속 합 + 횡단 보도 i의 거리 + 1부터 정보대까지의 오른쪽 거리 - 1부터 i까지의 거리


입니다.!


코드는 아래와 같습니다.


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 <vector>
#include <queue>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int cross[MAX_SIZE + 1];
ll edge[MAX_SIZE + 1][2];
 
int main() {
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++) cin >> cross[i];
 
    for (int i = 0; i < 2; i++) {
        for (int j = 2; j <= n; j++) {
            cin >> edge[j][i];
            edge[j][i] += edge[j - 1][i];
        }
    }
 
    ll ret = 1e16;
    int idx = 0;
 
    for (int i = 1; i <= n; i++) {
        ll tmp = edge[i][0] + cross[i] + edge[n][1] - edge[i][1];
 
        if (tmp < ret) {
            ret = tmp;
            idx = i;
        }
    }
 
    cout << idx << ' ' << ret;
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[2140] 지뢰찾기  (0) 2017.12.27
[12845] 모두의 마블  (0) 2017.08.26
[1700] 멀티탭 스케줄링  (0) 2017.08.01
[1992] 쿼드 트리  (0) 2017.07.30
[14488] 준오는 급식충이야!  (0) 2017.07.29

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


와우.. 이 문제 진짜로~ 어렵네요!


진짜 가장 중요한 힌트는 달리기 실력을 상대적인 값으로 바꾸는 것입니다.

다른 분들이 푸신 방법들을 봐도 설명이 상세히 안나와있고.. 코드만 봤을 때는 잘 이해가 안가더라구요.


제가 푼 방법은 런타임 속도는 상대적으로 느리지만 좀 직관적으로 해결했습니다.


상대적으로 바꾸는 이유는 달리기 실력 값이 1 ~ 10^9까지 존재하기 때문에 이 값대로 트리를 형성할 수 없기 때문입니다.

우선 N은 3이상 5 * 10^5이므로 실력의 절대값으로 순위를 매겨서 상대적인 값으로 변환합니다.

순위를 매길 때 저는 정렬을 이용했습니다.


그리고 실력을 상대적인 값으로 바꾼 후에 다시 입력받은 순으로 정렬을 합니다.

그 다음에 트리를 생성하는데요!

세그먼트 트리이므로 tree(1 << ((int)ceil(log2(n)) + 1))!!!

이 뜻이 무엇이냐면 ceil이 어떤 값보다 크거나 같은 수를 찾는 함수인데요

예를 들어서 n = 1024라면 log2를 씌우면 10이라는 값이 나옵니다.

ceil(10)은 10이겠지요

1025를 넣는다면 10.xxxx가 나올 것입니다.

이것 또한 10이 나옵니다.!


무튼 ! 이렇게 해서 트리를 생성하면

for문을 n번 돌면서

나보다 큰 순위의 값이 존재하는지 검사를 해서

최선의 순위를 출력해주면 되는데요


최선의 순위 = 1 + (나보다 빨리 출발한 녀석들 중에 나보다 속도가 빠른녀석들)

입니다.

즉, 내 앞에 달리는 놈들 중에 나보다 빠른녀석들의 개수를 트리에 넣어야해요!


n = 8이라면

0~7까지의 실력 값이 존재합니다.

트리에 나보다 실력이 높은 놈의 수를 세서 1을 더하면 순위가 됩니다!


달리기 문제에서의 예제를 예로 들면

2, 8, 10, 7, 1, 9, 4, 15라는 절대 실력 값이 들어옵니다.

이것을 상대 실력으로 바꾸면

1, 4, 6, 3, 0, 5, 2, 7 이 됩니다!


첫번째 달리기 선수는 상대 실력이 1인데

맨앞에 달리고 있으므로 트리는 비어있습니다.

그러므로 1 + 0으로 최선의 순위는 1이됩니다.


두번쨰 선수! 상대 실력은 4입니다.

트리에는 현재 1의 값 밖에 존재하지 않습니다.

순위는 1 + 0 = 1이 됩니다.


3번째도 마찬가지겠지요.

4번째에서는 상대 실력이 3입니다.

현재 트리에는 3가지의 실력 값이 들어가있는데요.

나보다 큰 실력 값이 몇개인지 찾아야겠지요.


찾아보니 4, 6이라는 실력 값이 존재합니다.

그러므로 1 + 2를 해서 3이라는 최선의 순위를 찾을 수 있습니다.


세그먼트 트리에서 어떻게 자신보다 큰 실력 값을 찾는지는 코드를 통해서 보시기 바랍니다.

궁금한 점은 댓글 달아주시면 답변 드리겠습니다.


풀 코드입니다.

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
 
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e6
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
pii arr[(int)5e5];//실력, 위치
 
int update(vi &tree, int node, int value, int start, int end) {
    if (value < start || end < value) return tree[node]; // 범위 벗어나면 그냥 리턴
    else if (start == end) return tree[node] = 1; // 내가 찾는 value이면 1리턴
 
    int mid = (start + end) / 2;
    return tree[node] = update(tree, node * 2, value, start, mid) + update(tree, node * 2 + 1, value, mid + 1, end);
}
 
int query(vi &tree, int node, int value, int start, int end) {
    if (value < start) return tree[node]; // 내가 찾는 value보다 시작점이 크면 그냥 tree의 개수를 리턴하면 됨.
    else if (end < value || start == end) return 0;
    // end가 나보다 작다는 것은 내 value보다 작으므로 개수를 세면 안됨.
    // 혹은 첫번째 if(value < start) 조건에 안걸렸으면 start == end가 같을 조건은 무조건 start==end가 나보다 작다는 것을 의미
    // 그러므로 0리턴
    
    int ret = 0;
    int mid = (start + end) / 2;
    return query(tree, node * 2, value, start, mid) + query(tree, node * 2 + 1, value, mid + 1, end);
}
 
bool cmp(pii a, pii b) {
    return a.second < b.second;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first;
        arr[i].second = i;
    }
 
    sort(arr, arr + n);
 
    for (int i = 0; i < n; i++) arr[i].first = i;
 
    sort(arr, arr + n, cmp);
 
    vi tree(1 << ((int)ceil(log2(n)) + 1)); // 구간에 데이터가 몇 개 있는지를 파악하는 트리
 
    for (int i = 0; i < n; i++) {
        cout << 1 + query(tree, 1, arr[i].first, 0, n - 1) << '\n';
        update(tree, 1, arr[i].first, 0, n - 1);
    }
    return 0;
}
cs


저작자표시

'알고리즘 > 세그먼트트리, 펜윅트리' 카테고리의 다른 글

[1395] 스위치  (0) 2017.08.30
[12844] XOR  (0) 2017.08.26
[10999] 구간 합 구하기 2  (0) 2017.08.15
[2042] 구간 합 구하기  (0) 2017.08.15

구간 합 구하기1처럼 풀면 시간초과가 나는 문제입니다.

Lazy Propagation + 세그먼트 트리를 섞어서 해결해야하는 문제입니다.
저도 Lazy Propagation ??이라는 알고리즘은 처음 보는데요.

개념은 간단합니다. 지금 할 필요 없는 일은 미루는 개념입니다. 굉장히 게으른 알고리즘이지만 효율이 굉장히 좋은 것 같습니다.


설명 : https://www.acmicpc.net/blog/view/26


여기에 설명이 매우 잘 나와있습니다.


제 코드입니다. 궁금하신건 댓글 달아주시면 무조건 답변 달아드립니다.

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 <vector>
#include <cmath>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
 
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e6
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int arr[MAX_SIZE];
 
ll init(vll &tree, int node, int start, int end) {
    if (start == end) return tree[node] = arr[start];
 
    int mid = (start + end) / 2;
    return tree[node] = init(tree, node * 2, start, mid) + init(tree, node * 2 + 1, mid + 1, end);
}
 
void update_lazy(vll &tree, vll &lazy, int node, int start, int end) {
    if (lazy[node] != 0) {
        tree[node] += lazy[node] * (end - start + 1);
 
        if (start != end) { //leaf노드가 아닐 때만 전파
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
 
ll update_range(vll &tree, vll &lazy, int node, int start, int end, int left, int right, ll add) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) return tree[node];
    else if (left <= start && end <= right) {
        tree[node] += add * (end - start + 1);
 
        if (start != end) {
            lazy[node * 2] += add;
            lazy[node * 2 + 1] += add;
        }
 
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right, add) + update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right, add);
}
 
ll sum(vll &tree, vll &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) return 0;
    else if (left <= start && end <= right) return tree[node];
 
    int mid = (start + end) / 2;
    return sum(tree, lazy, node * 2, start, mid, left, right) + sum(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
 
    int height = (int)ceil(log2(n));
    vll tree(1 << (height + 1));
    vll lazy(1 << (height + 1));
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    init(tree, 1, 0, n - 1);
 
    for (int i = 0; i < m + k; i++) {
        int cmd, a, b;
        ll add;
        cin >> cmd >> a >> b;
        a--, b--;
 
        if (cmd == 1) {
            cin >> add;
            update_range(tree, lazy, 1, 0, n - 1, a, b, add);
        }
        else {
            cout << sum(tree, lazy, 1, 0, n - 1, a, b) << '\n';
        }
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 세그먼트트리, 펜윅트리' 카테고리의 다른 글

[1395] 스위치  (0) 2017.08.30
[12844] XOR  (0) 2017.08.26
[2517] 달리기  (0) 2017.08.16
[2042] 구간 합 구하기  (0) 2017.08.15

세그먼트 트리 OR 펜윅 트리로 해결할 수 있는 문제입니다.


세그먼트 트리랑 펜윅 트리 설명 글은 따로 준비해보겠습니다.


세그먼트트리 : https://www.acmicpc.net/blog/view/9

펜윅트리 : https://www.acmicpc.net/blog/view/21


boj 블로그에 있는 내용입니다.

참고하세요!


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>
#include <string.h>
#include <algorithm>
#include <queue>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
#define INF 0x7fffffff
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int arr[(int)1e6 + 1];
ll tree[(int)1e6 + 1];
 
void update(int idx, int diff, int size) {
    while (idx <= size) {
        tree[idx] += diff;
        idx += (idx & -idx);
    }
}
 
ll sum(int idx) {
    ll ret = 0;
    while (idx) {
        ret += tree[idx];
        idx -= (idx & -idx);
    }
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
 
    //트리를 만드는 과정
    for (int i = 1; i <= n; i++) {
        update(i, arr[i], n);
    }
 
    for (int i = 0; i < m + k; i++) {
        int cmd, a, b;
        cin >> cmd >> a >> b;
 
        if (cmd == 1) {
            update(a, b - arr[a], n);
            arr[a] = b;
        }
        else {
            cout << sum(b) - sum(a - 1) << '\n';
        }
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 세그먼트트리, 펜윅트리' 카테고리의 다른 글

[1395] 스위치  (0) 2017.08.30
[12844] XOR  (0) 2017.08.26
[2517] 달리기  (0) 2017.08.16
[10999] 구간 합 구하기 2  (0) 2017.08.15

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


처음에 단순히 dfs로 해결했습니다.

간단하지만 런타임 시간이 꽤 오래 걸리더군요.

일단 다 풀고나서 다른 분들이 어떻게 풀었나 봤더니


disjoint-set(union-find)로 푸셨더라구요!


그래서 저도 다시 풀어보았습니다.


간단했습니다. 우선 연결되어있다면 union을 해서 같은 그룹으로 묶습니다.

union을 한다고 모든 노드에서의 부모가 바뀌는 것은 아닙니다.

x와 y를 유니온 하면 x와 y의 부모만 바뀌는 것이므로

다시한번 find를 해줘야 완전히 갱신이 됩니다.

아무튼!! 이것은 union-find에 대해서 공부하시면 알게되실겁니다.


그리고 나서 모든 노드에 대해 그루핑이 끝났다면!


그룹이 몇개인지 세어줘야합니다!

저는 간단하게 노드 3천개에 대한 tmp 배열을 만들어서

해당 노드의 부모가 tmp배열에서 true라면 이미 센 그룹이므로 넘어가고 

false라면 안센 그룹이므로 tmp배열을 갱신시켜주고

그룹의 개수를 늘려줍니다.


uinon-find 코드입니다.

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 <string.h>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
pii pos[3000];
int r[3000];
 
int parent[3000];
int n;
 
bool isConneted(int a, int b) {
    int x = pos[a].first - pos[b].first;
    int y = pos[a].second - pos[b].second;
    int z = r[a] + r[b];
 
    return (x * x + y * y) <= z * z;
}
 
int Find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = Find(parent[x]);
}
 
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
 
    if (x != y) {
        parent[x] = y;
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        cin >> n;
 
        for (int i = 0; i < n; i++) parent[i] = i;
        
        for (int i = 0; i < n; i++) {
            cin >> pos[i].first >> pos[i].second >> r[i];
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (isConneted(i, j) && parent[i] != parent[j]) {
                    Union(i, j);
                }
            }
        }
 
        bool tmp[3000] = { 0, };
        int ret = 0;
 
        for (int i = 0; i < n; i++) {
            int p = Find(i);
            if (!tmp[p]) {
                tmp[p] = 1;
                ret++;
            }
        }
 
        cout << ret << '\n';
    }
 
    return 0;
}
cs



dfs코드입니다.

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 <algorithm>
#include <vector>
#include <string.h>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
pii pos[3000];
int r[3000];
bool visit[3000];
int n;
 
int calcDistance(pii a, pii b) {
    int  x = (a.first - b.first);
    int y = (a.second - b.second);
    return x * x + y * y;
}
 
void dfs(int idx) {
    for (int i = 0; i < n; i++) {
        int rSum = r[idx] + r[i];
        if (idx == i || visit[i] || calcDistance(pos[idx], pos[i]) > rSum * rSum) continue;
        visit[i] = 1;
        dfs(i);
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(visit, 0, sizeof(visit));
 
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            cin >> pos[i].first >> pos[i].second >> r[i];
        }
 
        int ret = 0;
 
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                dfs(i);
                ret++;
            }
                
        }
        cout << ret << '\n';
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[2178] 미로 탐색  (0) 2017.09.15
[2667] 단지번호붙이기  (0) 2017.09.15
[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20

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


운영체제 스케줄링 기법을 이용하면 되는 문제입니다..

(어떤건지는 까먹음..)


분류는 그리디 알고리즘이며,

문제 해결 절차는 이렇습니다.


1. 내가 사용할 아이템(장비???)가 꽂혀있는지 확인합니다.

2. 1에서 꽂혀있으면 다음 장비로 넘어갑니다.

3. 1에서 꽂혀있지 않으면 비어있는 포트가 있는지 확인한다.

4. 3에서 빈 포트가 있으면 그냥 꽂는다.

5. 3에서 빈 포트가 없으면 현재 꽂혀 있는 아이템 중에 나중에 가장 늦게 사용하는 아이템 포트를 뺸다.

6. 1~5를 반복한다.


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 <algorithm>
#include <stack>
#include <string>
#include <queue>
#include <cstdio>
using namespace std;
 
#define ll long long
#define MOD ((int)1e9 + 9)
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int arr[100];
bool use[100];
int tab[100];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, nn;
    cin >> n >> nn;
 
    for (int i = 0; i < nn; i++) {
        cin >> arr[i];
        arr[i]--;
    }
 
    int ret = 0;
    int tabIdx = 0;
 
    for (int i = 0; i < nn; i++) {
 
        if (use[arr[i]]) continue; //사용하던 아이템임        
                                   //멀티탭 공간이 남음
        else if (tabIdx < n) {
            tab[tabIdx++] = arr[i];
            use[arr[i]] = 1;
            continue;
        }
 
 
        ret++; // 위 두가지 경우를 제외하고는 뽑을 수 밖에 없음.
 
        int port = 0;
        int farDistance = 0;
 
        //멀티탭에 꽂혀있는 것을 검사
        for (int j = 0; j < n; j++) {
            int distance = INF;
 
            for (int k = i + 1; k < nn; k++) {
                if (tab[j] == arr[k]) {
                    distance = k;
                    break;
                }
            }
 
            if (distance > farDistance) {
                port = j;
                farDistance = distance;
            }
        }
 
        //현재 꽂혀있는 것 중에 가장 먼 아이템을 포트에서 제거
        use[tab[port]] = 0;
        use[arr[i]] = 1;
        tab[port] = arr[i];
    }
 
    cout << ret;
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[12845] 모두의 마블  (0) 2017.08.26
[12841] 정보대 등산  (0) 2017.08.23
[1992] 쿼드 트리  (0) 2017.07.30
[14488] 준오는 급식충이야!  (0) 2017.07.29
[1913] 달팽이  (0) 2017.07.27

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


기본적으로 네트워크 이론이 좀 필요한 문제입니다.


서브넷 마스크 & ip 주소 = 네트워크 주소


라는 것을 알아야하며..

가장 크기가 작은(포함되는 IP 주소가 가장 적은, 즉 m이 최소인) 네트워크를 구하도록 한다.

라는 조건이 중요합니다.


모든 ip에 대해서 공통된 부분을 찾습니다.

모든 ip에 대해서 공통된 부분(왼쪽 비트 부터 시작해서 오른쪽 비트로 갈 때)

만약 다른 부분이 있으면 멈춰야합니다.


ip에서 네트워크 주소나 서브넷을 따질 때

nnnn.nnnn.nnnn.nnhh

이런식으로 n은 이어져야합니다.(n은 네트워크 h는 호스트)


무튼... 기본 이론은 이러합니당..


공통된 부분은 전부 1로 가득채워서 서브넷 마스크를 구하면

서브넷 마스크 & 임의의 ip주소 = 네트워크 주소 를 출력할 수 있습니다.


코드입니다.


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>
#include <cstdio>
 
using namespace std;
 
int ip[1000];
 
void print(int mask) {
    int shift = 24;
    for (int i = 0; i < 4; i++, shift -= 8) {
        cout << ((mask >> shift) & (1 << 8) - 1);
        if (i != 3) cout << '.';
    }
    cout << '\n';
}
 
int main() {
    int n;
    cin >> n;
 
    //ip입력받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            int a;
            cin >> a;
            ip[i] <<= 8;
            ip[i] |= a;
            getchar();
        }
    }
 
    //서브넷
    int subnet = 0;
 
    //0번째 ip와 틀린부분 찾기
    //찾으면 탈출해서 틀린부분 전까지는 전부 1로 채우기.
    for (int i = 31; i >= 0; i--) {
        int bit = 1 << i;
        bool end = 0;
 
        for (int j = 1; j < n; j++) {
            if ((ip[0] & bit) != (ip[j] & bit)) {
                end = 1;
                break;
            }
        }
 
        if (end) break;
        else subnet |= bit;
    }
 
    //네트워크 주소 출력하기
    print(ip[0] & subnet);
    //서브넷 주소 출력하기
    print(subnet);
 
    return 0;
}
cs


저작자표시

'알고리즘 > 비트마스크' 카테고리의 다른 글

[1322] X와 K  (0) 2017.08.01
[13701] 중복 제거  (1) 2017.07.06

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


범위 안보고 그냥 풀었다가 시간초과...ㅎㅎㅎㅎ...

K값이 20억까지인데 그렇다면 K의 시간으로는 해결할 수 없습니다.


X + Y = X | Y

+연산과 OR연산이 같을 조건은

생각해보면 금방 알 수 있습니다.


OR은

0 0 0

0 1 1

1 0 1

1 1 1


입니다.


그러므로 X를 비트로 바꿨을 때 0인 digit??을 1로 바꿔준다면 같아질 수 있습니다.


예를 들어 보겠습니다.


1001(9)라는 수가 있습니다.

이 이진수에 2 혹은 4 혹은 6 등등을 더하면 덧셈과 OR연산이 같아지는 것을 볼 수 있습니다.

2 -> 10

4 -> 100

6 -> 110


아 그렇다면 0인 부분(부분? 자리??)에서 K번째 수를 찾으면 된다는 이야기입니다.


위에서 예를들면 K = 1이면 2가 되고, 2라면 4가 됩니다. 3이라면 6이됩니다.

4라면 16이 되겠지요.


00000000000000000000001001이라는 수는 9인데 이 비트들에서 1을 제외하고 K번쨰 수 인 값을 찾으면 되는 것입니다.


주의할 것은 쉬프트 연산을 할 때 롱롱으로 캐스팅하는 것을 잊으면 안됩니다.(엄청 틀렸음..ㅠㅠ)


코드입니다.


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 <cstdio>
 
using namespace std;
 
int main() {
    long long x, k;
    cin >> x >> k;
 
    bool binX[64] = { 0, };
    bool binK[64] = { 0, };
 
    int i = 0;
 
    //2진수로 바꿔서 배열에 저장(2진수 리버스임)
    while (x || k) {
        binX[i] = x % 2;
        binK[i] = k % 2;
        x /= 2;
        k /= 2;
        i++;
    }
 
    int ki = 0;
    int xi = 0;
    long long ret = 0;
 
    while (ki < i) {
        //0인 비트를 해당 자리 수 만큼 쉬프트한다.
        if (binX[xi] == 0) {
            ret |= (1LL << xi) * binK[ki++];
        }
        xi++;
    }
    
    cout << ret;
    
    return 0;
}
 
 
cs


저작자표시

'알고리즘 > 비트마스크' 카테고리의 다른 글

[2064] IP 주소  (0) 2017.08.01
[13701] 중복 제거  (1) 2017.07.06

+ Recent posts

티스토리툴바