---

Data Structure

List

Linked List

• 배열과 달리 크기를 바꿀 수 있는 자료구조

• 각 노드는 다음노드를 가르키는 포인터를 가짐

• 첫번째노드: 헤드(Head), 마지막 노드: 테일(Tail)

Double Linked List

• 각 노드는 다음노드와 이전노드를 가르키는 포인터를 가짐

Circle Linked List

• Head가 Tail을 물고있는 형태의 Linked List

Stack

• 먼저 들어간 요소가 나중에 나옴 (First-In, Last-Out: LIFO)

Queue

• 먼저 들어간 요소가 먼저 나옴 (First-In, First-Out: FIFO)

Circle Queue

Linked Queue

Tree

• 나무를 닮은 구조
• Root, Branch, Leaf로 이루어져 있음

  깊이(Depth): 루트노드에서 해당 노드까지의 경로의 길이

  레벨(Level): 같은 깊이를 가지는 노드의 집합

  높이(Height): “가장 깊은 곳”에 있는 잎노드까지의 깊이

차수(Degree): 자식 노드의 개수

트리의 차수: 트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수

이진트리(Binary Tree)

• 모든 노드가 최대 “2 개”의 자식을 가질 수 있는 트리

  포화 이진 트리(Full Binary Tree)

• 모든 노드가 대대손손이 자식을 둘씩 가지고 있는 이진 트리

  완전 이진 트리

• 잎 노드들이 트리의 왼쪽부터 차곡차곡 채워진 트리

  완전 높이 균형 트리(Completely Height Balanced Tree)

• 루트 노드를 기준으로 왼ㅉ고 하위 트리와 오른ㅉ고 하위 트리의 높이가 같은 이진트리

Priority Queue

• 우선순위 속성을 갖는 데이터를 다룸

Heap

• 힙 순서 속성(Heap Order Property)를 만족하는 완전 이진 트리
• 힙 순서 속성 : 트리 내의 모든 노드가 부모 노드보다 커야 한다는 규칙

Graph

인접 행렬 : 정점 끼리의 인접 관계를 나타내는 행렬

---

Introduction to Algorithm

알고리즘의 학습목표

Design(설계)

알고리즘 설계하는 기법

Analysis(분석)

• 알고리즘을 분석, 시간/공간 복잡도 구하기

Computational Complexity(계산복잡도)

• 문제를 분석하여 계산적 복잡도 구하기

알고리즘의 분석

시간복잡도(Time Complexity) 분석

• 입력 크기에 따라서 단위연산이 몇번 수행되는지 결정하는 절차(n)

표현 척도

입력크기(input size)

• 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리에서 마디와 이음선의 수, 그래프에서는 정점과 간선의 수

  단위연산(basic operation)

• 비교(comparison), 지정(assignment) 등 시간복잡도에 가장 크게 영향을 미치는 연산

분석 방법의 종류

• 모든경우 분석(Every-case analysis)
• 최악의 경우 분석(Worst-case analysis)
• 평균의 경우 분석(Average-case analysis)
• 최선의 경우 분석(Best-case analysis)

계산복잡도

Big O 표기법

정의 : 점근적 상한(Asymptotic Upper Bound)

차수의 주요 성질

복잡도 함수 순서

• lgn, n, nlgn, n², n^j, n^k, aⁿ, bnⁿ, n!
  k > j > 2, b > a > 1

---

선형 대수 (Linear Algebra)

스칼라 : 숫자(Magnitude)나 크기만 있고 방향을 갖지 않는 (키, 몸무게, 속력 등)

벡터 : 스칼라의 배열, 크기와 방향을 가진 값 (속도 등) 공간벡터, 위치벡터..

행렬 : 2차원의 배열

텐서 : 임의의 차원을 갖는 배열, 좌표 변환 등으로 사용

• 0차 텐서, 1차 텐서, 2차 텐서, 3차 텐서 등 *

---

네트워크 계층 구조

네트워크 계층 구조: 네트워크 계층

네트워크 계층 프로토콜: ARP (Address Resolution Protocol)

• 데이터를 전달하려는 IP 주소와 통신에 필요한 물리적인 주소(MAC)를 알아내는 프로토콜
• 선택된 매체에 브로드캐스트를 통해 특정 IP 주소를 사용하는 호스트가 응답을 하도록 요구하는 방식을 사용

---

네트워크 계층 프로토콜: IP (Internet Protocol)

• 가장 대표적인 네트워크 계층의 프로토콜
• 하위 계층의 서비스를 이용하여 두 노드 간의 데이터 전송 경로를 확립해주는 역할 (단말장치 간 패킨 전송 서비스)

IP (Internet Protocol)주소 체계

• 32자리 2진수로, 8자리마다 점을 찍어 구분
• A, B, C, D, E 클래스로 구분하는데 각 클래스는 네트워크 부분과 호스트 부분으로 구성
• A, B, C 클래스는 맨 앞부분에 시작하는 2진수 숫자에 따라 구분

IP (Internet Protocol)주소 분류

• 사설 네트워크: 사설 네트워크는 공인 네트워크 주소 부족 현상을 해결하기 위해 많이 사용

---

네트워크 계층 프로토콜: ICMP (Internet Control Message Protocol)

• 호스트 서버와 인터넷 게이트웨이 사이에서 메시지를 제어 및 오류를 알려주는 프로토콜
• 대표적인 툴은 ping

ICMP Echo Request 메시지

• 송신측의 전송 패킷이 목적이 노드나 라우터에 도착했는지를 확인하는 데 사용

네트워크 계층 프로토콜: IGMP (Internet Group Management Protocol)

• 멀티캐스트에 관여하는 프로토콜로 멀티캐스트 그룹을 관리하는 역할
• 유니캐스트(Unicast) - 일반적, 브로드캐스트(Broadcast), 멀티캐스트(Multicast) - 중간 / 효율높음
• IP 멀티캐스트 주소는 D 클래스 주소 대역(244.0.0.1 ~ 239.255.255.255)으로 규정

네트워크 계층 관련 장비: 라우터

• 네트워크의 대표적인 장비, 게이트웨이라고도 함
• 논리적으로 분리된 둘 이상의 네트워크를 연결
• 로컬 네트워크에서 브로드캐스트를 차단하여 네트워크를 분리
• 패킷이 목적지까지 가장 빠르게 보내는 길잡이 역할

정적 라우팅

• 관리자 권환으로 특정 경로를 통해서만 패킷이 지날 수 있도록 설정
• 네트워크 변경사항이 발생하면 라우팅 테이블을 수동으로 직접 고쳐야 함
• 보안이 중요한 경우 선호

동적 라우팅

• 라우터가 네트워크 연결 상태를 스스로 파악하여 최적의 경로를 선택해 전송
• 네트워크 연결 형태가 변경되어도 자동으로 문제를 해결

---

네트워크 계층 구조: 전송 계층

4계층: 전송 계층(Transport Layer)

• 프로토콜(TCP, UDP)과 관련된 계층으로 오류 복구와 흐름 제어 등을 담당, 두 시스템 간에 신뢰성 있는 데이터를 전송
• 네트워크 계층에서 온 데이터를 세션 계층의 어느 어플리케이션에 보낼 것인지 판독, 전송할 경로(Port, 포트)를 선택
• 네트워크 계층에서 전송한 데이터와 실제 운영체제의 프로그램이 연결되는 통신 경로라고 할 수 있음

• 대표 프로토콜은 TCP(Transmission Control Protocol)
• TCP가 가진 주소를 포트(Port)라 하며 0~65532(2¹⁶-1)번까지 존재
• -~1023번(1,024)d을 잘 알려진 포트(Well Known Port)라고 부름 (보통 0번 포트는 사용하지 않음)

포트 주소

• 수신지 컴퓨터까지 전송하려면 IP 주소와 물리 주소의 포트주소도 필요함!
• 인터넷 통신의 최종 목적은 한 프로세스가 다른 프로세스와 통신할 수 있도록 하는 것

• 즉 포트는 Tcp가 상위 계층으로 데이터를 전달하거나 상위 계층에서 TCP로 데이터를 전달할 때 상호 간에 사용하는 데이터의 이동 통로를 말함

전송 계층 프로토콜: TCP(Transmission Control Protocol)

• 연결 지항형 프로토콜
• IP와 함께 통신을 하는 데 반드시 필요한 가장 기본적인 프로토콜

TCP의 특징

• 높은 신뢰성
• 가상 회선 연결 방식
• 연결의 설정과 해제
• 데이터 체크섬
• 시간 초과와 재전송
• 데이터 흐름 제어

연결 설정 과정(Three-Way Handshaking)

연결 해제 과정

전송 계층 프로토콜: UDP(User Datagram Protocol)

• 비연결 지향형 프로토콜
• 상대방이 보낸 응답을 확인하지 않아 네트워크에 부하를 주지 않음
• 데이터 자체의 신뢰성이 없어 수신한 데이터의 무결성을 보장받지 못함

UDP의 특징

• 비연결 지향형
• 네트워크 부하 감소
• 비신뢰성
• 전송된 데이터의 일부가 손실됨

---

네트워크 계층 구조: 세션 계층

5계층: 세션 계층(Session Layer)

• 응용 프로그램 계층 사이의 접속을 설정 · 유지 · 종료시켜주는 역할
• 통신장치간의 설정을 유지하고 동기화 하는 역할

---

네트워크 계층 구조: 표현 계층

6계층: 표현 계층(Presentation Layer)

• 데이터 표현 차이를 해결하려고 서로 다른 형식으로 변환하거나 공통 형식을 제공하는 계층

---

네트워크 계층 구조: 응용 계층

7계층: 응용 계층(Application Layer)

• 여러가지 프로토콜에 대하여 사용자인터페이스를 제공

응용 계층(Application Layer) 관련 프로토콜들

FTP(File Transfer Protocol, 20,21)

• 파일 전송을 위한 가장 기본적인 프로토콜
• 1972 년 텔넷과 함께 표준으로 제정
• 클라이언트와 서버가 대화형으로 통신 가능

Telnet(텔넷, 23)

• 사용자가 원격에 있는 서버에 로그인하도록 TCP 연결을 설정
• 단말기가 원격 컴퓨터 바로 옆에 있는 것처럼 직접 조작할 수 있게 해줌

POP3 & IMAP

• POP3(110) : 메일 서버로 전송된 메일을 확인할 때 사용하는 프로토콜
• IMAP(143) : POP3 와 기본적으로 같으나 , 메일을 읽은 후 메일이 서버에 남음

SMTP(Simple Mail Transfer Protocol, 25)

• 메일 서비스

DNS(Domain Name System, 53)

• 도메인 이름 주소를 통해 IP 주소를 확인할 수 있는 프로토콜

TFTP(Trivial File Transfer Protocol, 69)

• 파일을 전송하는 프로토콜
• UDP 패킷을 사용하고 , 인증 기능을 제공하지 않음

HTTP( HyperText Transfer Protocol, 80)

• 인터넷을 위해 사용하는 가장 기본적인 프로토콜

---

네트워크 장비

네트워크 장비: 스위치 종류

• L2 스위치: MAC 정보 기반 네트워크 통신 지원
• L3 스위치: IP 정보 기반 네트워크 통신 지원
• L4 스위치: IP 정보 + 포트정보 기반 네트워크 통신 지원
• L7 스위치: Application Data 기반 네트워크 통신 지원

기본적인 네트워크의 구성

---

네트워크의 이해

네트워크의 사전적 의미

• 여러한 통신설비를 통해서 두대 이상의 컴퓨터를 서로 연결하는것

다수의 컴퓨터를 네트워크로 연결했을 때 얻을 수 있는 이점

• 데이터 공유가 용이함 (NAS)
• 주변장치 공유 (프린터)
• 눙률적인 통신 (메일)

---

근거리통신 (Local Area Network)

근거리 통신망 (LAN, Local Area Network)

• 한 건물이나 학교 내 캠퍼스처럼 비교적 가까운 지역에 한정된 통신망
  

---

광역통신 (Wide Area Network)

광역 통신망 (WAN)

• 두 개 이상의 근거리 네트워크가 넓은 지역에 걸쳐 연결되어 있는 것
• WAN은 하나의 국가 또는 국가와 국가 간을 연결하는 매우 범위가 넓은 네트워크
• 우리가 매일 사용하는 인터넷
  

---

통신방식

클라이언트/서버 시스템

• 다른 컴퓨터에 데이터 전송 서비스를 제공하는 컴퓨터를 ‘서버’라 하고, 서버에서 보내주는 데이터서비스를 수신하는 컴퓨터를 ‘클라이언트’라고 한다.
  

유니캐스트

• 네트워크에서 가장 많이 사용하는 방식
• 서버와 클라이언트 간의 일대일(1:1) 통신 방식
• 클라이언트의 IP주소와 MAC주소가 필요
  

브로드캐스트

• 로컬 LAN(라우터로 구분된 공간)에 있는 모든 네트워크 단말기에 데이터를 보내는 방식

• 서버와 클라이언트간에 일대모두(1:모두)로 통신하는 데이터 전송 서비스

• 브로드캐스트의 MAC주소는 FF-FF-FF-FF-FF-FF로 미리 정해져 있다.
  

• 다른 라우터를 찾거나, 라우터끼리 데이터를 교환하거나, 서버가 서비스를 제공하려고 모든 클라이언트에게 알릴 때 등 여러 상황에서 사용

• 하지만 불특정 다수에게 전송되는 서비스라 수신을 원치않는 클라이언트도 수신하므로 네트워크 성능 저하를 가져올 수 있다.
  

멀티캐스트

• 브로드캐스트는 데이터를 무조건 CPU로 전송하기 때문에 컴퓨터 자체의 성능을 떨어뜨림
• 멀티캐스트는 전송하려는 특정 그룹에게만 한 번에 전송할 수 있기 때문에 유니캐스트처럼 반복해서 보낼 필요가 없고, 브로드캐스트처럼 전송받을 필요가 없는 컴퓨터에 보내지 않아도 됨
  

---

---

프로토콜 (Protocol)

프로토콜에 대한 이해

• 본래의 의미는 외교에서 의례 또는 의정서
• 톰 마릴이 컴퓨터와 컴퓨터 사이에서 메시지를 전달하는 과정이라 정의

---

프로토콜의 3가지 요소

• 구문(Syntax): 데이터의 구조나 포멧을 의미

• 의미(Semantics): 전송되는 데이터의 각 부분이 무엇을 뜻하는지를 알 수 있게 미리 정해둔 규칙
  (데이터 자체뿐만 아니라 오류 제어, 동기 제어, 흐름 제어를 포함)

• 순서(Timing): 어떤 데이터를 보낼 것인지와 얼마나 빠르게 데이터를 보낼 것인지 정의

프로토콜의 기능

주소 설정(Addressing)

• 서로 다른 시스템의 두 개체가 통신을 하는경우 필요

순서 제어(Sequence Control)

• 프로토콜 데이터 단위를 전송할 때 보내는 순서를 명시하는 기능(연결 지향형 (Connection-Oriented)에서만 사용)

데이터 대열의 단편화 및 재조합(Fragmentation & Reassembly)

• 대용량 파일을 전송할 때 전송 효율이 높은 작은 단위로 나누어 전송한 뒤 전송 받은 시스템에서 이를 재조합 해야 함
• 어떻게 쪼갤건지, 재조합 할건지

캡슐화(Encapsulation)

• 데이터에 제어 정보를 추가

연결 제어(Connection Control)

• 연결 설정, 데이터 전송, 연결 해제에 대한 통제 수행

흐름 제어(Flow Control)

• 송신측 개체로부터 오는 데이터의 양이나 속도를 조절하는 기능
• 송신측과 수신측의 속도 차이 등으로 인한 정보 유실을 방지

오류 제어(Error Control)

• 두 개체에서 데이터를 교환할 때 오류가 발생할 경우, 이를 제어하는 기법
• 순서를 검사하거나 특정 시간 안에 받지 못하면 재전송을 요구하는 방식

동기화(Synchronization)

• 두 개체 간에 데이터를 전송할 때 각 개체는 특정 타이머 값이나 윈도우 크기 등을 통해 동시에 정의된 인자 값을 공유하는 것

다중화(Multiplexing)

• 통신 선로 하나에서 여러 시스템을 동시에 통신할 수 있는 기법

전송 서비스

• 우선순위 결정, 서비스 등급과 보안 요구 등을 제어하는 서비스

---

---

네트워크 계층 구조

네트워크 계층화에 대한 이해

• 1980년대 초 ISO(International Organization for Standardization)은 여러 업체가 만든 시스템에 대해 상호 연동이 가능한 표준 네트워크 모델을 제정할 필요성을 인식
• 1984년 OSI(Open System Interconnection) 네트워크 모델을 발표
  

OSI 7계층 모델

OSI 7계층

물리 계층: 1계층

• 실제 장치를 연결하는데 필요한 전기적, 물리적 세부 사항을 정의
• 물리 계층의 장치로는 허브나 리피터가 있음

데이터 링크 계층: 2계층

• 점대점(Point-to-Point) 사이의 신뢰성 있는 전송을 보장하기 위한 계층
• CRC 기반의 오류 제어와 흐름 제어가 필요
• 가장 잘 알려진 예는 이더넷

네트워크 계층: 3계층

• 여러 노드를 거칠 때마다 경로를 찾아주는 역할
• 라우팅, 흐름 제어, 단편화(Segmentation/Desegmentation), 오류 제어 등을 수행
• 대표적인 예는 라우터임, 또한 3계층에서 동작하는 스위치를 흔히 L3 스위치라 함.

전송 계층: 4계층

• 양 끝단 사용자들이 신뢰성 있는 데이터를 주고받을 수 있게 하여 상위 계층이 데이터 전달의 유효성이나 효율성을 고려하지 않아도 되게 해줌.
• 전송 계층에서 동작하는 프로토콜 중 TCP는 연결 지향(Connetion-Oriented) 프로토콜임

세션 계층: 5계층

• 양 끝단의 응용 프로세스가 통신을 관리하기 위한 방법을 제공
• TCP/IP 세션을 만들고 없애는 책임을 짐.

표현 계층: 6계층

• 시스템에서 사용되는 코드 간의 번역을 담당
• 표현 계층은 data의 Format(형식)을 정의함

응용 계층: 7계층

• 사용자나 응용 프로그램 사이에 데이터 교환을 가능하게 하는 계층
• HTTP, FTP, 터미널 서비스, 메일 프로그램, 디렉토리 서비스 등을 제공

---

TCP/IP 4계층

OSI 7계층 vs. TCP/IP 4계층

• OSI는 개념적인 모델 (실제 구현에서 반드시 지킨다고 볼 수 없음)
• TCP/IP 프로토콜은 OSI 모델보다 먼저 개발됨
• TCP/IP 프로토콜의 계층은 OSI 모델의 계층과 정확히 일치하지 않음
• 두 계층을 비교할 때, 세션(Session)과 표현(Presentation) 2개의 계층이 TCP/IP프로토콜 그룹에 없다는 것을 알 수 있음
• OSI 7 Layer는 장비 개발과 통신 자체를 어떻게 표준으로 잡을지 사용되는 반면에 실질적인 통신 자체는 주로 TCP/IP 프로토콜을 사용함
• 최근에는 TCP/IP 모델을 5계층으로 분류하기도 함

---

네트워크 계층 구조: 물리 계층

1계층: 물리 계층(Physical Layer)

• 두 시스템 간에 데이터를 전송하려고 링크를 활성화하고 관리하는 전기적 · 기계적 · 절차적 · 기능적 특성 등을 정의

• OSI 참조 모델 7계층 중 물리 계층은 최하위 계층인 첫 번째 계층으로, 상위 계층에서 전송된 데이터를 물리매체를 통해 다른 시스템에 전기적 신호로 전송

• LAN 카드, 케이블, 허브, 라우터 등 물리적인 것과 데이터 전송에 사용하는 전압 등 기본적인 것들이 물리계층에 속함.

• 송신 측: 데이터 링크 계층에서 0과 1로 구성된 비트열의 데이터(프레임)을 받아 전기적 신호로 변환한 후 전송매체를 통하여 수신측에 보냄

• 수신 측: 송신측에서 받은 전기 신호를 0과 1로 구성된 비트열로 복원, 수신측의 데이터 링크 계층에 전송
  

물리 계층 관련 장비

리피터(Repeater)

• 네트워클르 연장하기 위한 장비
• 불분명해진 신호 세기를 다시 증가시키는 역할
• 최근 리피터가 모든 네트워크 장비에 공통으로 들어가는 기능이 됨.

허브(Hub)

• 요즘 쓰이는 스위치의 예전 형태
• 허브는 스위치와 형태나 사용 방법이 같지만 패킷을 모든 곳에 똑같이 복사해서 보내는 것이 다름(스위치는 목적지에만 데이터를 전송)
  

---

네트워크 계층 구조: 데이터 링크 계층

2계층: 데이터 링크 계층(Data Link Layer)

• 물리적 링크를 이용하여 신뢰성 있는 데이터를 전송하는 계층
• 네트워크를 통해 데이터를 전송할 때 전송로 역할
• 데이터 링크 계층은 비트를 프레임이라는 논리적 단위로 구성
• 시스템 간에 오류 없이 데이터를 전송하려고 **네트워크 계층에서 받은 데이터 단위(패킷)를 프레임으로 구성하여 물리 계층으로 전송

• 데이터 링크 계층의 물리적인 주소: 랜카드나 네트워크 장비의 하드웨어 주소(MAC 주소)
• 네트워크 카드의 MAC 주소는 윈도우 명령 창에서 ‘ipconfig /all’ 명령을 실행하면 ‘Physical Address’ 에서 확인 가능
  • 리눅스 Machine의 경우 ifconfig 명령어

MAC 주소

• 총 12개의 16진수로 구성
• 앞쪽 6개는 네트워크 카드를 만든 회사(OUI: Organizationally Unique Identifier)를 뜻하고, 뒤쪽 6개는 호스트 식별자(Host Identifier)로 각 회사에서 임의로 붙이는 일종의 시리얼
• 같은 MAC 주소는 존재하지 않음
  

데이터 링크 계층 프로토콜: 이더넷

• 제록스의 PARC(Palo Alto Research Center)에서 1970년대에 개발한 데이터 링크 계층의 프로토콜

CSMA/CD (Carrier Sense Multiple Access/Collision Detection)

• 이더넷의 통신 방식
• 이더넷 환경에서 통신을 하고 싶을 때, Carrier Sense를 수행함
• 복수개의 디바이스가 동시에 통신을 시작할 때, Collision이 발생하고 이를 Detection 할 수 있음
• Collision Detection이 일어난 후, 랜덤한 시간을 기다리고 다시 데이터를 보냄

데이터 링크 계층 장비

브리지(Bridge)

• 랜(LAN)과 랜(LAN)을 연결하는 초기의 네트워크 장치
• 데이터 링크 계층에서 통신 선로를 따라서 한 네트워크에서 그 다음 네트워크로 데이터 프레임을 복사하는 역할
  

스위치

• 기본적으로 데이터 링크 계층에서 작동하는 스위치를 뜻함 (L2 스위치)
• 허브의 단점이 Collision Domain의 확대를 해결
  • L2 스위치는 연결된 시스템이 늘어날수록 패킷 간 충돌 때문에 매우 낮은 속도로 동작하는 더미 허브의 문제점을 해결하는 획기적인 방안
• 과거에는 브릿지를 통해서 Collision Domain을 나누었지만, 현재는 스위치가 인기가 많음.

스위치의 MAC 주소 테이블

• 시스템 간의 원활한 통신을 위해 주소 테이블을 생성하고 관리하는 역할
  

네트워크 계층 구조: 네트워크 계층

3계층: 네트워크 계층(Network Layer)

• 랜(LAN)을 벗어난 통신을 하기 위해 네트워크 계층에서 IP 주소를 사용
• 라우팅 프로토콜을 사용하여 최적의 경로를 선택
• 네트워크 계층은 데이터를 패킷 단위로 분할하여 전송한 후 재결합함
  

---

수업 개요

• TCP/IP 모델을 사용하여 인터넷이 동작하는 원리를 학습

수업 교재

• Computer Networking: A Top-Down Approach, 7th Edition (Pearson)
  • James Kurose and Keith Ross
• 교재에 포함되지 않는 내용은 강의교안을 통해 제공

중간 기말 일정

• 중간시험 (8주차)
  • 2021년 10월 21일 목요일 오후 7시 (오프라인)
• 기말시험 (15주차)
  • 2021년 12월 9일 목요일 오후 7시 (오프라인)

성적 처리

• 중간/기말 시험 60%
  • 기말시험범위: 전범위
• 과제물 제출 30%
  • 퀴즈 및 과제 포함
• 출석 및 수업태도 10%