[백준] No.2064 - IP 주소 (C++, 비트 마스크)

문제

 

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

2064번: IP 주소

 

 

풀이

 

solved.ac 난이도: Gold 2

 

비트 마스크로 메모리나 계산 시간을 최적화하는 다른 문제들과 다르게 비트 마스크만을 이용하는 문제.

해당 문제에 등장하는 기법은 실제로 IPv4의 서브넷에 사용된다.

서브넷, 서브넷 마스크를 알아두면 문제를 훨씬 잘 이해할 수 있으므로 새로비님의 게시글을 통해 알아보고 오자.

서브넷, 서브넷 마스크 확실하게 짚고 넘어가자 - 새로비

 

즉, 컴퓨터들의 IP에 서브넷 마스크를 AND연산해준 것이 해당 컴퓨터의 네트워크 주소가 된다.

일단 문자열로 입력받아지는 IP주소들을 32비트의 unsigned int 배열에 저장할 수 있도록 변환해주자.

 

 

int start_idx,temp_num;
unsigned ip_num =0;
 
for(int i=0;i<computer_num ; ++i){
  cin>>temp_str;
  temp_str += ".";
 
  ip_num =0;
  start_idx =0;
  for(int idx=0; idx<temp_str.size() ; ++idx){
    if(temp_str[idx] == '.'){
      sub = temp_str.substr(start_idx,idx- start_idx +1);
      ip_num = (ip_num << 8);
      temp_num = stoi(sub);
      ip_num += temp_num;
      start_idx = idx+1;
    }
  }
 
  computer_ips[i] = ip_num;
}

 

 

 

n개의 IP주소들에서 서브넷 마스크(네트워크 마스크)를 구하기 위해서는

ip주소의 비트들을 최상위 비트(most significant bit, msb) 에서부터 차례대로 순회하면서 다른 비트가 발견되기 전까지 서브넷 마스크를 1로 채워주면 된다.

 

 

unsigned int bit;
bool is_broken;
  
for(int bit_order=31; bit_order>=0 ; --bit_order){
  bit = 1<<bit_order;
  is_broken = false;
 
  for(int idx =1; idx<computer_num ; ++idx){
    if((computer_ips[0] & bit) != (computer_ips[idx] & bit)){
      is_broken = true;
      break;
    }
  }
 
  if(is_broken) 
    break;
  else
    network_mask |= bit;
}

 

최종적으로 어떤 ip주소든 서브넷 마스크(네트워크 마스크)와 AND연산을 해주면 네트워크 주소가 나온다.

 

본인의 경우 모든 IP주소를 AND 연산하여 나온 비트를 각 IP주소에서 빼주어 나온 가장 큰 값을 이용하여 구현하려 했지만 예제들에는 맞는 결과가 나오지만 제출 시 계속 틀려서 결국 신동갓님의 게시글을 참조하였다...

[2064] IP 주소 - 신동갓의 알고리즘

 

해당 구현 코드를 올려드리니 오류를 발견하신 분은 알려주시면 감사하겠습니다.

 

 

  for(int i=1; i<computer_num ; ++i){
    total_and = total_and & computer_ips[i];
  }
  
  unsigned int max_num =0;
  for(int i=0; i<computer_num ; ++i){
    max_num = max(max_num, computer_ips[i] - total_and);
  }
  int cnt=0;
  while(max_num >1){
    max_num = max_num>>1;
    ++cnt;
  }
 
  network_mask = (unsigned int)(1<<31) + ((unsigned int)(1<<31) - 1 );
  network_mask = network_mask <<(cnt+1);

 

정답 코드