Wireless access network

1. Wireless Access Network

end system을 router로 연결시키는 access network를 wireless access network라고 한다. 말 그대로 '무선' 에 초점을 맞춘 개념이다. 

 

wireless access network에는 크게 두 가지 종류가 있는데 오늘은 이 두 종류를 살펴보겠다.

 

1) wireless LANs: 

LAN은 Local Area Network의 약자로 local area 직경 1km 이내에 device가 연결될 때 그것을 LAN이라고 한다. 이는 하나의 빌딩, 오피스, 집을 무선으로 연결시키는 것이고 이 때 사용하는 것이 802.11에서 나오는 각종 wifi protocol인 것이다. 조금 더 높은 속도, 안정적인 전송이 가능하게끔 하기 위해 802.11 b/g/n 등 다양한 버전이 나왔고 최근에는 802.11 ay가 나와 20 Gbps 무선촉감인터넷을 가능하게끔 하고 있다. 

 

2) wide-area wireless access:

wide area network를 의미하고 LAN보다 더 넓은 개념이다. 이것의 대표적인 예시가 cellular network이다. cellular 라는 단어를 쓰는 이유는 여러 개의 cell을 써서 넓은 영역을 커버한다고 해서 붙여진 이름이다. cellular network는 수십km, 수백km 까지 커버가 가능하다. 이름이 의미하는 바처럼 cell을 계속해서 확장하면 되기 때문이다. cell 사이에 통신이 가능해야 하기 때문에 cellular network가 여러 네트워크 중에서 어렵고 복잡한 축에 속한다. 3G, 4G, LTE 등 다양한 것이 나왔는데 이는 wireless LAN보다는 속도가 느리지만 6G로 가면 유선 광케이블정도까지 속도를 높일 수 있다고 한다. 

데이터 전송/ 전송 속도/ bandwidth

1. packet 통신

통신 어플리케이션 프로그램은 프로그램 혼자 작동하는 것이 아니라 컴퓨터 내에 데이터를 주고 받으면서 데이터를 기반으로 한 action을 취하고 이를 통해 사용자가 원하는 서비스를 제공해주는 것이다. 이렇게 데이터를 주고받을 때 어떤 경우에는 1,2byte처럼 작은 양의 데이터를 요구할 수도 있지만 어떤 경우에는 많은 양의 데이터를 요구할 수도 있다. 이렇듯, data size가 다 다르기 때문에 다양한 사이즈의 데이터를 일정한 사이즈로 잘라서 이를 개별적으로 포장해서 보내는 과정이 필요하다. 우리는 이 기본단위를 packet이라고 부른다. 

---

2. packet transmission delay

L bit (주로 1200 byte)를 보낸다고 하면 우리는 이것이 몇번째 chunk이고 크기가 어떻게 되고 이러한 추가 정보를 앞에 적어서 함께 보낸다. 이를 우리는 header를 붙인다고 말한다. 만약 우리가 매체의 초당 속도가 R bit라고 한다면 이 패킷을 내보내는 데 걸리는 시간은 자연스럽게 L/R이 된다. 

 

그러면 우리는 이를 packet transmission delay 라고 부른다. L bit packet을 보내는 데 걸리는 시간, 다시 말해 packet의 첫 비트가 링크를 타기 시작하는 순간부터 마지막 bit 가 링크를 타기까지 걸리는 시간을 의미하는 것이다. 

 

3. 전송속도/ bandwidth

생각해보면 R (1초에 보낼 수 있는 bit) 가 클수록 시간이 적게 걸릴 것이다. 따라서 우리는 R을 transmission rate/ 링크의 최대 전송 속도/ link bandwidth/ capacity 등 다양한 용어로 부른다. 

[유니온 파인드] union find 경로 압축

1. union find 경로 압축

Union Find에서 Find 를 할 때 루트가 가장 최 상단에 있다면 시간복잡도가 O(N) 이 나올수가 있기 때문에 굉장히 느리다. 

 

이런 문제점을 해결하기 위해서 우리는 경로 압축이라는 방법을 사용할 수 있다. 

 

부모 루트를 계속 연결시키는 것이 아니라 최상단의 노드를 부모로 정하는 것이다. 이렇게 구현하게 되면 트리의 모양은 바뀌지만 우리가 구현하려고 하는 알고리즘에는 전혀 지장을 주지 않는다. 

 

2. Find 함수 수정 

그래서 우리는 Find 함수를 아래와 같이 조금 수정해주려고 한다.

 

int Find(int x) {
 if (x==parent[x]){
  return x; //루트일 경우 루트 노드 return
 }
 else{
   int y=Find (parent[x]);
   parent[x]=y; // 부모 노드를 최상단 루트로 바꾸어줌
   return y;
 }

}

위 사이트에 올라와있는 코드를 그대로 사용했는데 여기에 parent[x]=y 라는 코드가 추가된 것이다. 

 

이렇게 하면 우리는 O(N)이던 연산의 시간을 O(α(N)) 으로 확실히 줄일 수 있다.

보안 관련 용어 알아보기 malware/virus/worm/DDos/sniffing/spoofing

1. 네트워크 통신 보안 용어

네트워크 통신에 있어서 보안은 굉장히 중요한 주제이기 때문에 보안을 철저히 신경써야 한다는 것은 누구나 아는 사실일 것이다. 요즘에는 공격에도 다양한 종류가 있어서 이에 대한 다양한 용어에 대해 알아볼 필요가 있다.

---

1) malware:

malware는 나쁜 공격을 총체적으로 이르는 말이다. 기기에 침투해서 기기를 감염시키고 하는 행위들을 malware라고 한다. mal은 접두사로 나쁘다는 뜻인데 그렇기 때문에 나쁜 것들을 지칭해서 이르는 말이다. 아래 설명하는 공격행위를 모두 포괄하는 넓은 단어라고 할 수 있다.

 

---

2) virus:

우리가 흔히 알고 있는 바이러스는 자가 복제 기능을 가진 malware 중에 대표적인 예시이다. 바이러스의 대표적인 특징은 user interaction이 있어야 실행된다는 것이다. 다시 말해 대상이 되는 device, program에 일단 침투가 되면 그 프로그램이 실행되어야 그것이 비로소 활성화되는 것이다. User interaction이 있어야 malfunction이 되는 것이다. 그 중에 하나의 예시로 이메일로 바이러스가 침투해있는 것을 들 수 있다. 그 경우 사용자가 이메일을 열어봤을 경우에 바이러스가 퍼지게 되는 것이다. 그런데 자가복제기능을 가지고 있기 때문에 첨부파일에 있던 악성코드가 활성화되어서 이메일 시스템에 온갖 receiver들에 대해 전부 자기를 복제해서 똑 같은 메일을 뿌리게 된다. 바이러스의 자기복제기능도 중요하지만 대상이 되는 파일이 실행될 때만 문제가 되는 것을 기억하는 것이 더 중요하다.

---

3) worm:

worm도 바이러스와 유사하지만 가장 큰 차이로는 user experience가 없어도 실행될 수 있다는 것이다. 네트워크에 연결되어있고 취약한 어플리케이션이 돌고 있으면 거기에 침투되어 스스로 실행될 수 있다.

---

4) spyware:

spyware은 이름 그대로 spy 적인 성격을 가지고 있다. 사용자가 모르게 들어와서 그 컴퓨터에 있는 주요정보를 수집해서 spyware를 침투시킨 해커에게 보고하는 성격이다. spy처럼 몰래 침투해서 주요 정보 keystroke 계속 분석하거나 비밀번호를 입력할 때 몰래 정보를 수집하는 식으로 이루어진다.

---

5) botnet:

인터넷에 연결되어 있으면서 해를 입은 여러 컴퓨터들의 집합을 지칭한다. 아래 DDos 공격에서 사용되는 용어이다. 즉 botnet은 하나의 컴퓨터가 아니라 여러 컴퓨터들의 집합이며, 이들은 모두 사이버범죄자가 악성 소프트웨어를 이용해 빼앗은 좀비 컴퓨터로 구성되어 있다. 쉽게 말해서 공격자가 주변의 많은 컴퓨터에게 악성코드를 심고 그것에 의해 감염된 컴퓨터의 집합체라고 이해하면 될 것 같다.

---

6) DDos: Distrubited denial-of-service

타겟을 하나 정하고 디도스 공격을 한다고 한다. 디도스 공격을 하기 전에 타겟 주변에 있는 많은 컴퓨터(호스트들)를 감염시켜놓는다. 이것들이 위에서 언급했던 botnet을 형성한다고 얘기하는 것이다. 그러면 감염된 Botnet의 각 컴퓨터들이 타겟으로 쓸데없는 패킷을 보낸다. 그러면 타겟 컴퓨터입장에서는 너무 많은 트래픽이 한꺼번에 들어오기 때문에 정상적인 서비스를 거부하고 못하는 것이다. 그래서 이것을 정상적인 서비스의 거부라고 해서, Denial of Service라고 하는 것이다. 이런 공격을 하는 것을 것을 여러 botnet을 통해서 하는 것이기 때문에 Distributed Dos 공격이라고 부른다.

---

7) Sniffing:

어떤 컴퓨터가 destination computer로 데이터를 보내게 되면 주변의 악성 공격자가 지나가고 있는 트래픽을 몰래 훔쳐보는 행위를 일컫는다. 이렇게 몰래 트래픽을 훔쳐보면서 민감한 정보들 (개인정보, 보안 비밀번호 등등)을 얻을 수 있는 것이다. 공유매체 사용하는 Ethernet이나 무선처럼 공중에 뿌리는 것( broadcast 매체)의 경우 정보를 공중에다가 뿌릴 수밖에 없는데 그러면 지나가는 모든 packet들은 몰래 들을 수 있다. 이렇기 때문에 sniffing이라는 행위가 발생하는 것이고 따라서 무선에서는 유선보다 보안이 어려운 것이 사실이다. 이러한 sniffing은 passive한 성격을 띄고 있기 때문에 더 감지하기도 어렵다. 그래서 이렇게 sniffing이 발생할 행위를 염두해 두고 암호화하여서 정보를 보내는 것이 필요할 때가 있다.

---

8) Spoofing:

예를 들어 컴퓨터 A와 컴퓨터 B와에는 신뢰관계가 구축되어 있어서 컴퓨터 B가 보낸 것이라면 컴퓨터 A는 검사를 하지 않는 상황이 있다고 가정해보자. 그런데 만약 악의적인 사용자 컴퓨터 C가 파일을 보내면서 자신이 아니라 source B가 보내는 것처럼 가장하면서 source B의 주소를 보내기도 한다. 이러면 컴퓨터 A는 컴퓨터 B로부터 온 줄 알고 추가 검사를 하지 않은 채로 파일을 받게 된다. 이런 식으로 spoofing이란 악의적인 사용자가 다른 사용자인척 가장하고 무엇인가를 보내는 상황을 지칭한다. 그래서 spoofing을 방지하기 위해서는 end-point authentication, 즉 정말 이 메세지가 거기로부터 온 것인지에 대한 검사를 철저히 해주어야 한다. 

[백준] 17088번 등차수열 변환 문제 풀어보기

1. 문제

www.acmicpc.net/problem/17088

문제는 위 링크에 들어가면 확인할 수 있다.

---

2. 풀이

이 문제는 등차수열의 성질을 활용하여 푸는 문제인데, 첫째항과 공차를 결정하여서 풀 수 있다.

 

가능한 첫째항은 a1, a1+1, a1-1 이렇게 세 가지가 가능하고, 마찬가지로 둘째항은 a2, a2+1, a2-1 이렇게 세 가지가 가능하다. 

 

그러면 총 3*3= 9가지의 경우의 수가 존재하고 첫째항과 공차가 결정되므로 모든 항에 대해서 가능한지 결정해보면 된다. 

3. 코드 

따라서 이를 코드로 구현한 것은 아래와 같다.

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        if (n == 1) {
            System.out.println(0);
            System.exit(0);
        }
        int ans=-1;
        for(int c1=-1;c1<=1; c1++ ){
            for(int c2=-1; c2<=1; c2++){
                int change=0;
                if (c1!=0) change++;
                if (c2!=0) change++;
                int a1=a[0]+c1;
                int d=a[1]+c2-a1;
                boolean ok=true;
                int cur=a1+d;
                for(int i=2; i<n; i++){
                    cur+=d;
                    if (a[i]==cur) continue;
                    else if (a[i]+1==cur || a[i]-1==cur){
                        change++;
                    }
                    else{
                        ok=false;
                        break;
                    }
                }
                if (ok) {
                    if (ans == -1 || ans > change) {
                        ans = change;
                    }
                }
            }
        }
         System.out.println(ans);
    }
}

 

여기서 change란 숫자를 변경하는 횟수를 뜻한다. 1 차이가 나면 1번 변경하면 가능하기 때문에 change를 1 증가시키는 것이다.

[백준] 16943번 숫자 재배치 문제 풀어보기

1. 문제

www.acmicpc.net/problem/16943

문제는 위 링크에 들어가면 확인할 수 있다.

---

2. 풀이

위 풀이에서 매번 순열을 하는 코드는 자바로 아래와 같이 구현할 수 있다.

 static boolean next_permutation(char[] a) {
        int i = a.length-1;
        while (i > 0 && a[i-1] >= a[i]) {
            i -= 1;
        }

        if (i <= 0) {
            return false;
        }

        int j = a.length-1;
        while (a[j] <= a[i-1]) {
            j -= 1;
        }

        char temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;

        j = a.length-1;
        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }

자바에서 순열을 만드는 코드이다. 

---

또한 우리가 문자로 입력을 받았기 때문에 이를 다시 숫자로 돌리는 과정이 필요하다. 

C++의 경우에는 위의 풀이처럼 stoi를 써야 하지만 자바는 이를 또 구현해주는 과정이 필요하다. 

 

char 배열을 int로 바꿔주는 부분의 함수는 아래와 같다.

 

   static int toNum(char[] a) {
        int ans = 0;
        for (char ch : a) {
            ans = ans * 10 + (ch - '0');
        }
        return ans;
    }

---

따라서 매번 순열로 순서를 바꾸어주고 이를 다시 toNum 함수를 사용해서 숫자로 바꾸어주는 것이다. 그런 다음에 문제의 조건을 만족하는지 살펴보면 된다.

 

3. 코드 

전체 코드는 아래와 같다.

import java.util.*;
public class Main {
    static boolean next_permutation(char[] a) {
        int i = a.length-1;
        while (i > 0 && a[i-1] >= a[i]) {
            i -= 1;
        }

        if (i <= 0) {
            return false;
        }

        int j = a.length-1;
        while (a[j] <= a[i-1]) {
            j -= 1;
        }

        char temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;

        j = a.length-1;
        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }
    static int toNum(char[] a) {
        int ans = 0;
        for (char ch : a) {
            ans = ans * 10 + (ch - '0');
        }
        return ans;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        char[] a = sc.next().toCharArray();
        int b = sc.nextInt();
        Arrays.sort(a);
        int ans = -1;
        do {
            int number = toNum(a);
            if (a[0] != '0' && number < b) {
                if (ans == -1 || ans < number) {
                    ans = number;
                }
            }
        } while (next_permutation(a));
        System.out.println(ans);
    }
}

[백준] 17142번: 연구소 3문제 BFS로 풀기

1. 문제 

www.acmicpc.net/problem/17142

문제는 위 링크에 들어가서 볼 수 있다.

---

2. 풀이

이 문제는 먼저 바이러스를 놓을 수 있는 칸에서부터 시작해 바이러스를 m개 놓아야 한다. 그것을 우리는 재귀함수 move로 구현하겠다. 항상 그랬듯이, index와 count를 parameter로 받고 정해진 지점에 도달했을 때, 우리는 bfs를 돌리면서 검사를 하는 것이다. 

 

move의 함수는 아래와 같다.

    static ArrayList<Integer> xs = new ArrayList<>();
    static ArrayList<Integer> ys = new ArrayList<>();
 public static void move(int index,int count){
        if (index==xs.size()){
            if (count==m){
                bfs();
            }
        }else{
            int x = xs.get(index);
            int y = ys.get(index);
            a[x][y] = 3; //바이러스 놓기
            move(index+1, count+1);
            a[x][y] = 2; 
            move(index+1, count);
        }
    }

여기서 xs는 가능한 바이러스의 위치를 알려주는 ArrayList이다. 문제에서 입력받을 때 바이러스를 놓을 수 있는 위치의 행을 xs에, 열을 ys에 저장한다. 그러면 index의 위치가 xs의 size와 같다는 것은 전체 바이러스를 다 검사했다는 것이고, 그 중에서 count의 값이 m이라는 것은 문제의 조건과 일치한다는 뜻이므로 그 때 bfs 함수를 호출해 bfs 검사를 해주면 된다.

---

 static void bfs(){
        int d[][]=new int[n][n];
        Queue<Integer>q=new LinkedList<>();
         for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                d[i][j] = -1;
                if (a[i][j] == 3) {
                    q.add(i);q.add(j);
                    d[i][j] = 0;
                }
            }
        }
        while(!q.isEmpty()){
            int x=q.remove();
            int y=q.remove();
            for(int k=0; k<4; k++){
                int nx=x+dx[k];
                int ny=y+dy[k];
                if (0<=nx && nx<n && 0<=ny && ny<n){
                    if (a[nx][ny] != 1 && d[nx][ny] == -1) {
                        d[nx][ny] = d[x][y] + 1;
                        q.add(nx); q.add(ny);
                    }
                }
            }
        }
        int val = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 0) { //이미 빈칸이었던 애들만 검사
                    if (d[i][j] == -1) return;
                    if (val < d[i][j]) val = d[i][j];
                }
            }
        }
        if (ans == -1 || ans > val) {
            ans = val;
        }
    }

위 코드는 bfs 함수만 적어본 것이다. 일반적인 BFS 코드와 유사하나 다른 점은 문제에서 빈칸이 바이러스에 감염되는 시간을 검사하라고 했으므로 원래 칸이 빈칸이었는지를 하나 더 검사해주어야 한다. 

 

---

3. 풀이

전체 JAVA 코드를 살펴보면 아래와 같다.

import java.util.*;

public class Main{
    static int[][] a;
    static int[][] d;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int n, m;
    static ArrayList<Integer> xs = new ArrayList<>();;
    static ArrayList<Integer> ys = new ArrayList<>();;
    static int ans = -1;
    static void bfs(){
        d=new int[n][n];
        Queue<Integer>q=new LinkedList<>();
         for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                d[i][j] = -1;
                if (a[i][j] == 3) {
                    q.add(i);q.add(j);
                    d[i][j] = 0;
                }
            }
        }
        while(!q.isEmpty()){
            int x=q.remove();
            int y=q.remove();
            for(int k=0; k<4; k++){
                int nx=x+dx[k];
                int ny=y+dy[k];
                if (0<=nx && nx<n && 0<=ny && ny<n){
                    if (a[nx][ny] != 1 && d[nx][ny] == -1) {
                        d[nx][ny] = d[x][y] + 1;
                        q.add(nx); q.add(ny);
                    }
                }
            }
        }
        int val = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 0) { //이미 빈칸이었던 애들만 검사
                    if (d[i][j] == -1) return; //불가능
                    if (val < d[i][j]) {val = d[i][j];}
                }
            }
        }
        if (ans == -1 || ans > val) {
            ans = val;
        }
    }
    public static void move(int index,int count){
        if (index==xs.size()){
            if (count==m){
                bfs();
            }
        }else{
            int x = xs.get(index);
            int y = ys.get(index);
            a[x][y] = 3; //바이러스 놓기
            move(index+1, count+1);
            a[x][y] = 2; 
            move(index+1, count);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                a[i][j] = sc.nextInt();
                if (a[i][j] == 2) {
                    xs.add(i);
                    ys.add(j);
                }
            }
        }
        move(0,0);
        System.out.println(ans);
    }
}