공부정리

1. 리스트(List)

 리스트는 입력받은 데이터를 순차적으로 저장하는 가장 간단한 형태의 선형 자료구조이다.  리스트는 일반적으로

다음과 같은 기능을 가진다.

• 데이터 삽입
  • insert(e) : 데이터 e를 맨 뒤에 삽입 
  • insert(e, i) : 데이터 e를 인덱스 i에 삽입
• 데이터 삭제
  • delete(i) : 인덱스 i의 데이터 삭제
  • delete(e) : 데이터 e를 찾아 삭제
• 데이터 탐색
  • search(i) : 인덱스 i의 데이터 반환
  • search(e) : 데이터 e를 찾아 인덱스를 반환

이 외에도 구현자의 의도에 따라 리스트의 모든 요소를 제거, 리스트의 요소를 정렬, 리스트가 비어있는지 확인 등

다양한 기능이 들어가기도 하지만 가장 기본적인것은 위의 세 가지이다.

2. 리스트의 특징

• 구현이 간단하며 대부분의 프로그래밍 언어에서 기본 자료형 또는 내장 라이브러리의 형태로 지원
• 다수의 데이터를 순서를 유지한채로 그룹화하여 관리하기 좋음
• 특정 데이터를 탐색하는데 O(N) 의 시간복잡도를 보임 

3. 리스트의 구현 방식에 따른 특징

• 배열 리스트(Array List) : 배열을 기반으로 구현된 리스트
  • 인덱스를 활용하여 특정 순번의 데이터에 대해 O(1) 의 시간복잡도로 빠른 탐색이 가능
  • 삽입, 삭제 연산 실행 시 데이터들의 인덱스를 조정해야하기 때문에 O(N)의 시간복잡도를 보임
  • 배열의 크기에 제한이 있어 최초에 할당했던 크기 이상의 데이터를 삽입할 경우 배열을 확장하는
    과정을 거쳐야함

• 연결 리스트(Linked List) : 데이터를 하나의 노드로 구성하여 서로 연결시키는 것으로 구현된 리스트
  • n 번째 데이터에 접근하기 위해서는 링크를 타고 넘어가는 과정을 n번 거칠 필요가 있어 특정 순번의
    데이터를 탐색하는데 O(N)의 시간복잡도를 보임
  • 어느 위치에서 삽입/삭제 연산 실행 하더라도 새로운 노드를 만들어 전후의 연결관계만을 조정하면
    되기 때문에 O(1) 의 시간복잡도로 처리 가능
  • 데이터가 추가될 때마다 노드를 생성하기 때문에 데이터가 늘어나더라도 별도의 확장과정이 필요없음

4. 연결 리스트의 종류

• 단방향 연결 리스트
  • 각 노드가 데이터와 다음 노드의 주소로 이루어진 연결 리스트
  • 현재 노드에서 이전 노드를 참조할 수 없음
• 양방향 연결 리스트
  • 각 노드가 데이터와 이전 노드의 주소, 다음 노드의 주소로 이루어진 연결 리스트
  • 현재 노드의 이전 노드와 다음 노드를 모두 참조할 수 있음
• 원형 연결 리스트
  • 양방향 연결리스트의 첫 노드와 끝 노드를 서로 연결시킨 연결 리스트
  • 현재 탐색중인 노드를 가리키는 포인터 하나만으로 head와 tail을 모두 참조할 수 있는 것과 마찬가지
  • 스트림 버퍼나 큐를 구현하는데에도 사용 가능하며 데이터를 순환탐색하기에도 편리하다.

1. ADT(Abstract Data Type) 란?

 ADT, 혹은 추상자료형이란 어떤 대상에 대한 데이터와 그 데이터들에 대한 연산을 정의하는 것으로 대상을

추상화하여 표현한 것이다.  

2. ADT의 예시

 예를들어 추상화의 대상이 동전지갑이라고 가정해보자.  동전지갑은 동전을 하나 또는 여러개씩 넣을 수 있으며

마찬가지로 하나 또는 여러개씩 꺼낼 수 있다.  이것을 추상화 한다면 다음과 같이 표현할 수 있을 것이다.

Datas:
    coin_10 : 10원짜리 동전의 갯수
    coin_50 : 50원짜리 동전의 갯수
    coin_100 : 100원짜리 동전의 갯수
    coin_500 : 500원짜리 동전의 갯수
   
Operations:
    insert(coin_type, cnt) : coin_type 에 해당하는 동전의 갯수를 cnt 만큼 증가시킨다.
    delete(coin_type, cnt) : coin_type 에 해당하는 동전의 갯수를 cnt 만큼 감소시킨다.

종류별 동전의 갯수를 data로 가지며 각 동전을 cnt개 만큼 넣었다 뺐다 할 수 있는 지갑을 ADT로 나타낸 것이다.

3. 자료구조의 인터페이스, ADT

 위의 예시처럼 ADT는 데이터와 연산의 기능에 대해 설명할 뿐, 연산의 내부 구현이 어떻게 이루어져있는지 등에 대해

언급하지 않는다. 그렇기에 ADT는 자료구조의 인터페이스와도 같다.  사용자는 ADT만을 보고도 자료구조를 사용할 수

있지만 실제로 각 연산들이 어떻게 구현되어있는지는 알 수 없으며 알 필요도 없다.  이렇게 인터페이스와 구현을

구분하는 것으로 내부 구현이 바뀌더라도 사용자는 여전히 같은 방식으로 자료구조를 사용할 수 있으며 개발 측에서는

필요 이상의 정보를 공개하지 않고도 사용자에게 기능을 제공할 수 있다.  앞으로 알아볼 자료구조들을 직접 구현해보는

경우에도 먼저 간단하게 ADT를 정의하고 이를 구현하는 흐름으로 진행할 것이다. 

네트워크의 종단.  호스트와 브라우저 등의 애플리케이션이 여기에 속한다

1. Network Architecture

 ① 클라이언트-서버(Client-Server) 모델

• 클라이언트(Client) : 네트워크를 통해 서버측에 접속하여 서비스를 요청하고 제공받는다.
  
  
• 서버(Server) : 네트워크를 통해 클라이언트로부터 요청을 받아 서비스를 제공한다.
  
• 서버가 다수의 클라이언트로부터 요청을 받아 이를 처리하고 결과를 반환하는 형태
  
• 중앙 서버가 서비스와 데이터를 전적으로 관리하기 때문에 네트워크 구성 및 유지/보수가 효율적
  
  
• 모든 부담이 중앙 서버에 집중되기 때문에 중앙 서버에 대한 공격을 허용하게 될 경우 치명적인
  상황으로 이어질 수 있다. 이를 막기위한 보안 솔루션이나 백업 등에 추가비용이 발생할 수 있다.

 ② P2P(Peer to Peer) 모델

• 서비스를 제공하는 측과 요청하는 측이 비대칭적으로 존재하는 클라이언트-서버 모델과 달리
  연결된 모든 호스트가 서비스를 제공하는 측이면서 동시에 서비스를 요청하는 측이 되는 모델
  
  
• 하나의 서버에 부담을 몰아주는 방식이 아니기 때문에 연결된 호스트가 늘어날 수록 트래픽과
  소모 자원을 분산시킬 수 있다는 장점이 있다.
  
  
• 기능의 추가나 업데이트 관리가 어려우며 호스트간의 전송 속도 차이로 인해 정보 불일치나
  성능 저하 등의 문제가 발생할 수 있다.

2. Protocol

 ① 프로토콜(Protocol)

• 네트워크에서의 Protocol이란 네트워크상에서의 통신을 위해 맺은 약속, 규약을 의미한다.
  
  
• TCP, IP, UDP, HTTP, SMTP 등의 마지막 P는 모두 Protocol의 약자

 ② 연결지향(Connection Oriented) 서비스 - TCP(Transmission Control Protocol)

• 서로 통신할 호스트간에 연결을 확립한 후 통신하는 방식. 네트워크 통신에 있어 여러 기능을 제공
  
  
• reliable, in-order byte stream data transfer : 데이터의 순서유지, 데이터의 전달을 확인하고 유실시 재전송
  
  
• flow control(흐름 제어) : 수신 측의 처리속도에 맞춰 데이터의 전송 속도(패킷의 전달 갯수) 조절
  
  
• congestion control(혼잡 제어) : 네트워크망 내의 데이터의 전송 속도 조절을 통해 네트워크의 오버플로를 방지

 ③ 비연결지향(Connectionless) 서비스 - UDP(User Datagram Protocol)

• 호스트간 연결을 확립하지 않고 통신하는 방식.  연결지향 서비스에서 제공하던 기능을 제공하지 않음
  
  
• 흐름제어, 혼잡제어, 데이터의 신뢰성과 순서유지를 모두 지원하지 않음
  
  
• 용도
  
  • 데이터의 유실이 치명적이지 않으며 실시간으로 빠르게 데이터를 전송할 필요가 있는 경우에 사용
  • broadcast 나 multicast 등 다수와의 통신이 이뤄질 경우 연결 확립이 불가능하기에 UDP가 사용됨
  • 화상회의 등이 대표적인 예시(음성과 영상의 실시간 전송)