CS 3일차

• Stack 과 Queue
• Insertion Sort
• HTTP 와 HTTPS
• 운영체제란?

Stack

• 스택은 Last In First Out 으로, 요소가 들어올 때마다 기존 요소들에 차곡차곡 쌓아 올린 형태의 자료구조이며,
  제일 마지막으로 들어온 요소 즉, Top 이 가르키는 요소에만 접근, POP을 할 수 있다.
• 비어있는 상태의 스택을 pop 할 때 stack underflow, 꽉 찬 스택에 push 할 때 stack overflow를 발생시킨다.
• 배열로 구현할 시에, top 인덱스를 활용하여 여러 메소드를 구현한다.
• 스택의 활용 예시
  • 운영체제의 메모리 스택
  • 웹 브라우저 방문기록의 뒤로가기
  • 역순 문자열, 후위 표기법 계산, 수식의 괄호 검사 등
  • DFS ( 함수의 재귀, 메모리 스택을 활용 ), 미로찾기
  • 2개로 큐 구현하기.

Queue

• 큐는 First In First Out 으로, 먼저 들어온 요소에만 접근하여 pop 되는 실생활의 대기줄과 같은 자료구조이며,
  큐의 front에서 pop이 일어나고, 큐의 rear에서 push가 일어난다.
• 배열로 구현시 front, rear 인덱스를 활용하여 규현한다.
• 스택과 다르게 삽입, 삭제의 발생 인덱스가 달라서, overflow, underflow를 잘 계산하여야 하며,
  원소의 수가 적거나 없어도 rear의 인덱스는 항상 증가하여 공간 낭비하는 문제점이 있다.
• 이를 해결하기 위해, 환형 큐를 사용하며, 인덱스들을 %큐의 크기 연산 해주어 공간 낭비를 해결한다.
  ( front와 rear인덱스의 값을 비교하여 겹쳐서 overflow인지 underflow인지 구분할 때 사이즈를 사용해야 한다. )
  ( 이를 단순하게 하기 위해서 항상 첫 원소를 비워두는 기법도 있다. )
• 큐의 활용 예시
  • 우선순위 작업
  • 프로세스 관리
  • 여러 대기 상황 구현.
  • 캐시 구현
  • BFS

Insertion Sort

void insertionSort(int arr[], int n){
    int tmp;
    int idx;
 
    for(int i=1;i<n;++i){
        tmp = arr[i];
        idx = i-1;
        while(idx >= 0 && arr[idx] > tmp){
            arr[idx+1] = arr[idx];
            --idx;
        }
 
        arr[idx+1] = tmp;
    }
}

• 삽입 정렬은 평균, 최악의 시간복잡도가 O(n^2) 로 버블, 선택 정렬과 같이 느리지만 직관적인 알고리즘으로 여겨지지만,
  최선의 경우 O(n)이기도 하며, 전체적으로 위 두 알고리즘보다 빠른 정렬기법이다.
• 배열의 인덱스가 0부터 시작될 때, 1 ~ n-1 라운드가 진행되며, i 라운드에 i 번째 원소의 위치를 찾는다.
  이 때, 0 ~ i 인덱스까지의 요소들은 정렬되어 있다고 가정하며 역순으로 탐방하며 자신의 위치를 찾아 들어간다.
  위 성질 때문에, 이미 원소가 정렬되어 있는 경우 즉, 최선의 경우 매 라운드마다 한번의 비교만을 거쳐 다음 라운드로 넘어가기 때문에
  O(n) 시간 복잡도를 지닐 수 있다.
• in-place 정렬이므로 공간복잡도는 O(n) 이다,

HTTP

• Hyper Text Transfer Protocol
• 웹상에서 텍스트를 주고 받는 통신 규약.
• TCP와 UDP, 80번 포트를 사용하여 주로 HTML 문서를 주고 받는다.
• Text를 암호화 없이 Plain으로 주고 받기 때문에 보안에 취약하다.
  도청 위험, 사용자 위장 위험, 무결성 보장 불가 등 단점이 있다.
• 비연결 지향 방식(요청에 응답 데이터 전송 후 연결 종료) 이기 때문에 간단하여 비용이 적고,
  인터넷이 끊겼다가 복구 되어도 서버와 재연결할 필요성이 없다.
• 때문에 사용자의 추가적인 요청 시 어떤 사용자의 요청인지, 여러 사용자가 요청 시 각각의 사용자를 구분할 수 없다.
• 따라서 아무나 봐도 상관없는 페이지는 효율적으로 http로 구성하기도 한다.
  이 밖의 보안에 민감한 정보를 갖고 있는 사이트들은 https를 사용하여야 한다.

HTTPS

• Hyper Text Transfer Protocol over Secure socker layer
• SSL 이나 TLS 프로토콜을 통해 데이터를 암호화하여 TCP/IP 443번 포트를 사용하여 통신한다.
• SSL 은 인증 받은 신뢰 기관인 CA를 통해 공개키 방식을 사용하여, 서버와 클라이언트가 통신할 때 사용 할
  대칭키를 안전하게 교환하고, 이를 사용하여 안전하게 통신을 진행한다.
• 암호화 방식을 통해 구글에서 제공하는 SEO 이점이 생겼으며, HTTP 방식과 다르게 보안성이 크게 향상 되었다.
• 연결 지향 방식이기 때문에 인터넷이 끊기면 소켓 연결이 끊어져 재연결 및 재 요청, 전송이 이루어져 다소 비효율적이다.
• 또한 암호키 교환, 암호화 - 복호화 진행 등 서버에 과부하가 생기고, CA 사용료 발생이라는 단점도 있다.

CA 공개키 기법을 활용한 대칭키 교환.

• CA ( Certificate Authority ) 는 신뢰하는 민간 서드 파트 인증 기관이다.
• 서버가 CA에 [서버의 사이트 정보, 서버의 공개키] 를 보내며 인증 요청을 한다.
• CA의 개인키로 [서버의 사이트 정보, 서버의 공개키] 를 암호화 하여 사이트 인증서를 발급한다.
• 사용자는 CA를 신뢰하고 이용하며, 사용자의 브라우저에 CA의 공개키를 저장한다.
• 사용자가 서버에 접속 요청을 하면, 서버는 CA의 개인키로 암호화된 발급받은 인증서를 제공한다.
• 사용자는 브라우저에 저장된 CA의 공개키로 인증서를 복호화하고 얻은 [사이트 정보, 사이트 공개키] 를 확인한다.
• HTTPS 통신에 사용할 대칭키를 생성하고, 획득한 서버의 공개키로 암호화하여 서버에 전송한다.
• 서버는 자신의 개인키로 복호화하여 대칭키를 얻는다.
• 안전하게 교환한 대칭키를 사용하여 서버와 사용자간 암호문을 주고받으며 통신한다.

운영체제란?

• 컴퓨터 하드웨어 위에 설치되어, 사용자 및 다른 모든 소프트웨어와 연결하고 인터페이스를 제공하여
  하드웨어를 쉡게 사용, 제어 하도록 도와주는 소프트웨어이다.
• 한정된 시스템의 자원을 효과적으로 사용할 수 있도록 관리 및 윤영함으로써 사용자에게 편리성을 제공한다.
• 운영체제의 기능은 프로세스 관리, 저장장치 관리, 네트워킹, 사용자 관리, 디바이스 관리 등이 있다.
• 운영체제는 동시 작업 가능 여부, 사용자 수, 처리 방식 등으로 분류 할 수 있다.

운영체제 기능

• 프로세스 관리
  • 프로세스와 스레드를 관리, 스케줄링하여 CPU의 사용률을 높히고 최적화 한다.
  • 다중프로그래밍 환경에서의 동기화
  • 프로세스간 통신, IPC
• 저장 장치 관리
  • 캐시 메모리
  • 메인 메모리
  • 2차 저장 장치
• 네트워킹
  • 인터넷 연결과 응용 프로그램이 네트워크를 사용할 수 있도록 네트워크 프로토콜을 지원한다.
• 사용자 관리
  • 여러 사용자가 사용하는 환경에서 별도의 파티션 관리
  • 사용자 별 접근 권한을 관리
• 디바이스 관리
  • 여러 하드웨어를 인식하고 관리하도록 디바이스 드라이버 지원
  • 디바이스 드라이버 = 운영체제 안의 하드웨어 추상화

운영체제 분류

• 동시 작업 가능 여부
  • 단일 작업 ( Single Tasking )
    • MS - DOS 프롬프트 처럼 한 번에 하나의 작업만 처리.
  • 다중 작업 ( Multi Tasking )
    • UNIX, MS Windows 처럼 한 명령의 수행이 끝나기 전에 다른 명령이나 프로그램을 처리 가능.
• 사용자 수
  • 단일 사용자 ( Single User )
    • MS - DOS, MS Windows
  • 다중 사용자 ( Multi User )
    • UNIX, NT Server
• 처리 방식
  • 일괄 처리 방식( Batch Processing System )
    • 작업 요청을 모아서 한꺼번에 처리.
    • 작업이 종료 될 때 까지 기다려야 함.
  • 시분할 방식 ( Time Sharing System )
    • 여러 작업을 수행할 때 컴퓨터 처리 능력을 일정한 시간 단위로 분할하여 사용.
    • 짧은 응답 시간 장점.
    • 대화형 방식 ( Interacive )
  • 실시간 방식 ( Realtime System )
    • 정해진 시간 안에 어떠한 일이 반드시 종료됨이 보장되어야 하는 실시간 시스템
    • Hard Realtime System = Deadline 이 엄격함.
    • Soft Realtime System = 조금 널널함.