• LeNet : 합성곱 신경망(CNN)의 초기 형태라 할 수 있는 모델. 페이스북의 얀 르쿤이 개발한 딥러닝 모델이다.
• ANN : Artificial neural network, 인공 신경망
• CNN : Convolutional neural netwokr, 합성곱 신경망
• 뉴런 / 유닛 : 인공 신경망의 기본 계산 단위. 뉴런 또는 유닛 둘 다 같은 의미.
• 필터 / 커널 : 합성곱 신경망의 기본 계산 단위. 인공 신경망의 뉴런 / 유닛과 같은 의미다.
• 입력층 : 처음 들어오는 데이터를 받는 곳. 신경망이 처리해야 할 원본 데이터를 전달하는 역할을 맡음.
• 은닉층 : 입력층과 출력층 사이에 있는 모든 층을 은닉층이라고 부름. 복잡한 계산을 통해 입력 데이터의 패턴을 찾고, 중요한 특징을 뽑아냄.
• 출력층 : 최종 결과를 내는 곳. 신경망의 최종 값을 만든다는 의미에서 출력층이라고 부름.
• 합성곱층(convolutional layer) : 이미지의 작은 부분을 스캔하여 중요한 특성을 추출하는 층. 특별히 합성곱 계산을 통해 압축적으로 얻은 출력을 특성 맵^{feature map}이라고 부름.
• 풀링층(pooling layer) : 합성곱층에서 추출한 특성 맵을 압축(축소)하는 층. 특성 맵을 축소해 처리 속도를 높이고, 모델이 더 중요한 패턴에 집중하도록 만드는 층.
• 밀집층(dense layer) : 이전 층에서 추출된 특성을 바탕으로 최종 결과를 도출하는 층. 밀집층의 출력층에서는 추출된 이미지의 패턴을 바탕으로 분류 작업을 수행함. ^{밀집층은 각각의 입력 값이 모든 뉴런에 연결되기 때문에 완전 연결층(fully connected layer)이라고도 불림.}
• 패딩(padding) : 이미지의 가장자리에 빈 공간(0)을 추가해 이미지 가장자리 부분의 픽셀이 처리될 수 있도록 함.
• 세임 패딩(same padding) : 입력과 특성 맵의 크기를 동일하게 만들기 위해 입력 주위에 적절한 개수의 패딩을 추가하는 방식.
• 밸리드 패딩(valid padding) : 패딩 없이 순수한 입력 배열에 대해서만 합성곱을 수행해 특성 맵을 만드는 방식.
• 스트라이드(stride) : 필터가 이미지 위를 이동하는 속도를 의미. 기본값은 1로, 예를 들면 입력 받은 이미지를 필터 크기만큼 1픽셀씩 이동하면서 스캔함.
• 평균 풀링(Average pooling) : 풀링 윈도 내에서 평균값을 구해 출력해 냄.
• 최대 풀링(max pooling) : 풀링 윈도 내에서 최대값을 구해 출력해 냄.

합성곱층(Convolutional layer)

import keras
from keras import layers
import numpy as np

# 정규 분포의 평균 : 0.0(기본값)
# 표준편차 : 1.0
# 생성하려는 배열의 크기 : (10 * 28 * 28 * 10) (w, x, y, z)
# normal() 함수를 사용해 28*28*1 크기의 흑백 이미지 10개를 랜덤으로 생성합니다. (1은 입력 데이터의 채널 수)
x = np.random.normal(size=(10, 28, 28, 1))

1. 필요한 라이브러리를 로드합니다.
2. 테스트에 사용할 (28, 28) 크기 흑백 이미지를 10개 랜덤하게 생성합니다.

conv1 = layers.Conv2D(filters=10, kernel_size=(3, 3))

# 첫 번째 합성곱층에 x를 입력으로 전달하고 특성 맵을 출력합니다.
# 필터 개수와 커널 크기를 지정하는 합성곱층을 추가합니다.
conv_out = conv1(x)

# shape 속성을 사용해 합성곱층을 통과한 입력 데이터의 크기를 확인합니다.
# 커널 크기가 (3, 3)이고 패딩을 추가하지 않았기 때문에 높이와 너비가 2식 줄어들었고
#(valid padding으로 인한 특성 맵 축소)
print(conv_out.shape) # output : (10, 26, 26, 10)

1. Conv2D 클래스로 2차원 합성곱 레이어를 만듭니다(=conv1). filters는 사용할 필터의 개수, kernel_size는 커널의 크기입니다
2. 합성곱 레이어에 입력 데이터를 넣어서 나온 특성 맵의 차원을 출력합니다.
3. 결과가 (10, 26, 26, 10)으로 나왔습니다. 각각의 의미를 살펴보자면,
   • 10 : 10개의 이미지가 그대로 처리되었다. (앞서 설정한 더미 이미지 데이터 10개)
   • 26 : 각 이미지의 높이가 26이다.
   • 26 : 각 이미지의 너비가 26이다.
   • 10 : 필터 10개를 사용했더니, 깊이가 10으로 늘어났다.

필터의 개수가 10개니까 나오는 특성 맵의 개수도 10개고, 이 특성 맵을 하나의 결과로 만들면, 깊이가 10인 특성 맵 하나가 만들어집니다.

높이와 너비가 26으로 줄은 이유는 커널의 크기가 (3, 3)이고, 패딩을 추가하지 않았기 때문입니다.

conv2 = layers.Conv2D(filters=10, kernel_size=(3, 3), strides=(2, 2))

print(conv2(x).shape) # (10, 13, 13, 10)

스트라이드 값을 2로 주니 한 칸 씩 건너 뛰면서 합성곱을 진행해서 출력 크기가 이전보다 절반이 줄어든 모습을 볼 수 있습니다.

# padding 방식을 same(세임)으로 변경합니다.
conv3 = layers.Conv2D(filters=10, kernel_size=3, strides=2, padding='same')

print(conv3(x).shape) # (10, 14, 14, 10)

스트라이드가 2이고 세임 패딩을 사용했기 때문에 (28, 28)이었던 입력의 높이와 너비 크기가 정확히 절반으로 줄어들어 (14, 14)가 되었습니다. 만약 스트라이드를 기본값으로 사용한다면 (28, 28) 크기의 특성맵으로 입력과 동일해질겁니다.

풀링층(Pooling layer)

# 풀링 윈도를 각각 (2, 2), (3, 3) 크기로 만듭니다.
pool1 = layers.AveragePooling2D(pool_size=(2, 2))
pool2 = layers.AveragePooling2D(pool_size=(3, 3))

# 만들어진 풀링 윈도로 원본 데이터를 평균 풀링합니다.
# (28, 28)크기를 (2, 2)로 절삭해 압축하니 (14, 14) 크기로 변환됐습니다.
print(pool1(x).shape) # (10, 14, 14, 1)
# (28, 28)크기를 (3, 3)로 절삭해 압축하니 (9, 9) 크기로 변환됐습니다.
print(pool2(x).shape) # (10, 9, 9, 1)

풀링을 통해 원본(28, 28)을 축소(압축)하니 풀링 윈도가 (2, 2)일 땐 절반 크기인 (14, 14)로, (3, 3)일 땐 (9, 9)로 압축됐습니다. 기본적으로 풀링 윈도에 딱 맞지 않는 짜투리 부분은 버려집니다.

밀집층(Dense layer)

# 뉴런이 3개짜리인 밀집층을 만듭니다.
dense1 = layers.Dense(3)

# 2개짜리 입력 특성을 만듭니다.
# 2차원으로 입력값을 넘기는 이유는 케라스 층에 전달되는 입력의 첫 번째 차원은
# 항상 배치 차원, 즉 데이터 묶음이여야 하기 때문에 입력값의 크기를 (2)이 아닌 (1,2)인 2차원 배열로 만듭니다.
x2 = np.array([[5, 7]])

print(dense1(x2).shape) # (1, 3)

밀집층은 입력과 가중치의 점곱^{dot product}을 수행합니다. 점곱 연산은 다음과 같은 수식으로 나타낼 수 있습니다.

$$ y = x \cdot W + b $$

$$

\begin{bmatrix} 5 & 7 \end{bmatrix}

\cdot

\begin{bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \ \end{bmatrix}

+

\begin{bmatrix} 0 & 0 & 0 \end{bmatrix}

=

\begin{bmatrix} (51) + (74) & (52) + (75) & (53)+(76) \ \end{bmatrix}

\ = \left[\begin{matrix}33 & 45 & 57\end{matrix}\right] $$

결과값의 형태가 (3, 1)크기로 나오는 이유는 중간에 입력값에 곱하는 가중치, 커널의 크기가 (입력 크기, 유닛 개수)이기 때문입니다. 유닛은 각각의 입력값에 대해 가중치를 가져야 하며 이 가중치가 각 유닛 마다 갖고 있어야하기 때문에 가중치, 즉 커널의 크기(입력 크기, 유닛 개수)가 (2, 3)이 됩니다.

```python weight = dense1.get_weights()[0] print(np.dot(x2, weight)) # [[33. 45. 57.]]

문제

설명

자연수 중에서 n까지 소수의 개수를 반환하는 문제다.

전제 조건에 n의 값이 최대 $$5 * 10^6$$ 이므로 수 하나하나 약수가 있는지 나눠가면서 판별하면 Time Complexity가 O(N^2)으로 매우 높아지기에 에라토스테네스의 체라는 알고리즘을 사용해 문제를 해결하기로 했다.

에라토스테네스의 체

1. 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

2. 배열을 생성하여 초기화한다.

3. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)

4. 2부터 시작하여 남아있는 수를 모두 출력한다.

풀이

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    // 2부터 n까지 숫자를 담을 배열
      let nums = [];
    let cnt = 0;

      // 배열에 2번 인덱스부터 n번 인덱스까지 초기값을 1로 설정(1이면 소수)
    for(let i = 2; i <= n; i++){
        nums[i] = 1;
    }

       /* 
     * n의 제곱근까지만 판별하는 이유는 어떤 수의 소수의 여부를 확인 할 때는, 
     * 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 
     * 빠르게 구할 수 있다.
     */
    for(let i = 2; i < Math.sqrt(n); i++){
          // 자기 자신을 제외한 배수를 소수에서 제외한다.
        for(let j = i*i; j < n; j += i){
            nums[j] = 0;
        }
    }

      // 소수로 남은 숫자의 개수를 센다
    for(let i = 2; i < n; i++){
        if(nums[i] === 1) ++cnt;
    }

    return cnt;
};

Reference

• [Algorithm] 에라토스테네스의 체 - Junseo Kim
• 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

문제

설명

이진 트리의 root가 주어지고 트리가 Binary Search Tree(이하 BST)인지 검증하는 문제다.

BST가 되기 위해선 3가지 조건이 있는데

• 부모 노드의 왼쪽 자식 노드는 부모 노드보다 작아야 한다.
• 부모 노드의 오른쪽 자식 노드는 부모 노드보다 커야 한다.
• 양쪽 서브 트리들은 위 두 가지 성질을 만족해야 한다.

추가적으로 문제에 전제조건이 있는데

• 트리에 있는 노드의 개수는 [$$1$$, $$10^4$$] 개다.
• 노드의 값은 [$$-2^{31}$$, $$2^{31}-1$$]이다.

풀이

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root, min = -Infinity, max = Infinity) {

    if(!root) return true;

    if(root.val <= min || root.val >= max) return false;

    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);

};

재귀적으로 서브 트리에 있는 자식 노드를 호출하며 중간에 부모 노드보다 큰 left node 혹은 작은 right node가 있는지 검사한다.

가장 밑에 있는 노드까지 검사하면서 부모 노드보다 큰 left node 또는 작은 right node가 발견되지 않을 경우 true를 반환하고, 발견될 경우 false를 반환한다.

이렇게 재귀적으로 검사한 값은 최종적으로 root node로 돌아가는데 이때 왼쪽 노드들 중에서 검사한 값이랑 오른쪽 노드들에서 검사한 값이 둘다 true일 경우에만 true를 반환하고 이외에는 false를 반환한다.

문제

설명

이진 트리의 루트를 받아 해당 트리의 가장 깊은 깊이(depth)를 반환하면 된다.

트리의 최고 깊이를 찾는 문제니까 DFS를 이용해서 문제를 풀었는데 DFS는 스택 또는 재귀함수로 구현할 수 있다.

나는 스택보단 재귀함수가 좀 더 보기 편해서 재귀함수로 구현했다.

풀이

var DFS = (node, depth) => {
    // 탐색할 노드가 없으면 lev를 반환
    if(!node) return depth;

    // 왼쪽, 오른쪽 순으로 순회하며 탐색
    let left = DFS(node.left, depth + 1);
    let right = DFS(node.right, depth + 1);

    return Math.max(left, right);
}
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    return DFS(root, 0);
};

root node(3)에서 시작:

if(!node) return depth

1. 빈 노드가 이니기 때문에 계속 진행한다.

let left = DFS(node.left , depth + 1);

2. 왼쪽 노드(9) 호출.

child node(9) 호출:

if(!node) return depth

1. 빈 노드가 아니니까 패스

   let left = DFS(node.left , depth + 1);

2. 왼쪽 노드를 호출하지만, 빈 노드여서 현재 depth인 1 반환.

   let right = DFS(node.right , depth + 1);

3. 오른쪽 노드 역시 빈 노드여서 1 반환.

root node(3)으로 돌아가기:

1. 왼쪽 노드 탐색 후 오른쪽 노트 탐색

   let right = DFS(node.right , depth + 1);

child node(20) 호출:

1. 빈 노드가 아니니까 패스
2. 왼쪽 노드 15 호출

child node(15) 호출:

1. 자식 노드가 없으니 depth = 2 반환.

child node(20)으로 돌아가기:

1. 오른쪽 노드 7 호출

child node(7) 호출:

1. 자식 노드가 없으니 depth = 2 반환.

child node(20)으로 돌아가기:

return Math.max(left, right);

1. 노드 20의 왼쪽 노드 13, 오른쪽 노드 7의 깊이를 비교해서 더 큰 값을 반환.

   root node(3)으로 돌아가기:

   let left = DFS(node.left, depth + 1);
   let right = DFS(node.right, depth + 1);
   

return Math.max(left, right);

1. left는 `1`, right는 `2`이므로 둘 중 더 큰 수인 `right = 2` 를 반환.

문제

💬 설명

구(phrase)를 거꾸로 읽어도 제대로 읽은 것과 같은걸 회문(palindrome)이라 한다. 이 문제는 어떠한 구가 주어지면 그 구가 회문인지 아닌지를 판별하면 되는 문제다.

📜 풀이

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let reg = /[^a-zA-Z|0-9]/gim;
    s = s.replace(reg, '').toLowerCase();

    let l = 0, r = s.length - 1;

    while(l < r){
        if(s[l] !== s[r]) return false;
        l++; r--;
    }

    return true;
};

구에서 불필요한 특수문자나 공백을 지우고 모든 문자를 소문자로 바꿔서 앞뒤로 서로 같은지 판별하면 된다. /[^a-zA-Z|0-9]/gim 는 영문, 숫자를 제외한 모든 문자를 찾는 정규식이다.

🔎 패턴

매칭하여 검색하고 싶은 문자열을 지정한다. 기존처럼 문자열의 따옴표를 포함해서 선언하면 따옴표까지도 검색하기 때문에 따옴표는 생략한다.

정규 표현식 패턴을 작성할 때는 일반 문자와 특수 문자를 사용할 수 있는데, 일반 문자는 리터럴 문자 / 특수 문자는 메타 문자로 표현한다.

리터럴 문자 (정규 문자) : 일반 문자, \0, \n, \t, \v, \f, \r, \xhh, \uhhhh, \cX 메타 문자 (정규 표현식의 구문 문자) : ^ $ \ . * + ? ( ) [ ] { } |_

🔎 플래그

플래그는 정규 표현식의 옵션이므로 선택적으로 사용이 가능하다. 순서와 상관없이 하나 이상의 플래그를 동시에 설정할 수 있다. 플래그를 사용하지 않는 경우에는 문자열 내 검색 대상이 1개 이상이더라도 첫번째 조건 대상만을 검색하고 종료하게 된다.

🚩 대표적인 플래그 i (ignore case) : 대소문자를 구별하지 않고 검색한다. g (global) : 문자열 내의 모든 패턴을 검색한다. m (multi line) : 문자열의 행이 바뀌더라도 검색은 계속한다.

🔗 References

Javascript에서 정규표현식(Regular Expression) 사용하기

인터넷이란, 컴퓨터들이 서로 통신 가능한 거대한 네트워크로

인터넷의 초기 형태이였던 ARPANET은 냉전 중 1969년에 미 국방부 고등연구계획국(ARPA)에서 컴퓨터가 먼 거리에서 서로 통신할 수 있는 네트워크를 구축하는 것을 목표로 ARPANET이라는 프로젝트를 시작했다.

군사 및 연구 목적으로 사용되었던 ARPANET이 1980년대에 임무를 완수하고 단계적으로 폐지되면서 연구 목적으로 사용되다 규모가 커지고 나서 이젠 모두가 사용하는 인터넷이 되었다.

단순 네트워크

1:1 연결

기본적으로 인터넷은 컴퓨터들이 서로 물리적으로(이더넷 케이블 등) 또는 무선으로 연결되어 두 대 이상의 컴퓨터가 데이터를 주고 받는것이다.

모든 현대 컴퓨터들은 이러한 연결 중 하나를 이용하여 데이터를 주고 받는다.

하지만 아래와 같이 인터넷은 두 대의 컴퓨터가 연결되어 있는 것이 아니라, 무수히 많은 컴퓨터가 연결되어 있는데 모든 컴퓨터끼리 연결을 하기엔 매우 복잡해진다. 예를 들어 컴퓨터 10대가 있는 네트워크를 구성하려면 $10(10-1)/2 = 45$개의 케이블이 필요하다.

이러한 문제점을 해결하기 위해 우리는 라우터라는 특수한 소형 컴퓨터를 사용하는데 이 라우터라는 소형 컴퓨터는 한 가지 작업만 하게 설계되어있다. 철도역의 신호원처럼 주어진 컴퓨터에서 보낸 메시지가 올바른 대상 컴퓨터에 도착하는지 확인한다. 컴퓨터 A가 컴퓨터 B에게 메시지를 보내기 위해선 라우터에 메시지를 보내고 라우터는 받은 메시지를 수신자인 컴퓨터 B에게 전달해야한다. 또한 다른 컴퓨터로 송신되지 않게 해야한다.

라우터를 설치하니 모든 컴퓨터끼리 케이블을 연결했을 때와 다르게 각 컴퓨터를 라우터에 연결하면 되니 케이블을 10개만 사용해도 된다.

네트워크 속 네트워크

라우터를 사용해 여러 대의 컴퓨터를 수용할 수 있게 됐지만, 아직 라우터 하나론 더 많은 컴퓨터를 수용하기엔 라우터의 플러그 수도 제한되어있다. 이런 문제를 해결하기 위해 라우터도 컴퓨터와 마찬가지로 라우터끼리 연결할 수 있다.

컴퓨터와 라우터를 연결하고 라우터와 라우터를 연결해 무한하게 네트워크를 확장할 수 있다.

이 네트워크는 우리가 인터넷이라 부르는 것과 매우 유사하다.

상대적으로 적은 케이블로 많은 컴퓨터를 연결이 가능하다. 하지만 아직까진 물리적인 한계가 있다. 만약 내가 아주 먼 곳까지 네트워크를 연결하고 싶은데 그곳까지 라우터와 유선 케이블을 연결하기엔 무리가 있다.

하지만 우리는 집집마다 전화선이라는 케이블이 설치되있다. 전화기 기반의 시설은 이미 세계 어느 곳과도 연결되어 있으므로 우리가 필요로 하는 완벽한 배선이니 전화선을 이용하면 된다. 우리는 네트워크와 전화 시설을 연결하기 위해 모뎀(MODEM, Modulator and DEModulator)이라는 특수 장비가 필요하다.

이 모뎀은 우리 네트워크의 정보를 전화 시설에서 처리 할 수있는 정보로 바꾸며, 그 반대의 경우도 마찬가지로 네트워크에서 처리할 수 있는 정보로 바꿔준다.
모뎀을 통해 우리의 네트워크는 전화 시설에 연결된다.

그리고 우리의 네트워크에서 도달하려는 네트워크에 메시지를 보내야 한다.

이 메시지가 전달되려면 인터넷 서비스 제공 업체(ISP, Internet Service Provider)에 연결되어야 한다.

ISP는 모두 함께 연결되는 몇몇 특수한 라우터를 관리하고 다른 ISP의 라우터에도 액세스 할 수 있는 회사이다. 우리나라에는 SKT, KT, LG 등이 있다.

따라서 우리 네트워크의 메시지는 ISP 네트워크의 네트워크를 통해 대상 네트워크로 전달된다.

컴퓨터 찾기

컴퓨터에 메시지를 보내려면 메시지를 받을 특정 컴퓨터를 지정해야합니다. 따라서 네트워크에 연결된 모든 컴퓨터에는 IP 주소 (IP는 인터넷 프로토콜을 나타냄)라는 고유한 주소가 있고, 주소는 점으로 구분 된 네 개의 숫자로 구성된 주소로 되어있다. 예: 192.168.2.10.

컴퓨터는 이러한 주소로 다른 컴퓨터를 찾아가는데 문제가 없지만, 우리들은 IP주소를 기억하기 어려우니 도메인 이름 이라고하는 사람이 읽을 수 있는 IP 주소의 이름을 지정할 수 있다.

예를 들어 google.com은 IP 주소로 173.194.121.32 입니다. 따라서 도메인 이름은 IP주소보다 인터넷을 사용하기에 쉽다.

인터넷과 웹

웹 브라우저를 사용하여 웹을 탐색 할 때 일반적으로 도메인 이름을 사용하여 웹 사이트에 접속하는데, 이게 인터넷과 웹이 같은 것을 의미하진 않는다.

앞에서 보았듯이 인터넷은 수십억 대의 컴퓨터를 모두 연결하는 기술 인프라이다. 이러한 컴퓨터들 중에 일부는 웹 서버로서 웹 브라우저가 이해할 수 있는 서비스를 제공한다. 인터넷은 인프라이며, 웹은 그 인프라 기반 위에 구축된 서비스입니다. 웹 뿐만 아니라 인터넷 위에 구축된 다른 서비스들(이메일, IRC 등)도 있음을 알아야한다.

DNS 설명

실제 웹 주소는 멋지거나, 여러분이 선호하는 웹사이트를 찾기 위한 주소 막대에 입력하는 기억할만한 문자가 아닙니다. 그것은 63.245.217.105 같은 숫자 덩어리로, 이런 주소를 IP주소라 한다.

웹의 하나뿐인 특정 위치를 나타냅니다. 그러나 기억하기에 쉽지는 않은 형태여서 사람이 쉽게 기억할 수 있는 문자열 형태의 도메인 이름 서버가 발명되었다. 도메인 이름 서버는 여러분이 브라우저에 입력하는 웹주소 mozilla.org 같은 웹사이트의 실제 (IP) 주소에 맞춰주는 특별한 서버이다.

웹사이트는 그들의 IP 주소를 통해 직접 접근할 수도 있다. IP Checker와 같은 도구에 도메인을 입력해 IP 주소를 찾을 수 있습니다.

패킷과 프로토콜

우리가 전송하는 데이터로는 텍스트, 이미지 등이 있는데, 통째로 전송하지 않고 작게 나눠서 보낸다.

이 작게 나눈 데이터 조각을 패킷이라고 한다. 전송되는 패킷은 전자 신호로 변환되어 이더넷 케이블이라는 전선을 먼저 통과해야 한다.

전자 신호는 0과 1로 이루어져 있고, 이 신호를 다른 컴퓨터에 전송하면 다시 원래의 데이터로 변환해야 하는데, 아무런 양식 없이 전송하면 다른 컴퓨터가 이 데이터가 텍스트인지 이미지인지 어떻게 변환해야 하는지 알 수 없다.

따라서 데이터를 전송하는 특정 양식(통신 규약)을 정해놓았는데, 이것을 프로토콜이라고 한다.

프로토콜은 장치마다 처리하는 역할마다 다양하다. 프로토콜을 각 역할로 구분하여 계층을 나눠놓은 것을 TCP/IP 4 Layer라고 한다. 이렇게 구분해 놓으면 서로 간에 간섭을 최소화하여 편리성을 높일 수 있다.

L4 - 응용(Applicaiton) 계층 (HTTP, FTP, SMTP 등) 웹(HTTP), 이메일(SMTP), 파일전송(FTP) 같은 응용프로그램을 위한 프로토콜

L3 - 전송(Transport) 계층 (TCP) 응용프로그램을 구분하는 포트 번호를 통해 컴퓨터에서 돌아가는 프로그램들 중 특정 응용 프로그램 하나를 찾아감

L2 - 인터넷(Internet) 계층 (IP) IP 주소를 통해 수많은 컴퓨터들 중 특정 컴퓨터 하나를 찾아감

L1 - 네트워크 연결(Network Accesss) 계층 전선과 장비들을 통해 물리적으로 데이터 전송하기 위해 적절한 디지털/아날로그 신호 등등으로 변환함

이러한 4개의 계층을 합쳐 TCP/IP 4계층이라고도 한다.

응용 프로그램에서 데이터를 전송하면 각 프로토콜에 따라 패킷이 만들어지고, 아래 계층으로 내려가며 각 계층의 프로토콜에 따라 해석되거나 다른 정보가 덧붙여져 그 아래 계층으로 내려간다.

네트워크 연결 계층까지 오면 전선과 장치들을 통해 인터넷으로 전송되고, 아래 계층부터 위 계층까지 차례대로 거쳐 프로토콜에 의해 원본 데이터에 해석된다.

이러한 구분을 통해 서로 간에 간섭이 최소화되어 편하지만, 응용 계층에서는 응용 프로그램끼리의 해석만 신경 쓰면 되고 그 밑에 이 응용 프로그램을 어떻게 찾아오는지, 컴퓨터를 어떻게 찾아가는지, 디지털/아날로그 신호로 어떻게 바꾸는지 신경 쓰지 않아도 되기 때문이다.

✏️Reference

• https://developer.mozilla.org/ko/docs/Learn/Common_questions/Web_mechanics/How_does_the_Internet_work#%EB%8B%A4%EC%9D%8C_%EB%8B%A8%EA%B3%84
• https://gyunny.tistory.com/2#

문제

설명

정수형 배열 nums에서 유일한 수를 반환하면 된다.

풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let uniqueNum = 0;

    for(let i = 0; i < nums.length; i++){
        uniqueNum ^= nums[i];
    }

    return uniqueNum;
};

XOR연산을 이용한 풀이이다. 조건에서 Each element in the array appears twice except for one element which appears only once. 각 요소는 한 번만 나타나는 요소를 제외하고 두 번 나타난다는 것을 알 수 있다. 1 ^ 1 = 0001(2) ^ 0001(2) = 0000(0) 같은 수를 두 번 xor 연산하면 0이 나오는 것을 이용해 고유한 수를 찾을 수 있다.

Example 1:
i: 0, unique: 0000(0) ^ 0010(2) = 0010(2)
i: 1, unique: 0010(2) ^ 0010(2) = 0000(0)
i: 2, unique: 0000(1) ^ 0001(1) = 0001(1)

// output: 1

----------------------------------------------------

Example 2:
i: 0, unique: 0000(0) ^ 0100(4) = 0100(4)
i: 1, unique: 0100(4) ^ 0001(1) = 0101(5)
i: 2, unique: 0101(5) ^ 0010(2) = 0111(7)
i: 3, unique: 0111(7) ^ 0001(1) = 0110(6)
i: 4, unique: 0110(6) ^ 0010(2) = 0100(4)

// output 4

위의 연산 과정을 보면 같은 수를 두 번 XOR 연산하게 되면 0으로 무산되는 것을 알 수 있다.

문제

설명

정수형 배열 nums을 k번 오른쪽으로 회전시키면 되는 문제다.

풀이

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    if(nums.length === 1) return;
    if(k === 0) return;

    let arr = JSON.parse(JSON.stringify(nums));
    let temp = k % arr.length;

    let idx = arr.length - temp;
    for(let i = 0; i < arr.length; i++){
        nums[i] = arr[(idx+i) % arr.length];
    }
};

그냥 원소를 한 칸씩 밀기엔 시간복잡도가 O(nums.length * k) 이 되기 때문에 원본 배열을 복사해두고 k가 nums.length보다 클 경우 (k % nums.length)번 회전한 결과와 같기에 k는 nums.length로 나눈 나머지로 바꿨다. Example 1와 Example 2를 보면 output이 원본 배열의 nums.length - k번째부터 하나씩 넣은 결과와 같이 때문에 이 점에 초점을 두고 nums의 원소를 변경했다. arr를 참조하면서 IndexOutOfBoundsException가 일어나지 않게 arr.length로 나눈 나머지를 넣었다.

문제

설명

정수형 배열 heights가 주어지고 heights를 오름차순으로 정렬한 배열과 비교했을때 일치하지 않은 횟수 반환하면 됨.

풀이

/**
 * @param {number[]} heights
 * @return {number}
 */
var heightChecker = function(heights) {

    // 배열 복사(그냥 대입하면 얕은 복사가 되기에 깊은 복사로 넣는다.) 및 오름차순 정렬
    let sortedArr = [...heights].sort((a,b) => (a-b));

    // 비교
    let cnt = 0;

    for(let i = 0; i < heights.length; i++){
        if(heights[i] !== sortedArr[i]) cnt++;
    }

    return cnt;
};

문제

설명

정수형 배열 nums이 주어지고 In-place를 활용해 각각 고유한 원소만 있는 배열로 수정 후 배열의 길이를 반환하면 된다.

풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
      // 1개짜리 배열은 바로 리턴
    if(nums.length === 1) return 1;

      // 기준이 될 pointer1과 비교할 pointer2를 선언
    let pointer1 = 0, pointer2;
    for(let i = 1; i < nums.length; i++){
        pointer2 = i;

          // 원소 검사 중 중복되지 않는 원소가 나오면
        if(nums[pointer1] !== nums[pointer2]){
              /*
             * 기준이 되던 nums[pointer1]의 바로 뒤 원소를 nums[pointer2]로
             * 바꾼 후 pointer1를 한 칸 뒤로 변경
             */
            nums[pointer1 + 1] = nums[pointer2];
            ++pointer1;
        }
    }

    nums.length = pointer1 + 1;

    return nums.length;
};

문제

설명

감소되지 않는 두 정수형 배열 nums1, nums2와 정수 m, n이 주어진다. 두 정수형 배열을 0을 제외한 나머지 값들만 병합해서 nums1에 저장하면 된다. m은 nums1의 병합되어야 하는 원소의 개수고, n은 무시해야 하는 0의 개수이고, nums2의 길이이기도 하다.

풀이

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
      /**
     * nums1의 m번째부터 0으로 n개 채워져있으니
     * 그 부분을 nums2의 원소로 변경한다.
     */
    for(let i = 0; i < n; i++){
        nums1[m+i] = nums2[i];
    }

      // 이후 배열을 오름차순으로 정렬한다.
    nums1.sort((a,b) => (a-b));
};

문제

설명

정수형 배열이 주어지고 arr[i]의 값을 arr[i+1] ~ arr[arr.length] 까지의 값 중에서 가장 큰 수로 바꿔주면 된다. 가장 마지막에 있는 원소는 -1로 바꿔주면 된다.

풀이

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var replaceElements = function(arr) {
      // 배열 원소가 하나인 경우
    if(arr.length == 1) arr[0] = -1;

    for(let i = 0; i < arr.length; i++){
        // 마지막 원소는 -1로 고정
          if(i === arr.length-1) {
            arr[i] = -1;
            break;
        }

        let max = 0;
        // arr[i]보다 뒤에 있는 원소 값 중 최고값 찾기
        for(let j = i + 1; j < arr.length; j++){
            if(max < arr[j]) max = arr[j];
        }

        arr[i] = max;
    }

    return arr;
};
```![](https://velog.velcdn.com/images/j_zero/post/341195b2-6096-4e1b-a883-7f4b702fe56a/image.png)

난이도: Easy

문제

설명

길이가 고정된 정수형 배열이 주어진다. 원소 중에 0이 있으면 해당 원소 뒤에 0을 삽입하면 된다.

풀이

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
var duplicateZeros = function(arr) {
    let temp = [];

    for(let i = 0; i < arr.length; i++){
        temp.push(arr[i]);
        if(arr[i] == 0) temp.push(0);
    }

    for(let i = 0; i < arr.length; i++){
        arr[i] = temp[i];
    }
};

원소 0뒤에 추가로 0을 넣은 배열 temp를 생성하고 기존 배열 arr의 길이만큼 temp를 잘라서 넣는다.

난이도: Easy

문제

설명

정수로 된 감소되지 않는 배열이 주어지는데 이 배열의 요소들을 제곱한 후 오름차순으로 정렬하면 된다.

풀이

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {

    for(let i = 0; i < nums.length; i++){
        nums[i] = nums[i] * nums[i];
    }

    nums.sort((a,b) => (a - b));
    return nums;
};

각 배열의 원소를 제곱한 후 sort 메서드로 오름차순 정렬했다. sort안의 콜백함수의 리턴이 1이면 a,b를 서로 교환하고, -1이면 넘어간다.

난이도: Easy

문제해설

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote.

해답

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    for(const char of magazine){
        ransomNote = ransomNote.replace(char, "");
    }

    if(ransomNote === '') return true;
    else return false;
};

난이도: Easy

문제해설

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

해답

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let listLength = 0;
    let pointer = head; // Linked List 포인터

      // head의 Node개수 세기
    while(pointer.next != null){
        pointer = pointer.next;
        ++listLength;
    }

    pointer = head;
    // list의 중간지점으로 이동    
      for(let i = 0; i < listLength / 2; i++){
        pointer = pointer.next;
    }

    return pointer;
};

난이도: Easy

문제해설

Given an integer n, return a string array answer (1-indexed) where:

• answer[i] == "FizzBuzz" if i is divisible by 3 and 5.
• answer[i] == "Fizz" if i is divisible by 3.
• answer[i] == "Buzz" if i is divisible by 5.
• answer[i] == i (as a string) if none of the above conditions are true.

정답

/**
 * @param {number} n
 * @return {string[]}
 */
var fizzBuzz = function(n) {
    let arr = [];

    for(let i = 1; i <=n; i++){
        if(i % 15 == 0) {
            arr[i-1] = "FizzBuzz";
        }
        else if(i % 3 == 0){
            arr[i] = "Fizz";
        }
        else if(i % 5 == 0){
            arr[i] = "Buzz";
        }
        else{
            arr[i] = i.toString();
        }
    }

    arr.shift();
    return arr;
};

난이도: Easy

문제해설

You are given an m x n integer grid accounts where accounts[i][j] is the amount of money the ith customer has in the jth bank. Return the wealth that the richest customer has. A customer's wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.

정답

/**
 * @param {number[][]} accounts
 * @return {number}
 */
var maximumWealth = function(accounts) {
    let row = accounts.length;
    let col = accounts[0].length;
    let max = 0;
    for(let i = 0; i < row; i++){
        let temp = 0;
        for(let j = 0; j < col; j++){
            temp += accounts[i][j];
            if(max < temp) max = temp;
        }
    }

    return max;
};

난이도: Easy

문제 설명

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]). Return the running sum of nums.

해설

배열 nums가 입력되고 새로운 배열 runningSum을 만드는데 runningSum의 i번째 요소가 sum(nums[0]...nums[i])여야 한다. 구한 runningSum을 반환하면 된다.

정답

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var runningSum = function(nums) {
    let arr = []
    let sum = 0;
    for(let i = 0; i < nums.length; i++){
        sum += nums[i];
        arr.push(sum);
    }

    return arr;
};

난이도: Easy

문제 설명

Given an integer num, return the number of steps to reduce it to zero. In one step, if the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

해석

정수 $$num$$ $$(0 <= num <= 10^6$$)이 입력된다. 정수가 짝수면 2로 나누고 홀수면 1로 빼야한다. 정수 $$num$$이 0이 될 때까지 걸린 연산의 횟수를 반환해라.

정답

/**
 * @param {number} num
 * @return {number}
 */
var numberOfSteps = function(num) {
    let answer = 0;

    while(num != 0){
        if(num % 2 === 0) num /= 2;
        else num -= 1;

        ++answer;
    }

    return answer;
};