개발 블로그

문제 링크 : https://www.acmicpc.net/problem/2064

문제

네트워크에 연결되어 있는 컴퓨터들은 각각 하나의 IP 주소를 갖게 된다. 그리고 이러한 IP 주소를 갖는 컴퓨터들이 여러 개 모여서 하나의 IP 네트워크를 구성하게 된다. IP 네트워크는 ‘네트워크 주소’와 ‘네트워크 마스크’라는 두 개의 정보로 표현된다.

IP 주소는 네 개의 바이트로 구성되어 있으며, 각각을 10진수로 나타내고(앞에 0을 붙이지 않은 형태로) 사이에 점을 찍어 주소를 표현한다. 바이트이기 때문에 각각의 수는 0부터 255까지의 값을 갖게 된다. 네트워크 주소와 네트워크 마스크 역시 같은 형식으로 나타낸다.

IP 네트워크에 대해 올바르게 이해하기 위해서는 위와 같은 주소를 2진수로 이해하면 된다. 즉, 각각의 바이트를 8자리의 이진수로 나타내고, 이를 네 개 붙여놓은(앞에서부터) 32자리의 이진수를 생각해 보자. IP 네트워크에는 기본적으로 2m 개의 컴퓨터(혹은 IP 주소)가 할당될 수 있다. 이 경우의 네트워크 주소는 앞의 32-m 자리가 임의의 수(0 또는 1)로 구성되어 있고, 뒤의 m자리는 0으로 채워지게 된다. 네트워크 마스크는 앞의 32-m 자리가 1로 채워져 있고, 뒤의 m자리는 0으로 채워지게 된다. 이와 같은 IP 네트워크에는 앞의 32-m 자리가 네트워크 주소와 일치하는 모든 IP들이 포함되게 된다.

예를 들어 네트워크 주소가 194.85.160.176이고, 네트워크 마스크가 255.255.255.248인 경우를 생각해 보자. 이 경우, 이 네트워크에는 194.85.160.176부터 194.85.160.183까지의 8개의 IP 주소가 포함된다.

어떤 네트워크에 속해있는 IP 주소들이 주어졌을 때, 네트워크 주소와 네트워크 마스크를 구해내는 프로그램을 작성하시오. 답이 여러 개인 경우에는 가장 크기가 작은(포함되는 IP 주소가 가장 적은, 즉 m이 최소인) 네트워크를 구하도록 한다.

입력

첫째 줄에 정수 n(1≤n≤1,000)이 주어진다. 다음 n개의 줄에는 각 컴퓨터의 IP 주소가 주어진다.

출력

첫째 줄에 네트워크 주소를, 둘째 줄에 네트워크 마스크를 출력한다.

접근 방법

1) 입력받은 각 ip 주소를 의미하는 문자열을 '.'를 기준으로 split 하여 inputIp[]에 넣는다. 다음 바이트 자리 숫자를 입력받을때는, 먼저 왼쪽으로 8비트를 shift한 뒤에 입력받은 숫자를 or 연산을 이용하여 inputIp[]를 갱신한다.

2) 주소의 4byte 즉 32bit에서 하나라도 다른 비트가 나온 첫 비트를 찾는다. 

   i                            31 ...     24 23... 16  15...      8   7...         0

  194.85.160.177 = 10000010 1010101 10100000 10110001

  194.85.160.183 = 10000010 1010101 10100000 10110111

  194.85.160.178 = 10000010 1010101 10100000 10110010

에서는, 첫번째부터 i = 31이라고 했을 때 i=31...3까지는 모두 비트가 일치하다가 i=2에서 일치하지 않는 비트가 처음으로 생긴다.

비트가 일치했던 i=31...3에 대해서는 subnet |= 1 연산을 통해서 

subnet : 11111111 11111111 11111111 11111000 (255.255.255.248) 를 만들어 놓는다.

4) print() 에 파라미터로 subnet & inputIp[0]를 넘겨서 네트워크 주소를 출력하고, 

subnet도 넘겨서 네트워크 마스크를 출력한다.

print() 가 동작하는 원리

for문에서 shift의 값은 24, 16, 8,0 순으로 변한다. 

그래서 32비트로 넘어온 num을 네파트로 나눠서 1byte씩 8비트의 수를 십진수로 출력하게 되는 것이다. 

(1<<8) -1 는 2^8에서 1을 뺀 수로 8비트가 1로 이루어진 수를 의미한다. 이 수와 & 연산을 한다는 것은 num>>shift의 값 중 8비트만 출력하겠다는 의미이다. 

//
//  SM_BOJ2064_IP주소.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//3:42
//

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
#include <cmath>
using namespace std;

void print(int num){    //num은 32비트 수 -> 8비트씩 끊어서 십진수로 출력해야함
    
    int shift = 24;
    for(int i = 0; i<4; i++, shift -= 8){
        cout << ((num>>shift) & (1<<8)-1);  //31bit->7bit... 24bit->0bit /// 23bit->7bit...
        if(i != 3) cout << '.';
    }
    cout << "\n";
}
int main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    int n; cin >> n;
    string ip;
    
    //ip 주소 입력
    int inputIp[n];
    for(int i = 0; i<n; i++){
        cin >> ip;
        istringstream ss(ip);
        string tmp;
        while(getline(ss,tmp,'.')){
            inputIp[i] <<= 8;       //8비트 왼쪽으로 shift 해서 자리 만들고
            inputIp[i] |= stoi(tmp);    //or 연산
        }
    }
    
    int subnet = 0; //inputIp[n]들이 모두 어디 byte까지 같은지
    //각 바이트 자리끼리 비교해서 달라지는 비트 몇번 비트인지 확인
    int netAddr = 0;
    for(int i = 31; i>=0; i--){
        
        int bit = 1 << i;   //i만큼 왼쪽 shift -> &연산을 통해 오른쪽에서 i번째 비트를 뽑아 비교하기 위함.
        bool isContinue = true;
        for(int r=1; r<n; r++){
            if((inputIp[0] & bit) != (inputIp[r] & bit)){//기준은 첫번째로 입력한 ip 주소.
                isContinue = false;         //비트 달라지는 즉시 검사 중단.
                break;
            }
        }
        if(!isContinue) break;
        else {
            subnet |= bit;         //n개의 ip주소에 대해 해당 비트가 모두 같으면 1로 채워나감.
            
        }
    }
    
    //subnet : 11111111 11111111 11111111 11111000 (255.255.255.248)
    
    print(subnet & inputIp[0]); //뒤에 m개만(다른부분만) 0으로 만들고 앞의 32-m개는 inputIp[0]와 같게
    print(subnet);
    
    
    
    
    
    return 0;
}

참고 : (https://donggod.tistory.com/88)

문제 링크 : https://www.acmicpc.net/problem/1062

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

접근 방법

int형은 4byte( = 32bit) 이므로 0부터 (2^32 - 1)까지 표현할 수 있다. 

여기서 알파벳은 총 26개이므로 0번비트부터 25번 비트까지만 사용하므로 int 형 내에서 커버가능하다.

먼저 N개의 단어를 입력받는데, 이때 단어를 이루고 있는 알파벳을 체크해서 word[]에 비트마스크로 표시한다. 

ex) 0번째 단어가 "antarctica"라고 하면, 이 단어를 이루고 있는 알파벳 [a,c,i,n,r,t]를 아래와 같이 비트로 표현해서 word[0]에 저장한다.

그 다음으로 K의 값을 따진다.

case 1) 5보다 작으면 N개 단어 모두 읽지 못하게 될 것이다. 왜냐하면 N개의 단어들 중에 최대한 많이 읽어야 하는데, 각 단어는 무조건 "a,n,t,i,c"가 포함된다고 했기 때문이다.

case 2) 만약 K가 26이면 모든 알파벳을 알고 있으므로 N개의 단어 모두 읽을 수 있다.

case 3) K가 5도 아니고 26도 아니면 chcked 변수를 초기화한뒤 DFS()를 호출한다.

cheked 변수는 이때까지 배운 알파벳들을 비트로 표현한 것이다.

DFS()에서는 완전탐색으로 26개의 알파벳 중에 K-5개를 선택하는 모든 경우를 따지게 된다. 단, 시간복잡도를 줄이기 위해 start 파라미터를 이용해서 중복조합을 구했다. (a,b를 선택하는 경우나 b,a를 선택하는 경우나 같기 때문이다.)

toPick이 0이 되면, 즉 배워야할 알파벳을 다 선택했으면, 그 알파벳들로 읽을 수 있는 단어가 N개 중 몇개인지 카운트한다. 

알파벳을 선택하는 조합을 바꿀 때마다 "읽을 수 있는 단어 수의 최대값"을 갱신한다. 

모든 경우를 따진 뒤 최대값을 출력한다.

//
//  비트_BOJ1062_가르침.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int checked;
int word[50];   //N 최대 50개
int N, K;

int maxi = 0;

void DFS(int toPick, int start, int checked){    //증복조합
    
    if(toPick==0){  //배울 알파벳 골랐으면
        
        //그 알파벳들로 N개 단어 중 몇개 읽을 수 있는지 카운트해서 최대값 찾기
        int cnt = 0;
        for(int i = 0; i<N ;i++){
            if((word[i] & checked) == word[i]) cnt++;
        }
        if(maxi < cnt) maxi = cnt;
        return;
    }

    for(int i = start; i<26; i++){
        if((checked & (1<<i)) == 0){   //방문 안 한 경우에만
            checked |= (1<<i);
            DFS(toPick-1, i, checked);
            checked &= ~(1<<i);
        }
        
    }
}

int main(){
    
    cin >> N >> K;
    
    string str;
    for(int i = 0; i<N; i++){
        cin >> str;
        
        int num = 0;
        for(int j = 0; j<str.length(); j++){
            num |= 1 << (str[j] - 'a');
        }
        word[i] = num;
    }
    
    if(K<5) cout << 0;  //anta ~ tica 읽으려면 최소 a,n,t,i,c 5개 이상은 알고 있어야함
    else if (K==26) cout << N;
    else{
        
        //a, n, t, i, c 를 이미 알고 있음을 초기화.
        checked |= 1 << ('a'-'a');
        checked |= 1 << ('n'-'a');
        checked |= 1 << ('t'-'a');
        checked |= 1 << ('i'-'a');
        checked |= 1 << ('c'-'a');
        
        DFS(K-5, 0, checked);
        cout << maxi;
    }
 
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/2098

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

접근 방법

처음에는 DFS로 완전탐색을 생각했었는데,

1->2->3->4->1

2->3->4->1->2

이와 같이 중복이 발생하므로 DP와 비트연산을 사용했다.

먼저 아래와 같이 정의한다. 

- W : 그래프 G = (V,E)의 인접 행렬 (노드의 연결 관계 나타냄)

- V : 모든 도시의 집합

- A : V의 부분 집합

- D[Vi][A] : A에 속한 도시를 한 번씩만 방문해서 Vi -> V1(시작 노드)로 가는 최단 경로의 길이

여기서 우리가 구할 것은 A가 시작노드인 V1만 제외한 부분집합일 때 즉,  D[Vi][A-{V1}]을 구하는 것이다. 

이제 재귀 관계식을 구하면 아래와 같다. 

- A가 공집합이라면, D[Vi][공집합]은 아무것도 거치지 않고 다이렉트로 Vi -> V1으로 가는 경우이다. 이것은 인접행렬로부터 값을 바로 얻을 수 있다.

- A가 공집합이 아니라면, D[Vi][A]는 두 파트로 나뉜다.

1) W[i][j] : 처음 시작 노드 Vi에서 Vj로 가는 거리(다이렉트 거리)

2) D[Vj][A-{Vj}] : Vj에서 시작해서 {Vi, Vj를 제외한 모든 노드}를 방문하고 다시 시작 노드 Vi로 가는 경로의 길이

예를 들어, j = 2이면 A - {Vj} = {V3, V4}이고, 시작노드 Vi를 V1이라고 하자.

그럼 D[v1][{V3, V4}] = min(W[1][2] + D[V2][{V3, V4}]) = min(length(V1,V2,   V3,V4,V1) , length(V1,V2,    V4,V3,V1))이다.

자세한 설명은 주석으로 표시했다. 

//
//  비트_BOJ2098_외판원순회.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/06.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

#define INF 987654321
#define MAX 16
int N;
int W[MAX][MAX];
int dpCost[MAX][1<<MAX];   //1<<16 = 2^16개의 노드의 방문 여부를 비트로 표시.
int allVisitBit;

int DFStravel(int cur_node, int visited_bit){   //cur_node : 현재 위치 , visited_bit : 현재 위치를 포함해서 방문했던 곳들 비트로 표현
    
    if(visited_bit == allVisitBit){             //다 돌았는데
        if(W[cur_node][0]==0) return INF;   //현재 위치에서 첫 시작 노드(0번)로 돌아갈 수 없으면
        else return W[cur_node][0];         //다 돌고 첫 시작노드로 돌아갈 수 있으면??
    }
    
    //-1이 아니라면 자명한 최소값(dpCost[][]) 바로 리턴.
    if(dpCost[cur_node][visited_bit] != -1 ) return dpCost[cur_node][visited_bit];
    
    //-1이라면
    dpCost[cur_node][visited_bit] = INF;
    for(int i = 0; i<N; i++){
        
        if(W[cur_node][i] == 0) continue;   //연결 안 되어 있어서 길이 없거나
        if((visited_bit) & (1<<i)) continue;    //이미 방문한 곳이면
        
        //DFStravel(i, visited_bit|1<<i) : 현재 노드에서 재귀적으로 다음 노드 방문.
        dpCost[cur_node][visited_bit] = min(dpCost[cur_node][visited_bit],
                                            W[cur_node][i] + DFStravel(i, visited_bit|1<<i));
    }
    return dpCost[cur_node][visited_bit];
}



int main(){
    
    cin >> N;
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            cin >> W[i][j];
        }
    }
    
    allVisitBit = (1<<N) - 1;       //N개 노드 모두 다 방문한 경우 (111...11)
    memset(dpCost, -1, sizeof(dpCost));
    
    int ans = DFStravel(0,1); //0 : 0번 노드가 첫 시작노드 / 1 : 1은 2^0 -> 즉 시작 노드인 0번 노드를 방문했음을 표시)
    //어떤 도시에서 출발하던 비용은 같으므로 0번 노드를 첫 시작노드로 임의 설정.
    
    cout << ans;
    
    return 0;
}

참고 : (https://yabmoons.tistory.com/358),(https://www.youtube.com/watch?v=wj44Dd0zdzM)

문제 링크 : https://www.acmicpc.net/problem/1094

문제

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

막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.

1. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.
   1. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
   2. 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
2. 이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.

X가 주어졌을 때, 위의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.

접근 방법

가장 먼저 생각나는 방법은 우선순위 큐를 이용해 막대기 길이를 오름차순 정렬해서 구현하는 것이었다.

@ 우선순위 큐는 디폴트가 내림차순 정렬이므로, 오름차순 정렬을 위해서는 아래와 같이 선언해주어야 한다. 

priority_queue<int, vector<int>, greater<int>> pq;

그러나 문제를 잘 생각해 보면 처음 가지고 있는 막대기 길이는 64(=2^6)으로 항상 같고,

막대기를 항상 절반으로 자르기 때문에 비트마스킹을 활용해서 풀 수도 있다.

즉, X를 이진수로 나타냈을 때의 1의 개수가 답이 되는 것이다. 처음에 이해가 잘 되지 않았지만 입력 예제를 활용해서 한 단계씩 따져보면 금방 파악할 수 있다.

(백준 사이트 기준으로 두 코드 모두 실행시간은 0ms이다.)

//
//  SM_BOJ1094_막대기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/06.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <queue>
using namespace std;

int main(){
    
    int X; cin >> X;
    
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(64);
    int sum = 64;
    
    while(sum>X){

        //1. 제일 짧은 막대기 꺼내서 절반으로 나누기
        int half = pq.top() / 2;
        pq.pop();
        
        //2. 절반으로 나눈 막대기 2개 push
        pq.push(half);
        pq.push(half);
        
        //3. 제일 짧은 막대기의 절반을 뺀 수가 X보다 크거나 같다면 버림.
        if(sum - half >= X){
            int mini = pq.top();
            sum -= mini;
            pq.pop();
        }
    }
    cout << pq.size();
    return 0;
}

#include <iostream>
using namespace std;

int main(){
    
    int X; cin >> X;
    int ans = 0;
    for(int i = 0; i<=6; i++){
        if(X & (1<<i)) ans += 1;
    }
    cout << ans;
    return 0;
}