안녕하세요, 여행벌입니다.

그동안 공부에 집중을 하느라 git에만 정리를 하고 블로그 포스팅을 못하고 있었습니다.

다시 그동안 공부한 내용에 대해서 블로그에 차근차근 정리하며, 댓글도 답해보도록 하겠습니다!

 

이번 포스팅에서는 네트워크의 기본이 되는 인터넷이란 무엇인지, 인터넷에서 사용하는 IP 프로토콜이란 무엇인지에 대해서 다뤄보도록 하겠습니다.

[ 인터넷이란 ]

 우리가 자연스럽게 사용하고 있는 인터넷이란 무엇일까요??

 

 인터넷은 여러 통신망을 하나로 연결한다는 의미의 inter-network 라는 말에서 시작되었으며, 전 세계 컴퓨터들을 하나로 연결하는 거대한 컴퓨터 통신망을 의미합니다. 여러 컴퓨터가 각각 클라이언트와 서버로써 서로 연결되어 구성된 망을 컴퓨터 네트워크라고 하고, 인터넷은 이러한 컴퓨터 네트워크가 전 세계적인 규모로 이루어진 일종의 컴퓨터 네트워크 시스템입니다.

 

 우리가 미국에 있는 친구 노트북과 내 노트북으로 SNS 로 메시지를 주고받을 수 있는 것도 물리적으로 네트워크 기기들이 연결이 되어있고 (해저광케이블 등!) 그렇게 형성된 인터넷을 이용하기 때문에 가능한 것입니다.

 

[ 인터넷 4계층 ]

 인터넷은 4개의 계층으로 이루어져 있습니다. 계층 구조로 형성되어있기 때문에, 문제가 생겼을 때 문제가 되는 계층만 파악하고 고치면 되므로 대처하기 편하다는 장점이 있습니다.

  • 애플리케이션 계층 - HTTP, FTP
  • 전송 계층 - TCP, UDP
  • 네트워크 계층, 인터넷 계층 - IP
  • 링크 계층 - LAN 장비

네트워크01

 

[ IP, 인터넷프로토콜 ]

 인터넷에서 서로 다른 컴퓨터가 어떻게 통신을 할까요??

 어떤 방식으로 통신을 주고받을지 정해놓은 규약을 IP (인터넷프로토콜) 이라고 합니다.

 

 인터넷 프로토콜은 기본적으로 다음과 같이 동작합니다.

  • 지정한 IP주소에 패킷(Packet) 이라는 통신 단위로 데이터 전달
    • 즉, 인터넷 프로토콜의 역할은 개개의 패킷을 상대방에게 전달하는 것이다.
  • IP 주소는 각 노드에 부여된 주소를 가리키고 MAC 주소는 각 네트워크 카드에 할당된 고유의 주소다. IP 주소는 변경 가능하지만 MAC 주소는 변경할 수 없고, IP 주소와 MAC 주소를 이용해 통신을 합니다.

 인터넷에서 통신을 할 때 여러 대의 컴퓨터와 네트워크 기기를 중계해서 상대방에게 도착합니다. (인터넷 망이 여러 중간 노드들로 이루어져 있기 때문에 ) 이때, ARP (Address Resolution Protocol )을 이용하는데 도착지의 IP 주소를 바탕으로 거쳐가야 하는 기기들의 MAC 주소를 조사해서 최종적으로 도착하게 됩니다.

 

network01_3

꿀팁!

IP주소는 컴퓨터마다 서버한테 부여받은 자기의 주소라고 생각하면 편하다.

 

[ IP 인터넷프로토콜의 한계 ]

 인터넷 프로토콜은 다음과 같은 한계점들이 있습니다.

 먼저, 패킷을 보내고 싶은 상대가 서비스 불능 상태여도 알 수 없기 때문에 패킷을 전송하게 됩니다. 그럼 우리가 원하는 대로 상대방이 패킷을 받을 수가 없게 됩니다.

  • 비연결성
    • 패킷을 받을 대상이 없거나 서비스 불능 상태여도 패킷 전송

 또, 패킷이 제대로 도착했는지 알 수 없습니다. 우리는 무수히 많은 중간 노드들을 통해서 상대방에게 패킷을 전송하기 때문에 중간에 무슨 문제가 있는지, 제대로 전달이 된 건지 알 수 없습니다. 또, 패킷을 순서대로 1, 2, 3 을 보냈는데 패킷 1,2,3이 각각 다른 중간 노드들을 거쳐서 간다면 패킷이 순서대로 전달되지 않습니다.

  • 비신뢰성
    • 중간에 패킷이 사라질 수 있음. ( 중간 인터넷망에서 문제가 생길 수 있음 )
    • 패킷 순서를 보장하지 않음.

 마지막으로, IP 주소를 이용해서 상대방을 찾기 때문에 하나의 노트북에서 여러 애플리케이션을 실행 중이고 그중 채팅 애플리케이션을 통해 다른 IP 주소와 소통하고 있다면 상대방은 내 노트북의 어떤 애플리케이션에게 패킷을 전달해야 될지 알 수 없습니다.

  • 프로그램 구분
    • 같은 IP를 사용하는 서버에서 통신하는 애플리케이션끼리 구분 불가능.

오늘은 인터넷이 무엇인지, 인터넷에서 통신하기 위해 사용하는 IP(인터넷 프로토콜)에 대해서 알아봤습니다.

IP (인터넷 프로토콜) 만으로는 많은 한계점이 있기 때문에, 다른 계층과 다른 프로토콜들이 추가로 등장했습니다.

다른 프로토콜에 대해서는 다른 포스팅에서 정리해보도록 하겠습니다.

 

참고

- 김영한님의 모든 개발자를 위한 HTTP 웹 기본 지식

- 그림으로 배우는 HTTP&Network Basic

'Dev > Network' 카테고리의 다른 글

[Network] HTTP_Response_상태코드  (0) 2021.04.23
[Network] HTTP_Message  (0) 2021.04.22
[Network] HTTP_Method  (0) 2021.04.21
[Network] HTTP ( HyperText Transfer Protocol )  (0) 2021.04.20
[Network] TCP / UDP 프로토콜, 3way / 4way handshake  (0) 2021.04.19

문제 : www.acmicpc.net/problem/1747

에라토스테네스체

[ 알고리즘풀이 ]

 

 N에서 시작해 소수이면서 팰린드롬인 숫자를 찾을 때까지 N보다 크거나 같은 수를 순회한다. 

 1) 소수인지 체크

 : 에라토스테네스 체를 이용해 입력 최댓값인 100만 보다 넉넉히 큰 1000만까지 소수를 다 구해놓는다.

 --> 입력 최대값인 100만을 입력했을 때 정답이 100,3001 이므로 1000만까지 안 해도 됐었다...!!

 

 2) 팰린드롬인지 체크

 : 숫자의 각 자리를 추출해서 vector에 담아두고 팰린드롬인지 체크하면 된다.

 

[ 코드구현 C++ ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
bool isPrime[10000001];
 
void eratos() {
    isPrime[0] = isPrime[1] = true;
    for (int i = 2; i <= 10000000; i++) {
        if (!isPrime[i]) {
            for (int j = 2 * i; j <= 10000000; j += i)
                isPrime[j] = true;
        }
    }
}
 
bool isPalindrome(int x) {
    vector<int> numbers;
    while (x) {
        numbers.push_back(x % 10);
        x /= 10;
    }
    bool ans = true;
    for (int i = 0; i < ((int)numbers.size() / 2); i++) {
        if (numbers[i] != numbers[numbers.size() - 1 - i]) ans = false;
    }
    return ans;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    eratos();
    int N, x;
    cin >> N;
 
    x = N;
    while (1) {
        if (!isPrime[x] && isPalindrome(x)){
            cout << x << '\n';
            break;
        }
        x++;
    }
    return 0;
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ1747.cpp

 

travelbeeee/ProblemSolving

백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 9202 : Boggle  (0) 2020.09.17
[BOJ] 14226 : 이모티콘  (0) 2020.09.15
[BOJ] 1107 : 리모컨 고치기  (0) 2020.09.14
[BOJ] 17404 : RGB거리 2  (0) 2020.09.03
[BOJ] 9576 : 책 나눠주기  (0) 2020.09.02

문제 : www.acmicpc.net/problem/9202

Sort Backtracking BinarySearch

[ 알고리즘풀이 ]

 

-Sorting

1) 단어사전을 입력받고 sort를 진행한다. ( binary search 를 위해 )

 

-Backtracking

2) 4 x 4 보드 판을 입력받고, 모든 지점에서 만들 수 있는 모든 단어를 Backtracking 을 이용해서 만든다.

 

-BinarySearch 

3) 만들어진 단어가 단어사전에 있는지 binary search를 이용해 탐색한다.

 

4) 이진탐색 결과가 실패라면 넘어가고, 성공이라면 가장 긴 단어와 score, 단어 count를 갱신한다.

이때, 같은 단어를 만들어서 찾은 경우라면 한 번만 count 해야 되므로 isSelected bool 배열을 이용해 단어 사전에서 탐색에 성공한 단어들은 체크해둔다.

 

 5) (2) ~ (4) 과정을 보드판마다 반복한다.

 

[ 코드구현 C++ ]

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
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
int w, b;
int scores[9] = { 0, 0, 0, 1, 1, 2, 3, 5, 11 };
int dx[8] = { -1, -1, -1, 0, 1, 1, 1, 0 }, dy[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
 
string dictionary[300000];
 
int cnt, score;
bool isSelected[300000];
bool visited[4][4];
string board[4];
string longWord;
 
bool isInside(int x, int y) {
    return (0 <= x && x < 4 && 0 <= y && y < 4);
}
 
int binary_search(string word) {
    int left = 0, right = w - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (dictionary[mid] == word) return mid;
        else if (dictionary[mid] < word) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
 
void makeWord(int x, int y, string word) {
    if (int(word.length()) >= 9) return;
    if (word.length() >= 1) {
        // binarySearch로 찾기
        int ind = binary_search(word);
        if (ind != -1) {
            if (word.length() > longWord.length()) longWord = word;
            else if (word.length() == longWord.length() && word < longWord) longWord = word;
            if (!isSelected[ind]) {
                isSelected[ind] = 1;
                cnt++;
                score += scores[word.length()];
            }
        }
    }
 
    for (int i = 0; i < 8; i++) {
        int nextX = x + dx[i], nextY = y + dy[i];
        if (!isInside(nextX, nextY)) continue;
        if (visited[nextX][nextY]) continue;
 
        visited[nextX][nextY] = 1;
        word.push_back(board[nextX][nextY]);
        makeWord(nextX, nextY, word);
        word.pop_back();
        visited[nextX][nextY] = 0;
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> w;
    for (int i = 0; i < w; i++)
        cin >> dictionary[i];
 
    sort(dictionary, dictionary + w);
 
    cin >> b;
    for (int i = 0; i < b; i++) {
        for (int j = 0; j < 4; j++)
            cin >> board[j];
 
        memset(isSelected, 0, sizeof(isSelected));
        longWord = "";
        cnt = 0;
        score = 0;
 
        string word;
        for (int j = 0; j < 4; j++)
            for (int k = 0; k < 4; k++){
                word.push_back(board[j][k]);
                visited[j][k] = 1;
                makeWord(j, k, word);
                visited[j][k] = 0;
                word.pop_back();
            }
        cout << score << ' ' << longWord << ' ' << cnt << '\n';
    }
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ9202.cpp

 

travelbeeee/ProblemSolving

백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 1747 : 소수 & 팰린드롬  (0) 2020.09.18
[BOJ] 14226 : 이모티콘  (0) 2020.09.15
[BOJ] 1107 : 리모컨 고치기  (0) 2020.09.14
[BOJ] 17404 : RGB거리 2  (0) 2020.09.03
[BOJ] 9576 : 책 나눠주기  (0) 2020.09.02

문제 : www.acmicpc.net/problem/14226

BFS

[ 알고리즘풀이 ]

 

 BFS 탐색을 이용해 현재 화면에 있는 이모티콘의 개수와 클립보드에 있는 이모티콘의 개수 정보를 갱신해나가며 답을 구할 수 있다.

 우리는 현재 상태에서 다음 3가지 행동을 할 수 있다.

1) 현재 화면의 이모티콘 개수와 클립보드에 있는 개수가 다르다면 클립보드에 새롭게 복사한다.

2) 현재 클립보드에 있는 개수가 0이 아니라면 현재 화면에 붙여넣기를 한다.

3) 현재 화면에 이모티콘이 0개가 아니라면 하나를 삭제한다.

 

 이렇게 3가지 동작을 수행할 수 있고, 구해야하는 이모티콘의 개수가 S개라면 클립보드에 S 보다 큰 값을 저장하는 경우는 항상 최소가 아니게 되고, 화면에 있는 이모티콘의 개수가 2 * S 가 넘어가는 경우도 최소가 아니게 된다. 따라서, 우리는 화면에 있는 이모티콘의 개수( 0  ~  2 * S ), 클립보드에 있는 이모티콘의 개수 ( 0 ~  S) 가 성립하는 경우만 다루면 된다.

 

[ 코드구현 C++ ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
const int INF = 99999999;
int S;
int visited[2001][1001] = {};
 
bool isInside(int x, int y) {
    return (0 <= x && x <= 2 * S && 0 <= y && y <= S);
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> S;
 
    for (int i = 0; i <= 2 * S; i++)
        for (int j = 0; j <= S; j++)
            visited[i][j] = INF;
 
    queue<pair<int, int>> q;
 
    q.push({ 1, 0 });
    visited[1][0] = 0;
    while (!q.empty()) {
        int curE = q.front().first, curC = q.front().second;
        q.pop();
        if (curE == S) {
            cout << visited[curE][curC] << '\n';
            break;
        }
 
        // 복사
        if (curC != curE) {
            if (isInside(curE, curE) && visited[curE][curC] + 1 < visited[curE][curE]) {
                visited[curE][curE] = visited[curE][curC] + 1;
                q.push({ curE, curE });
            }
        }
        // 붙여넣기
        if (curC != 0 && isInside(curE+curC, curC) && visited[curE][curC] + 1 < visited[curE + curC][curC]) {
            visited[curE + curC][curC] = visited[curE][curC] + 1;
            q.push({ curE + curC, curC });
        }
        // 이모티콘 삭제
        if (isInside(curE - 1, curC) && visited[curE][curC] + 1 < visited[curE - 1][curC]) {
            visited[curE - 1][curC] = visited[curE][curC] + 1;
            q.push({ curE - 1, curC });
        }
    }
 
    return 0;
}}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ14226.cpp

 

travelbeeee/ProblemSolving

백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 1747 : 소수 & 팰린드롬  (0) 2020.09.18
[BOJ] 9202 : Boggle  (0) 2020.09.17
[BOJ] 1107 : 리모컨 고치기  (0) 2020.09.14
[BOJ] 17404 : RGB거리 2  (0) 2020.09.03
[BOJ] 9576 : 책 나눠주기  (0) 2020.09.02

+ Recent posts

티스토리툴바