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

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


메모리 제한 8MB

n의 범위는 0<= n < 2^25


8MB는 약 2의 23승이므로

n의 범위만큼 배열을 만들 수 없습니다.


해쉬로 해결해보려했으나 N의 개수가 500만이여서 전부 저장할 수 없었습니다.


이 문제는 비트마스크로 해결할 수 있습니다.


핵심은 int가 32비트라는 점입니다.

int가 32비트이므로 비트를 32개 사용할 수 있는 것입니다.


n의 범위가 2^25이지만 몫을 배열의 인덱스로 사용하고 나머지를 해당 인덱스의 값에 비트로 저장하면 표현이 가능해집니다.



배열[ 입력받은 N / 2^5 ] = (N % 2^5) << 1

로 저장을 합니다.

그리고 존재하는지 검사를 할 때는 엔드 연산을 통해서 하면 되겠지요?


아래는 풀 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
 
int exist[(1 << 25) / 32];
int main() {
    int n;
 
    while (~scanf("%d", &n)) {
        int v = n / 32;
        int m = 1 << (n % 32);
 
        if (!(exist[v] & m)) {
            exist[v] += m;
            printf("%d ", n);
        }
    }
 
    return 0;
}
 

c


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

[2064] IP 주소  (0) 2017.08.01
[1322] X와 K  (0) 2017.08.01

+ Recent posts

티스토리툴바