[CS] 놓쳤던 기초 CS 정리

Logun·2023년 10월 5일

CS basic

CS

목록 보기

13/17

✅ Mark and Sweep Algotithm

닿을 수 없는 주소를 더 이상 필요없는 주소로 정의하고 지우는 알고리즘

표시 페이즈(Mark phase)

객체가 생성되면 비트를 0(false)로 표시한다.
마크 페이즈에서는 모든 도달 가능한 객체. 또는 사용자가 참조할수 있는 객체에 1(true)가 찍힙니다.
이제 이 동작을 수행하려면 그래프 탐색(graph traversal)을 할 필요가 있다. 그리고 그 방법으로 깊이우선 탐색기법(depth first search approach)을 사용한다.
여기에선 모든 객체를 노드처럼 취급하고, 더이상 들를 곳이 없을때까지 노드에서 접근할 수 있는 모든 노드들을 방문합니다.
루트는 객체를 참조하는 변수이며, 지역변수가 곧장 접근할 수 있다.
일단 루트가 하나만 있다고 간주한다.
markedBit(obj)의 호출로 객체의 mark bit에 접근할 수 있다.
만약 루트가 하나 이상이라면 그냥 모든 루트에다 Mark를 호출하면 된다.

쓸기 페이즈(Sweep phase)

"sweep(쓸어버린다)"라고 이름을 붙였듯이, 이건 힙 메모리에 있는 모든 도달 불가능한 객체를 치워버린다.
marked 값이 false로 설정된 모든 객체는 정리되고, true인 객체는 유지한다.
이제 도달가능한 객체의 mark값을 false로 설정해서 다시 마크 페이즈로 넘어가 모든 도달가능한 객체에 마크를 하도록 해야한다.
마크앤스윕 알고리즘은 프로그램에서 직간접적으로 접근할 수있는 모든 객체를 추적하기 때문에 추적(tracing) 가비지 컬렉터라고도 부른다.

✅ 관계 연산자

객체에 속성이 있는지 확인하기 위한 연산자

const x = {
    name: "Kim Tae-Wan"
    email: "ktw9115@naver.com"
  }
  "name" in x; // true

✅ 흐름제어

Control Flow
- if / Then / Else
  거짓으로 표현되는 것들
  false, undefined, null, 0, NaN, ""(empty string)
- Switch / Case
- For / While
  do - while
  while문과 다르게 먼저 진입 후 로직을 실행한 다음 조건을 검사한다.
```
   let x = 0;
do {
  console.log("Fire");
} while (x > 10);
```
Data Flow
- Stateless
- Recursion
- Pipe

✅ 컴퓨터가 시간을 표현하는 방법

하드웨어의 시스템 클럭을 이용하여 특정 시각(Epoch)을 기준으로 클럭의 틱을 세는 것으로 구현된다.

이를 시스템 시간으로 부르고, 값으로 표현한 것을 타임스탬프(Timestamp)라고 부른다. 타임스탬프는 운영체제마다 기준 시간과 단위가 다를 수 있다.

유닉스 계열 운영체제에서 시간을 표시하는 방법을 Unix Time라고 부른다.

시스템 클럭의 원리
Rtc(Real Time Clock)라는 모듈이 메인보드에 붙어있어, 전원을 끄더라도 계속 작동한다. 카운터회로를 통해 클럭을 발생시키는데, 핵심부품인 결정 진동자가 만드는 주파수를 이용한다. 1클럭에 1초를 계산하기 쉬운 주파수인 32.768kHz가 발생한다.
결정 진동자에대한 자세한 내용
UTC(세계 협정 시)
원자 시계와 윤초 보정을 기반으로 표준화한 시각이며, 모든 시간을 UTC+0 기준으로 환산한다. T는 Time을 의미하고, Z는 Zulu Time을 뜻한다.
경도 0(Zero)의 앞글자 z를 나타내고 z는 무선 통신 용어로 Zulu라고 표현된다.
```
2021-03-20T09:00:00Z 
// UTC+0기준 2021년 3월 20일 9시
2021-03-20T09:00:00+09:00
// UTC+9(한국시간) 기준 2021년 3월 20일 9시
```
Unix Time
1970년 1월 1일 0시 0분 0초가 기준 시각이며, 이전 시간은 음수로 표현된다. 초 단위로 시간이 증가하는 특징이 있다.

🤔 현재 시간은 어떻게 알아낼까?

시스템 시간을 네트워크 타임 프로토콜(NTP)를 통해 동기화 할 수 있고, NTP서버에 네트워크 요청을 하여 현재 시간을 받을 수 있다.

NTP서버는 계층으로 이루어져 있으며, 그 계층을 Stratum이라 부르고 최상위 계층은 PRC(Primary Reference Clock)라고 부른다.

🧨 그렇다면 시간대를 어떻게 고려해야할까?

Time zone 데이터를 활용하여 시간을 고려할 수 있다. 현실 세계에서 일광 시간 절약제나 어떠한 이벤트로 시간이 바뀌면 해당 데이터베이스에 저장이 된다.

표기법은 Asia/Seoul, America/New_York와 같이 대륙/도시 형태를 따르고 이 값을 Zoneid라고 부른다.

✌️ 시간을 어떤 기준으로 사용해야 할까?

글로벌 서비스를 운영할 때 시간을 매우 중요한데, 사용되는 시간을 용도에 맞춰서 기록할 필요가 있다.

UTC
역사, 사회, 문화에 대한 맥락 없이 사건이 발생한 시각만을 고려할 때 사용한다.
주식과 같은 시계열 데이터

Time Zone이 적용된 시간
역사, 사회, 문화를 고려하여 이용한 시간을 정확히 알아야 할 때 사용한다. UI에 표시되는 시간을 사용자 기준으로 보여줄 때 사용한다.
결제 시각, 푸시 알림시간, UI 시각 표시, 캘린더

🎉 코드로 보는 시간 정리

'userId': 1,
'name': '김태완',
'zoneId': '1991-01-05' // 순수한 시간
'creatAt': '2023-10-08T04:59:25Z' // 기준 시간 UTC
'updateAt': '2023-10-08T05:12:38Z'
'posts': [
  {
    'postId': 1,
    'publishedAt': '2023-10-08T06:00:00Z',	
    // 기준 시간 오전 6시에 발행
    //publishedAt은 user의 zoneId에 따라 다르게 보일 수 있다.
]

✅암호화

평문(Plaintext)을 해독할 수 없는 암호문(Ciphertext)로 변환하는 것을 의미한다. 단방향(해싱)과 양방향 암호화가 존재한다.

단방향 암호화

해시 알고리즘을 이용하여 평문을 복호화 할 수 없는 형태로 암호화한다.
데이터를 저장하는 측에서 해당 정보를 알 수 없어야 하기에 사용한다.
대표적으로 MD5와 SHA 알고리즘이 있다.
사용자 비밀번호 등을 저장할 때 자주 사용된다.
MD%와 SHA-0, SHA-1은 해시 충돌이 발생할 수 있는 취약점이 있기에 사용을 권하지 않는다.

단방향 암호화에서 고려할 점

복호화가 불가능하지만 Rainbow Table을 통해 원문을 알아낼 수도 있다.
Rainbow Table은 평문과 해시 함수로 만든 문자열을 모두 저장시켜 놓은 표를 말한다.

따라서 불의의 사고로 암호화된 데이터를 탈취당하더라도 원문을 알아 낼 수 없도록 조치를 해야한다.

Salt, Key stretching를 이용하여 해결할 수 있다.

Salt
- 평문에 임의의 문자열을 추가하여 암호화하는 방법을 만한다.
- 재료에 소금을 곁들여 먹는것에 비유한 방법으로 128bit 이상으로 만들 것을 권장한다.
- 사용자마다 다른 Salt를 사용하게 하면 더 안전하다.
```
	8129387198asjldasljdaoislf + redfl0wer => DIGEST
```
Key stretching
- 해시를 여러 번 박복하여 원문을 알기 힘들게 만드는 방법이다.
- 일반적인 시스템에서 0.2초 이상 반복되면 안전하다고 한다.

Salt와 Key stretching을 이용하는 알고리즘

직접 구현하는 것보다 이미 검증받은 알고리즘을 사용하는 것이 안전하다.

PBKDF2
- NIST(미국표준기술연구소)에서 승인된 알고리즘
- DIGEST = PBKDF2(PRF, Password, Salt, c, DLen)
bcrypt
- 비밀번호 저장을 목적으로 탄생했다.
- OpenBSD에서 기본으로 사용하고 있는 알고리즘.
- $2a$10$N9qo8uLOickgx2ZMRZoMyeljZAgcfl7p92ldGxad68LJZdL17lhWy
- $2a Alg, $10 Cost
- $N9qo8uLOickgx2ZMRZoMyelj Salt
- ZAgcfl7p92ldGxad68LJZdL17lhWy Hash

양방향 암호화

평문을 복화하 할 수 있는 형태로 암호화하는 방법이다.
대칭키와 비대칭키 알고리즘으로 나뉜다.
대표적으로 대칭키를 이용하는 AES와 비대칭키를 이용하는 RSA로 나뉜다.

대칭키 암호 알고리즘
- 대표적으로 AES(Advanced Encryption Standard)가 있다.
- 같은 키를 이용하여 암호화, 복호화가 가능하다.
비대칭키 암호 알고리즘
- 대표적으로 RSA(Rivest, Shamir and Adleman)가 있다.
- 이름이 특이한데 RSA 알고리즘을 만든 사람들 3명 이름을 따서 만들었다고 한다.
- 공개키(암호화)와 개인키(복호화) 두 가지 키가 존재한다.
- RSA는 소인수 분해를 기반으로 만들어진 알고리즘이다.

다수를 대상으로 하는 방법으로 비대칭키가 쓰인다.

✅ 프로그래밍

프로그램은 순차, 분기, 반복, 참조로 구성된다.
패러다임은 위 4가지 요소를 어떻게 이용할 것인가를 다룬다.

객체지향 OOP

객체지향 추상화의 최소 단위가 객체이고, 객체는 현실에 있는 것을 추상화한 것이다. 객체 위주로 설계하고 프로그래밍하는 패러다임으로 각각의 객체는 메시지를 주고받을 수 있다.

function StringNumber(string) {
  this.string = string;
}
  StringNumber.prototype.calculate = function () {
      const stringNumber = "12345";
      this.sum = 0;
      for (let i = 0; i < sringNumber.length; i += 1) {
          this.sum += stringNumber[i] - "0"; 
      }
  };

const stringNumver = new StringNumber("12345");
const printer = new Printer();
stringNumber.calculate();
printer.log(stringNumber.sum);

부모 객체를 이용하여 프로토타입 함수를 정의할 수 있다.(prototype)

function Person(name) {
	this.name = name;
}

Person.prototype.getName = function () {
	return this.name || "선협"; 
};

function Korean(name) {}
Korean.prototype = new Person();

const lee = new Person("이선협");
const kim = new Korean("김선협");
console.log(lee.getName()); // 이선협
console.log(kim.getName()); // 선협

부모 생성자를 빌려 쓸 수 있다. (apply)

  function Person(name) {
  	this.name = name;
  }

  Person.prototype.getName = function () {
  	return this.name || "선협";
  }

  function Korean(name) {
  	Person.apply(this, arguments);
  }
  Korean.prototype = new Person();
  Korean.prototype.setName = function (name) {
  	this.name = name;
  };

  const lee = new Person("이선협");
  const kim = new Korean("김선협");
  console.log(lee.getName()); // 이선협
  console.log(kim.getName()); // 김선협
  kim.setName("박선협");
  console.log(kim.getName()); // 박선협

기존 객체를 재활용할 수 있다. (object.create)

const lee = {
	name: "이선협"
    getName: function () {
    	return this.name;
    }
};

const kim = Object.create(lee);
kim.name = "김선협";

console.log(lee.getName()); // 이선협
console.log(kim.getName()); // 김선협
console.log(lee.__proto__); // {}
console.log(kim.__proto__); // { name: '이선협', getName: [Function: getName]}

함수형 Functional

함수형은 함수가 최소 단위이고,함수 단위로 나눠지므로 재사용성이 높다.
불변성을 지향하기에 동작을 예측하기 쉽고 사이드 이펙트를 방지한다.
사이드 이펙트를 방지한다는 것은 동시성 문제도 해결된다는 의미
함수형은 변수 할당에 부과되는 규율

장점
- 상태가 없기 때문에 사이드 이펙트가 없다.
- 재사용성이 높고, 코드가 짧고 간결하다.
단점
- 상태가 없기 때문에 메모리와 성능을 사용하는 경우가 발생한다.
- 쪼개진 함수가 너무 많아 기억을 못할 수 있다.

const stringNumber = "12345";
console.log(
	stringNumber
  		.split('')
  		.map(x => parseInt(x))
  		.reduce((x,y) => x + y, 0);
);

참고 자료
마크 앤 스윕 알고리즘(번역)

Logun

로건의 개발이야기

이전 포스트

[CS] 네트워크에 대하여

다음 포스트