알고리즘 고수가 되기까지

CS 정리

1. CPU 스케줄링 정리

2. 캐시 정리

코테 준비

1. 백준 1162 - 도로포장

: 다익스트라는 bfs의 연속이라고 보면 쉽다. 방문처리를 boolean으로 하는 것이 아닌 거리로 표현하여 이용하는 것임을 기억하자

2. 백준 2151 - 거울설치

: 방문처리를 할 때 어떤 것이 겹칠지를 더 상세히 생각해보자.

점점 TIL이 짧아지고있지만... 항상 복습하면서 꾸준히 쓰자!!!

설명 순서는 다음과 같습니다.

1. Cache가 등장한 배경
2. Cache란
3. Cache에 담는 데이터 선택하기

1. Cache가 등장한 배경

   - 기술의 발전으로 CPU 속도는 빠르게 증가하는 반면, 메모리는 그렇지 않음

   - CPU가 아무리 빨라도 메모리 처리 속도가 느리다면, 전체 속도는 느려지게 되어있음

   - 이를 개선하기 위한 장치가 Cache임

2. Cache란

   - Cache란 빠른 CPU와 느린 메인 메모리 사이 병목현상을 줄이기 위한 빠르고 작은 메모리

   - 메인 메모리를 빠른 캐시처럼 만들면되지 않을까? 용량이 크고 빠른 메모리를 사용하기에는 비용이 너무 많이 듬(가성비 X)

   - 결국 메모리의 '특정 데이터'만을 캐시에 올려서 빠르게 사용하도록 해야함. 어떤 부분을 캐시에 올려야할까

   - 우리는 메인 메모리에 접근하는 시간을 줄여야함. 최대한 CPU가 캐시에서만 사용할 수 있도록 해야함

   - 따라서, 자주 사용하는 데이터를 캐시에 올려야함

3. Cache에 어떤 데이터를 담을까

   - 어떤 데이터가 자주 사용될까 -> 자주 사용되는 데이터는 시간적 또는 공간적으로 몰려있을 가능성이 높다는 법칙을 이용함

      ① 시간적 지역성 : 최근 사용한 데이터를 다시 사용할 확률이 높다(ex. for문의 i)

      ② 공간적 지역성 : 최근 사용한 데이터의 주변 데이터를 사용할 확률이 높다(ex. 배열)

   - 따라서, 최근 사용한 데이터와 그 주변 데이터를 캐시에 올려놓을 필요가 있음

   - 또한, 캐시에 없는 데이터를 메모리에서 찾아서 올릴 때 '가장 최근에 사용된 적이 없는 것'과 교체함

   - 이 알고리즘 또한 시간적 지역성을 이용한 사례라고 생각합니다

캐시 메모리에 대해 알아볼 수 있었습니다

순서는 다음과 같습니다

1. CPU 스케줄링이 필요한 이유
2. CPU 스케줄링의 성능 평가 기준
3. CPU 스케줄링의 종류

1. CPU 스케줄링이 필요한 이유

   - 프로세스는 동작하려면 CPU가 필요함

   - 많은 프로세스들이 CPU를 요구할 때, CPU는 그 중 어떤 프로세스를 실행해야할지 선택해야함

   - CPU에 어떤 프로세스를 할당할 지 결정하는 것을 CPU 스케줄링이라고 

2. CPU 스케줄링의 성능 평가 기준

   - 여러 CPU 스케줄링 알고리즘이 등장할 수 있음(ex. 먼저 요청한 프로세스를 먼저, 적게 걸리는 것 먼저 등등)

   - 그 중 어떤 스케줄링이 가장 적합한지 고르려면 기준이 있어야 함. 이것이 CPU 스케줄링 성능 평가 기준임

   - 성능평가 기준

      ① CPU 이용률 : 시간당 CPU를 사용한 시간의 비율. CPU가 쉬지않고 계속 일을 해야(프로세스를 돌려야) 좋은 알고리즘임. 그러므로, 입출력 작업보다 프로세서 중심의 작업을 해야함.

      ② 처리율 : 시간당 처리한 작업의 비율. 많은 일을 끝내야 좋은 알고리즘임. 그러므로, 작업소요시간이 짧은 것을 먼저 처리하도록 해야함.

      ③ 소요시간 : 한 프로세스가 처리된 총 시간. 이 시간이 짧을수록 좋은 알고리즘임

      ④ 대기시간 : CPU를 할당받기까지 기다린 시간. 이 시간이 짧을수록 좋은 알고리즘임

      ⑤ 응답시간 : 처음 CPU를 할당받기까지 기다린 시간. 이 시간이 짧을수록 좋은 알고리즘임

3. CPU 스케줄링의 종류

   - 크게 두가지로 나눌 수 있음(선점형, 비선점형)

      ① 선점형

         : 프로세스가 CPU를 사용하고 있더라도, 운영체제가 강제로 CPU를 빼앗아 다른 프로세스에게 할당할 수 있는 방식.

      ② 비선점형

         : 프로세스가 종료되거나 스스로 대기상태에 접어들기 전까지 다른 프로세스가 CPU를 사용할 수 없는 방식.

   - 선점형 특징 : 더 급하게 처리해야할 일이 들어왔을 경우 먼저 처리할 수 있음. 그렇지만, Context-Switching이 발생하므로 오버헤드가 발생할 수 있음

   - 비선점형 특징 : Context-Switching 오버헤드는 적지만, 더 급한일을 처리할 수 없음

   - 대표적인 스케줄링 알고리즘

      ① FCFS(First Come First Served)

         * 먼저 온 프로세스가 먼저 CPU를 할당받아서 하나씩 처리하는 방식, 비선점형

         * 긴 시간이 필요한 프로세스가 끝날때까지 다른 프로세스는 모두 기다려야하므로 비효율

      ② SJF(Shortest Job First)

         * 짧은 시간이 필요한 프로세스를 먼저 처리하는 방법

         * 프로세스가 얼마나 시간을 필요로할지 애초에 알지 못함. 긴 시간이 필요한 프로세스는 기아현상 발생

      ③ Priority Scheduling

         * 높은 우선순위를 가진 프로세스를 먼저 처리하는 방법

         * 선점형 방식에서는 도착한 프로세스의 우선순위가 현재 실행되는 것보다 높으면 CPU를 할당받음

         * 비선점형 방식에서는 준비큐에 우선순위에 따라 삽입

         * 우선순위가 낮은 프로세스일 경우 기아현상 발생함

         * 이러한 기아현상은 결국 우선순위가 높은 프로세스가 계속 실행되므로 발생하는 것임. 그러므로, 우선순위가 높은 것을 낮춰야하고, 낮은것을 높이는 방식으로 해결해야 함.

         * 대표적인 방법으로는 aging이 있는데, 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방법임. 이렇게 하면 기아현상을 줄일 수 있음

      ④ Round Robin

         * 동일한 시간동안 계속 돌아가면서 CPU를 할당받는 방식, 선점형

         * 만약 이 시간이 커지면 결국 FCFS와 같아지므로 비효율적이고, 너무 짧을 경우 Context-Switching이 자주 발생해 오버헤드가 증가함

      ⑤ 다단계 피드백 큐 스케줄링

         * 가장 일반적인 CPU 스케줄링 알고리즘

         * 우선순위에 단계별로 큐가 여러개 있고, Round Robin으로 돌아감

         * 이후 실행된 프로세스의 우선순위를 하나씩 낮춤(aging)

         * 우선순위에 따라 긴급한 처리가 가능, 기아 현상 줄임, Round Robin으로 응답시간을 줄임

CPU 스케줄링에 대해 알아볼 수 있었습니다

설명 순서는 다음과 같습니다.

1. HTTP란?
2. HTTPS가 등장하게 된 배경
3. 두 가지 암호화 방식, 대칭키와 비대칭키
4. HTTPS를 이용한 전체적은 요청-응답 흐름

1. HTTP란?

   - HTTP란 Hyper Text Transfer Protocol의 약자입니다

   - 이 뜻은 Hyper Text를 전달하는데 사용되는 Protocol이란 뜻입니다

   - Hyper Text란 단순한 텍스트를 넘어 링크로 다른 문서로 넘어갈 수 있는 텍스트와 여러 멀티미디어 요소로 이루어진 문서를 말합니다

   - 이러한 Hyper Text는 HTML이라는 마크업 언어로 작성됩니다

   - Protocol은 약속을 의미합니다

   - 둘 사이에 메시지나 데이터를 주고받을 때 정해진 형식입니다

   - 따라서, HTTP는 HyperText를 요청하고 전달받는데 정해진 규칙을 의미합니다

   - 요즘 HTTP는 단순히 HyperText를 넘어 이미지, JSON 등 다양한 데이터를 주고받을 때 사용합니다

2. HTTPS의 등장배경

   - 우리는 네트워크 위에서 HTTP 규약에 맞는 요청 및 응답메시지를 주고받을 수 있게 되었습니다

   - 하지만, HTTP는 암호화를 하지 않고 평문으로 전송하기 떄문에, 네트워크 상에서 데이터를 탈취당할 수 있습니다

   - 그래서 보안에 취약한 HTTP를 해결하기 위해 HTTPS가 등장하게 되었습니다

   - HTTPS는 HTTP Secure의 약자로 HTTP에 보안을 더한 것입니다

   - HTTPS는 데이터를 암호화하는 방식으로 보안을 취득합니다

3. 두 가지 암호화 방식, 대칭키와 비대칭키

   - 그렇다면 어떻게 HTTPS는 데이터를 암호화할까요?

   - 클라이언트가 서버로 암호화된 메시지를 보내고 서버는 받은 암호화된 메시지를 복호화 해야합니다

   ① 대칭키

      - 가장 간단한 방법은 클라이언트와 서버 모두 둘만 아는 비밀스런 암호화된 방식을 알고 있으면 됩니다

      - 예를 들어 메시지가 a -> b, b -> c, c -> d ... 로 암호화됐다면, 복호화는 반대 방식으로 진행하면 되기 때문입니다

      - 이렇게 둘 모두 같은 암호화된 방식(키)를 가지고 있다고 해서 이러한 방법은 '대칭키'라고 불립니다

      - 하지만, 네트워크를 통해 통신하는 클라이언트와 서버는 직접 만나지 않기에 둘만 아는 '키'를 공유할 수 없습니다

   ② 비대칭키

      - 이후 '비대칭키' 암호화 시스템이 등장했습니다

      - 비대칭키는 공개키와 개인키로 이루어져있습니다

      - 클라이언트-서버 구조에서 공개키는 클라이언트 모두에게 공개된 키이고 개인키는 서버만 가지고 있는 키입니다

      - 비대칭키의 암호화 방식은 공개키로 암호화된 메시지는 개인키로만 복호화할 수 있고, 개인키로 암호화된 메시지는 비공개키로만 복호화할 수 있는 것입니다

      - 그래서 클라이언트는 요청 메시지를 서버의 공개키를 이용해 암호화를 하고 서버는 개인키를 이용해서 메시지를 복호화합니다

      - 이렇게 되면 클라이언트의 요청 메시지가 탈취당하더라도 복호화할 수 없습니다

4. HTTPS를 이용한 전체적인 요청-응답 흐름

   - HTTPS는 HTTP와 보안 계층인 SSL/TLS 프로토콜이 결합된 것입니다(TLS는 SSL의 업데이트 버전이므로, 둘은 같다고 봐도 무방함)

   - 요청 응답 흐름

      ① 서버는 CA(Certificate Authority)로 부터 CA의 개인키로 암호화된 '인증서'를 발급받습니다 (이유 : 클라이언트가 서버와 통신할 때, 그 서버가 신뢰할 수 있는 서버임을 증명하기 때문임)

      ② 클라이언트는 서버와 통신하기 전 접속 요청을 보냅니다

      ③ 서버는 인증서를 클라이언트에 전송합니다

      ④ 클라이언트는 CA의 공개키르 인증서를 복호화하고 서버를 신뢰할 수 있습니다

      ⑤ 클라이언트는 인증서안에 있는 서버의 공개키로 임의의 대칭키를 생성해 암호화합니다

      ⑥ 클라이언트는 암호화한 대칭키를 서버에 보내면, 클라이언트와 서버는 같은 키인 '대칭키'를 갖게됩니다

      ⑦ 이제 이 대칭키를 이용해서 서버와 클라이언트는 안전하게 데이터를 주고받을 수 있습니다

   - 데이터를 바로 공개키로 암호화하지 않는 이유는 대칭키를 이용해서 암호화하고 복호화할 때 더 빠르기 때문입니다

HTTP부터 HTTPS까지 알아보며, 대칭키와 공개키에 대해서도 알아볼 수 있었습니다.  

부트캠프 온라인 강의

1. 상속은 언제 사용할까?

   (1) 일반적으로 코드의 재사용성으로 알고 있지만, 그 뿐만이 아님

   (2) 부모의 클래스를 좀 더 확장 또는 구체적으로 만들때 사용

1. 문제
   - 부모의 private 메서드를 override 가능할까?

2. 시도
   - 직접 해보자

3. 해결
   - 부모의 private은 접근 자체가 불가능해서 되지 않는다

4. 알게된 점
   - override 조건
      ① 이름이 같고, 매개변수가 같고, 반환타입이 같아야함
      ② 부모보다 접근제한자가 더 넓어야 함
      ③ 부모보다 많은 수의 예외를 발생할 수 없음
      -> 만약 자식에서 예외를 발생한다면, 부모에서도 예외를 던지게끔 바꿔야함
      -> 만약 부모에 throw가 있다고 하더라도 자식 메서드는 예외를 던지지 않아도됨
   - private은 오로지 그 클래스 내부에서만 사용할 수 있음

코테준비

1. 백준 9466 - 텀 프로젝트

: 사이클을 찾고, 사이클에 해당하는 노드들의 개수를 세는 것. 다양하게 dfs를 적용시켜보자

2. 백준 1937 - 욕심쟁이 판다

: dfs를 이용한 dp문제. 많이 풀어본 유형이라 쉽게 끝낼 수 있음

내일은 네트워크 준비 착실히 해가자. HTTP와 HTTPS의 차이, 대칭키 공개키에 대해서 공부하자

부트캠프 실시간 강의

1. 문제
   - 부모와 조상까지 있을 경우, super는 어떤 것을 가리킬까?

2. 시도
   - 직접 해보자

3. 해결
   - super는 자신의 바로 위 조상을 가리킨다

4. 알게된 점 
   - super는 바로 위 부모을 가리키지만, 부모 또한 super를 써서 조상을 가리킬 수도 있다

1. 문제
   - "#".split("#")을 하면 배열에 어떻게 담길까?
   - "".split("#")을 하면 어떻게 될까?
   - " ".split("#")을 하면 어떻게 될까?

2. 시도
   - 직접 해보자

3. 해결
   -  첫번째는 길이가 0인 배열이 생성, 두번째는 길이가 1인 배열 생성, 세번째도 길이가 1인 배열 생성

4. 알게된 점
   - split메서드는 해당 구분자로 나눌 수 없을 경우, 문자열이 그대로 배열에 담겨서 반환됨
   - 나눌 수 있는 경우 구분자를 기준으로 양쪽을 길이로 나눔

2. 코테준비

1. 백준 1520 - 내리막 길

: 비교적 쉬운 dp문제

2. 백준 1707 - 이분 그래프

: 노드에서 하나씩 들어가며 1 또는 -1을 표시. 만약 1이 들어갈 자리에 -1이 표시되어있다면 이분 그래프를 만들 수 없는 것

다음주부터는 CS 모의면접이 있으니 준비 잘해서 가자!!!

코테준비

1. 백준 7662 - 이중 우선순위 큐

: 처음에는 두 개의 우선순위 큐를 이용해서 구현했다. 이 후 다른사람들의 풀이를 보고 TreeMap 자료구조를 알게되었다. 데이터 삽입, 삭제시 시간복잡도 O(logN)이므로, 정렬된 데이터에서 빈번하게 삽입과 삭제가 일어날 때 유용하게 사용할 수 있는 자료구조라고 생각했다.

2. 백준 17280 - 카풀 매칭

: end가 작고 start가 작은 운전자부터 매칭을 시작한다. 승객을 TreeMap 자료구조에 넣어놓고 운전자부터 lower_bound를 찾아서 승객과 매칭시켜준다. 그리디 알고리즘이 어려운 이유는 어떻게 탐욕적으로 선택할 것인가 이다. 다양한 문제를 풀어보며 방법을 익혀야한다고 생각한다.

부트캠프 온보딩강의 빠르게 clear한 후에 넘어가자. 할 것이 많다.

부트캠프 실시간 강의

1. 문제
   - 가변인자(ex. int... numbers)에서 인자를 전달하지 않으면 매개변수에 어떻게 들어갈까?
   - 인자로 null을 전달하면?
   - 가변인자 사용시 내부적으로 배열을 사용한다고 알고 있다. 위 두 상황일 경우 어떻게 될지 알아보자

2. 시도
   - 직접 확인해보자

3. 해결
   - 인자에 아무것도 전달하지 않을 경우(ex. sum()) -> numbers에는 길이가 0인 배열이 들어감
   - 인자에 null을 전달했을 경우(ex. sum(null)) -> numbers에 null이 들어감
   - 인자에 배열을 전달했을 경우(ex. sum(arr)) -> numbers에 arr의 주소가 들어감
   - 인자에 2차원 배열을 전달했을 경우 -> 컴파일 에러 발생, 가변인자는 1차원 배열만

4. 알게된 점
   - 가변인자는 sum(a, b, c) 이렇게 보통 사용되고, 내부적으로 배열을 생성해서 사용한다
   - 인자를 전달하지 않았을 경우 길이가 0인 배열이 전달된다

코테준비

1. 백준 1991 - 트리 순회

: 기본적인 트리 문제. 나중에는 정확한 트리를 구현해서 문제를 풀어보자

2. 백준 1967 - 트리의 지름

: 트리 탐색 문제. 모든 노드에서 갈 수 있는 최대 거리리 중 최대를 구하는 문제

오늘 하루도 고생했다!!!