‘하루 3분 네트워크 교실(아미노 에이지, 김현주, 영진닷컴)’ 참조

10. TCP / IP 모델

• (의미) 데이터 통신이 진행되는 단계와 순서에 대해 정의한 규약
• (TCP/IP 프로토콜 군) OSI 프로토콜을 대신하여 인터넷에서 가장 많이 사용되는 프로토콜 군으로 사실표준(De Facto Standard)에 해당함
• (배경) IETF(the Internet Engineering Task Force)라는 단체가 RFC(Request For Comments)라는 문서에 의해 제정함
• (내용)

'하루 3분 네트워크 교실(아미노 에이지, 김현주, 영진닷컴' 참조

9. 프로토콜

개념

• (의미) 컴퓨터 내부 또는 컴퓨터 사이에서 데이터를 교환하는 방식에 관한 규칙
• (계층 별 프로토콜 관계) 상위 계층 프로토콜이 하위 계층 프로토콜을 이용할 수 있고, 하위 계층은 상위 계층 프로토콜에 데이터를 전송할 수 있는 구조를 가지며 이러한 연결 구조를 인터페이스라고 함
• (프로토콜 군) 인터페이스에 의해 각 계층별로 연결된 프로토콜을 통합한 것을 프로토콜 군(Protocol Suite)이라고 함

프로토콜 결정 사항

• (데이터 내용) 프로토콜은 송수신하는 데이터에 관하여 ‘명령을 쓰는 법', ‘파일명', 사용하는 ‘문자 코드’ 등을 정의함
• (헤더) 프로토콜이 속한 계층의 기능을 수행하기 위해 송수신처 주소, 코드, 등을 나타내는 헤더를 결정함
• (데이터 송수신 순서) 데이터를 보내는 순서, 데이터 내용, 데이터 수신 후 처리 순서, 등을 프로토콜이 결정함

'파이썬 알고리즘 인터뷰(박상길, 책만)' 참조

해시 테이블

1. (문제) 중복 문자 없는 가장 긴 부분 문자열(리트코드 3)

- 문제: 중복 문자가 없는 가장 긴 부분 문자열(Substring)의 길이를 리턴하라

  - Input: s = "abcabcbb"
  - Output: 3
  - Explanation: The answer is "abc", with the length of 3.

문자열 내에서 중복이 없고, 길이가 가장 긴 부분 문자열을 출력하는 문제다.

s = ‘abcabcbb’ 일 때,

중복이 없고 가장 긴 문자열은 ‘abc’이므로,

부분문자열의 최대 길이는 3이다.

2. (풀이) 슬라이딩 윈도우와 투 포인터로 윈도우 크기 조정

우선, 문제의 풀이 과정을 그림으로 표현하겠다.

우선 투 포인터 left와 right를 모두 인덱스 0에 지정한다.

for 반복문으로 right 포인터를 한 칸씩 이동 시키면서, 부분 문자열의 중복 여부를 판단하고,

부분 문자열의 최대 길이를 업데이트한다.

위에 빨간선은 left와 right 포인터가 가리키는 범위(윈도우)이며,

윈도우 크기는 최대 3으로 ‘abc’, ‘bca’, ‘cab’ ‘abc’ 순서로 위치는 바뀌지만 크기는 모두 동일하다.

1) (해시 테이블) 생성 및 ‘key:value’ 삽입

우선, for 반복문으로 right 포인터를 오른쪽으로 한 칸씩 이동하면서 해시 테이블(used)에 포인터가 가리키는 값(char, 해시 맵 key)과 위치(right, 해시 맵 value)를 담는다.

# 해시 테이블 생성
used = {}

for right, char in enumerate(s):


        '''       

        # 해시테이블 상 현재 문자(key)에 인덱스(value) 삽입
        used[char] = right

2) (for 반복) 부분 문자열의 중복 여부 판단 and 최대 길이 업데이트

for right, char in enumerate(s):
            # 해시 테이블에 존재하는 문자의 경우 'left' 위치 업데이트
            # 'left' 위치가 업데이트 되는 경우 max_len 갱신 불필요
            if char in used and left <= used[char]:
                left = used[char] + 1

            else:
                # 문자의 최대 길이 업데이트
                max_len = max(max_len, right - left + 1)


            # 현재 문자에 인덱스 삽입
            used[char] = right

2)-1 for 반복문에서 right 포인터가 가리키는 문자열이 해시 테이블(used)에 포함 되어 있는지 여부를 판단한다.

만약 이미 해시 테이블에 포함된 문자열이라면 해당 윈도우 내에서 중복 문자열이 발생하기 때문이다.

따라서, left포인터를 ‘해시 테이블에 든 문자열의 위치 + 1 ‘로 이동시킨다면 윈도우 내에서 중복 문자가 제외된다.

2)-2 반면, for 반복문에서 right 포인터가 가리키는 문자열이 해시 테이블에 포함되어 있지 않다면,

해당 부분 문자열은 중복이 없으므로 길이를 구한다. 이전에 구한 최대 길이(max_len) 보다 더 크다면 새로 구한 길이로 ‘max_len’을 업데이트한다. for 반복 연산을 마친 후, ‘max_len’을 리턴하여 최대 길이를 출력하면 된다.

3. 전체 코드

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        # 해시 테이블 생성
        used = {}

        left = 0
        max_len = 0

        for right, char in enumerate(s):
            # 해시 테이블에 존재하는 문자의 경우 'left' 위치 업데이트
            # 'left' 위치가 업데이트 되는 경우 max_len 갱신 불필요
            if char in used and left <= used[char]:
                left = used[char] + 1

            else:
                # 문자의 최대 길이 업데이트
                max_len = max(max_len, right - left + 1)


            # 현재 문자에 인덱스 삽입
            used[char] = right

        return max_len

'파이썬 알고리즘 인터뷰(박상길, 책만) 참조'

문제 26. 원형 데크 디자인

1. 데크의 개념

데크(Deque) 자료형을 구현하는 문제다.

데크는 더블 엔디드 큐(Doble-Ended Queue)의 줄임말로, 양쪽 끝에서 큐 연산을 진행할 수 있는, 추상 자료형(ADT)이다.

데크는 이중 연결 리스트(Double Linked List)로 구현할 수 있다.

데크는 ‘head’와 ‘tail’ 두개의 포인터를 가지고 있으며,

새로운 아이템이 추가되면 앞쪽, 또는 뒤쪽으로 연결시켜주면 된다.

2. 문제 - 원형 데크 디자인(리트코드 641)

MyCircularDeque(int k) Initializes the deque with a maximum size of k.
    boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.
    boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.
    boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.
    boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.
    int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.
    int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.
    boolean isEmpty() Returns true if the deque is empty, or false otherwise.
    boolean isFull() Returns true if the deque is full, or false otherwise.

위에서 제시한 데크의 함수를 구현하는 문제다

우선 데크의 맨 앞과 맨뒤에 요소를 추가하는 함수(insertFront() & insertLast())가 있다.

동시에 요소를 제거하는 함수(deleteFront() & deleteLast())도 구현한다.

요소의 추가 및 제거를 위해 별도의 함수(_add() & _del())를 구현할 예정이다.

데크의 맨 앞과 맨 뒤의 값을 조회하는 getFront(), getRear() 함수를 만들고,

마지막으로 데크가 비었는지 또는 가득 찼는지 여부를 판단하는 isEmpty(), isFull()함수를 구현한다.

1. 초기화 함수

def __init__(self, k):
        """
        :type k: int
        """

        self.head, self.tail = ListNode(None), ListNode(None)
        self.k, self.len = k, 0
        self.head.right, self.tail.left = self.tail, self.head

초기화 함수의 입력값으로 데크의 길이를 나타내는 k를 설정한다.

먼저 앞서 말한 헤드와 테일 포인터를 빈 연결리스트(ListNode(None))로 생성한다.

또한 특정 시점의 데크 길이를 표현할 값(self.len)도 0으로 초기화 한다.

2. 삽입 함수

def _add(self, node, new):
        n = node.right
        node.right = new
        new.left, new.right = node, n
        n.left = new

def insertFront(self, value):
        """
        :type value: int
        :rtype: bool
        """

        if self.len == self.k:
            return False

        else:
            self.len += 1
            self._add(self.head, ListNode(value))

            return True   

def insertLast(self, value):
        """
        :type value: int
        :rtype: bool
        """

        if self.len == self.k:
            return False

        else:
            self.len += 1
            self._add(self.tail.left, ListNode(value))
            return True

삽입 함수의 구성은 간단하다.

우선, 데크의 길이가 전체 길이와 같으면 더 이상 삽입할 공간이 없으므로 False를 리턴한다.

삽입할 공간이 있으면 데크의 길이를 1만큼 증가시키고, _add() 함수를 호출하여 노드를 삽입한다.

앞 쪽 삽입(insertFront())의 경우 _add() 함수의 입력값으로 self.head가 들어가고,

뒤 쪽 삽입(insertLast())의 경우 self.tail.left가 들어가는 차이가 있다.

_add() 함수를 조금 더 살펴보자면,

입력값 노드와 본래 연결된 노드(함수에서 n으로 정의한다) 사이에 새로운 노드 new를 삽입하여 방식이다.

연산 과정은 아래 그림의 번호 순서대로 진행된다.

3. 제거 함수

def _del(self, node):
        n = node.right.right
        node.right = n
        n.left = node

def deleteFront(self):
        """
        :rtype: bool
        """

        if self.len == 0:
            return False

        else:
            self.len -= 1
            self._del(self.head)
            return True


    def deleteLast(self):
        """
        :rtype: bool
        """

        if self.len == 0:
            return False 

        else:
            self.len -= 1
            self._del(self.tail.left.left)
            return True

제거 함수의 구성도 삽입 함수와 크게 다르지 않다.

우선, 데크의 길이가 0이면 더 이상 제거할 값이 없으므로 False를 리턴한다.

제거할 값이 있다면 데크의 길이를 1만큼 줄이고 _del() 함수를 호출한다.

del() 함수에서, 입력값인 node와 오른쪽에 이어진 노드(n으로 정의된다) 간의 연결을 끊어 내기 위해서,

node를 n 오른쪽의 노드와 연결한다.

그림으로 나타내면 아래와 같다.

4. 나머지 및 전체 코드

삽입과 제거 함수를 제외하면 나머지 함수는 이해하기에 무리가 없다.

전체 코드는 아래와 같다.

class MyCircularDeque(object):

    def __init__(self, k):
        """
        :type k: int
        """

        self.head, self.tail = ListNode(None), ListNode(None)
        self.k, self.len = k, 0
        self.head.right, self.tail.left = self.tail, self.head


    def _add(self, node, new):
        n = node.right
        node.right = new
        new.left, new.right = node, n
        n.left = new

    def _del(self, node):
        n = node.right.right
        node.right = n
        n.left = node

    def insertFront(self, value):
        """
        :type value: int
        :rtype: bool
        """

        if self.len == self.k:
            return False

        else:
            self.len += 1
            self._add(self.head, ListNode(value))

            return True


    def insertLast(self, value):
        """
        :type value: int
        :rtype: bool
        """

        if self.len == self.k:
            return False

        else:
            self.len += 1
            self._add(self.tail.left, ListNode(value))
            return True

    def deleteFront(self):
        """
        :rtype: bool
        """

        if self.len == 0:
            return False

        else:
            self.len -= 1
            self._del(self.head)
            return True


    def deleteLast(self):
        """
        :rtype: bool
        """

        if self.len == 0:
            return False 

        else:
            self.len -= 1
            self._del(self.tail.left.left)
            return True



    def getFront(self):
        """
        :rtype: int
        """

        return self.head.right.val if self.len else -1


    def getRear(self):
        """
        :rtype: int
        """

        return self.tail.left.val if self.len else -1


    def isEmpty(self):
        """
        :rtype: bool
        """

        return self.len == 0


    def isFull(self):
        """
        :rtype: bool
        """

        return self.len == self.k

# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

'하루 3분 네트워크 교실(아미노 에이지, 김현주, 영진닷컴)' 참조

8. 캡슐화

• ( 데이터 통신의 흐름)
  • (순서) 수신자는 OSI 7계층 → 1계층으로, 송신자는 1계층 → 7계층으로 데이터 통신 진행
  • (단계) 각 단계마다 통신에 필요한 정보(제어 데이터)를 추가할 수 있음
• (프로토콜 데이터 유닛) 데이터 전송을 위해 수신처 및 송신처의 주소, 등 데이터 외에 필요한 것들이 통합된 것을 프로토콜 데이터 유닛(Protocol Data Unit: PDU)이라고 함
• (캡슐화) 데이터에 제어정보를 덧붙여서 PDU로 완성하는 작업
  • (헤더, Header) 데이터 앞부분에 붙은 제어 데이터
  • (꼬리부, Trailer) 데이터 뒷부분에 붙은 제어 데이터
• (내용)

'하루 3분 네트워크 교실(아미노 에이지, 김현주, 영진닷컴)' 참조

7. OSI 참조 모델

• (배경) 국제표준화기구(ISO)가 통신과 프로토콜의 표준화를 시도하는 과정에서 OSI 탄생
• (용어) OSI 참조 모델(Open System Interconnection Reference Model)
• (의미) 데이터 통신을 단계로 나누어 각 단계의 순서를 명확히 하고 프로토콜을 정의
• (내용)

• (특징)
  • (계층) OSI 참조 모델은 7개의 계층(Layer)로 나뉨
  • (독립성) 각 계층은 독립성을 지님
  • (관계) 하위 계층은 상위 계층을 위해 일하고 상위 계층은 하위 계층에 관여하지 않음

'하루 3분 네트워크 교실(아미노 에이지, 김현주, 영진닷컴)' 참조

6. LAN과 WAN

• (네트워크의 범위 및 규모에 따른 분류) LAN(Local Area Network) 및 WAN(Wide Area Network)
• (LAN) 지역적으로 좁은 범위에서 본인 책임 하에 구축하는 네트워크
• (WAN) 넓은 범위에 걸친 지역의 LAN끼리 통신사업자의 통신 케이블을 빌려서 연결한 네트워크

'하루 3분 네트워크 교실(아미노 에이지, 김현주, 영진닷컴)' 참조

5. 네트워크의 구조

1) 멀티 엑세스 네트워크와 포인트 투 포인트 네트워크

• (통신에 필요한 기기) 네트워크 통신에는 컴퓨터, 인터페이스, 통신매체, 그리고 패킷 교환기인 라우터(Router)가 필요하다.
• (포인트 투 포인트 엑세스) 컴퓨터 한 대와 한 대가 연결되는 방식을 포인트 투 포인트 엑세스라고 한다.
• (멀티엑세스) 허브를 이용하여 여러대의 컴퓨터가 동시에 연결되는 구조를 멀티엑세스 네트워크라고 한다.
• (전체 네트워크) 구성 아래 그림과 같이 ‘멀티엑세스 네트워크'와 ‘포인트 투 포인트 네트워크’의 조합으로 구성된다.
•