TIL 45 (유니코드, 운영체제, 가비지컬렉션, 캐시) (2021.11.25)

-오늘의 코플릿 2021.11.25- LCS
문제
두 문자열을 입력받아 다음의 조건을 만족하는 LCS*의 길이를 리턴해야 합니다.
LCS: 두 문자열에 공통으로 존재하는 연속되지 않는 부분 문자열(Longest Common Subsequence)문자열 'abc'의 subseqeunce는 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc' 입니다.

// 입출력 예시
let output = LCS('abcd', 'aceb');
console.log(output); // --> 2 ('ab' or 'ac')

output = LCS('acaykp', 'capcak');
console.log(output); // --> 4 ('acak')

최근 들어서 토이 문제의 난이도가 많이 올라가서 구현보다는 알고리즘에 대해서 학습한다는 의미로 코드를 이해하고 있습니다. 해당 문제도 dp 로 풀 수 있는 문제로, 해당 방법에 대해서 리뷰해보도록 하겠습니다.

이 방법에서 가장 중요한 것은 각 문자열을 앞에서 부터 하나씩 비교하면서 LCS를 구한다고 가정을 하면, 각 문자열에서 중복되는 문자가 있을 경우, 해당 문자까지의 LCS는 그 직전 문자열까지의 LCS에서 1을 더한 값이며,

동일하지 않은 문자까지의 LCS는 직전 LCS와 동일하다 입니다. 

참 간단하고 당연한 이론인데, 이 방법을 알면 코드로 쉽게 구현할 수 있습니다.

dp 에 대한 블로그 글

// dynamic programming: O(M * N)
// tabulation(테이블에 정리)을 활용해 bottom-up 방식으로 해결

// 참고한 글 https://st-lab.tistory.com/139
const LCS = function (str1, str2) {
    const M = str1.length;
    const N = str2.length;
    // table[i][j]는 str1.slice(0, i)와 str2.slice(0, j)의 LCS를 저장
    // str1.slice(0, i)는 0부터 i 바로 직전까지를 의미함 (i까지가 아님에 주의)
    const table = [];
    for (let i = 0; i < M + 1; i++) table.push(Array(N + 1).fill(-1));
  
  // table = [ -> str2의 길이
  //        a   c   e   b
  //   [-1, -1, -1, -1, -1],
  // a [-1, -1, -1, -1, -1],
  // b [-1, -1, -1, -1, -1],
  // c [-1, -1, -1, -1, -1],
  // d [-1, -1, -1, -1, -1]
  //]
  
    for (let i = 0; i <= M; i++) { // 테이블의 각 행을 표현한다.
      for (let j = 0; j <= N; j++) { // 테이블의 각 열을 표현한다.
        if (i === 0 || j === 0) {
          // 테이블 상에서 i 또는 j가 0인 경우, 한쪽 문자열이 길이가 0이라는 의미이다.
          // LCS가 존재할 수 없으므로, 0을 저장한다.
          // table 0번째 행이 전부다 0으로 채워진다
          // table 각 행의 0번째 요소가 0으로 채워진다.
          table[i][j] = 0;
        } else if (str1[i - 1] === str2[j - 1]) {
          // 테이블 상에 0이 포함되어 있으니깐, -1을 해줘야지, str1, str2 상에서 문자의 위치가 나오게 된다.
          // 두 문자가 같은 경우
          // 양쪽 문자열의 인덱스가 한 개씩 이전인 상태에서 만들 수 있는 LCS의 길이보다 1만큼 더 길다.
          // => 테이블 상에서 해당 위치의 좌측 상향의 대각선에 위치한 값보다 1이 크다.
          table[i][j] = 1 + table[i - 1][j - 1];
        } else {
          // 두 문자가 같지 않은 경우
          // 둘 중 한쪽을 포기하는 경우에 만들 수 있는 LCS의 길이를 따른다.
          // 현재 위치에서 좌측, 상측 중 큰 값
          table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);

        }
      }
    }
    return table[M][N];
  };
  // 최종적으로 만들어지는 table의 모양
  // [
  //   [ 0, 0, 0, 0, 0 ],
  //   [ 0, 1, 1, 1, 1 ],
  //   [ 0, 1, 1, 1, 2 ],
  //   [ 0, 1, 2, 2, 2 ],
  //   [ 0, 1, 2, 2, 2 ]
  // ]

---

유니코드란

유니코드 협회(Unicode Consortium)가 제정하는 전 세계의 모든 문자를 컴퓨터에서 일관되게 표현하고 다룰 수 있도록 설계된 산업 표준입니다.(문자셋(인코딩, 디코딩의 기준)의 국제 표준)

 

이 표준에는 ISO 10646 문자 집합, 문자 인코딩, 문자 정보 데이터베이스, 문자를 다루기 위한 알고리즘 등을 포함하고 있습니다.

 

유니코드의 목적은 현존하는 문자 인코딩 방법을 모두 유니코드로 교체하는 겁니다.

 

ASCII 문자란

영문 알파벳을 사용하는 대표적인 문자 인코딩으로 7 비트로 모든 영어 알파벳을 표현할 수 있습니다. 52개의 영문 알파벳 대소문자와, 10개의 숫자, 32개의 특수 문자, 그리고 하나의 공백 문자를 포함합니다. (유니코드는 ASCII를 확장한 형태입니다.)

 

UTF-8과 UTF-16의 차이점

UTF-8과 UTF-16은 인코딩 방식의 차이를 의미합니다.

UTF-8은 Universal Coded Character Set + Transformation Format – 8-bit의 약자로, UTF- 뒤에 등장하는 숫자는 비트(bit)입니다.

UTF-8은 1 byte에서 4 bytes까지의 가변 길이를 가지는 인코딩 방식입니다. 네트워크를 통해 전송되는 텍스트는 주로 UTF-8로 인코딩됩니다. 사용된 문자에 따라 더 작은 크기의 문자열을 표현할 수 있기 때문입니다.

UTF-8은 ASCII 코드의 경우 1 byte, 크게 영어 외 글자는 2byte, 3byte, 보조 글자는 4byte를 차지합니다.

그리고 UTF-8은 UTF-16에 비해서 바이 순서를 따지지 않고 바이트 순서가 고정되어있습니다.

 

반면 UTF-16는 코드 그대로 바이트로 표현 가능하며 바이트 순서가 다양합니다.

UTF-16은 유니코드 코드 대부분(U+0000부터 U+FFFF; BMP) 을 16 bits(2바이트)로 표현합니다.

• 대부분에 속하지 않는 기타 문자는 32 bit(4 bytes)로 표현하므로 UTF-16도 가변 길이라고 할 수 있으나, 대부분은 2 바이트로 표현합니다

U+ABCD라는 16진수를 있는 그대로 이진법으로 변환하면 1010-1011-1100-1101 입니다. 이 이진법으로 표현된 문자를 16 bits(2 bytes)로 그대로 사용하며, 바이트 순서(엔디언)에 따라 UTF-16의 종류도 달라집니다.

UTF-8에서는 한글은 3 바이트, UTF-16에서는 2 바이트를 차지합니다.

정리를 하자면, UTF-8, UTF-16의 차이는 인코딩 용량의 차이이며, UTF-8은 1~4바이트, UTF-16은 2, 4바이트로 인코딩이 된다. UTF-8은 통상적으로 사용을 하고, UTF-16은 극한의 최적화를 위해 사용한다.

 

---

 

비트맵(래스터)과 벡터 이미지의 차이점

비트맵은 수학적 연산을 사용해서 Heavy한 벡터보다 Light하며, 다운로드 받을 때는 벡터가 조금 더 빠를 수 있지만, 출력할 때는 비트맵이 더 빠를 수 있습니다. 

---

운영체제가 하는 일

시스템 자원 관리

운영체제는 응용 프로그램이 하드웨어에게 일을 시킬 수 있도록 도와줍니다. 하드웨어를 구성하는 일을 하는 CPU, 자료를 저장하는 RAM, 디스크 등의 시스템 자원을 관리하는 주체가 바로 운영체제입니다.

• 프로세스 관리(CPU)
• 메모리 관리
• I/O(입출력) 관리 (디스크, 네트워크 등)

응용 프로그램 관리

• 응용 프로그램이 실행되고, 시스템 자원을 사용할 수 있도록 권한과 사용자를 관리합니다.

응용 프로그램이 운영체제와 소통하기 위해서는, 운영체제가 응용 프로그램을 위해 인터페이스(API)를 제공해야 합니다. 응용 프로그램이 시스템 자원을 사용할 수 있도록, 운영체제 차원에서 다양한 함수를 제공하는 것을 시스템 콜(System call)이라고 부릅니다.

 

응용 프로그램이 사용할 수 있는 권한을 획득한 후에는, 필요한 API를 호출해야 합니다. 이 API는 시스템 콜로 이루어져 있습니다.

 

읽어볼 자료

---

1. 프로세스(Process)

운영체제에서는 실행 중인 하나의 애플리케이션을 프로세스라고 부릅니다. 사용자가 애플리케이션을 실행하면, 운영체제로부터 실행에 필요한 메모리를 할당받아 애플리케이션의 코드를 실행합니다.

 

2. 스레드(Thread)

한 가지 작업을 실행하기 위해 순차적으로 실행한 코드를 의미합니다. 하나의 스레드는 코드가 실행되는 하나의 흐름이기 때문에, 한 프로세스 내에 스레드가 두 개라면 코드가 실행되는 흐름이 두 개 생긴다는 의미입니다.

 

스레드의 특징

• 프로세스 내에서 실행되는 흐름의 단위
• 각 스레드마다 call stack이 존재(call stack: 실행 중인 서브루틴을 저장하는 자료 구조)
• 스레드는 다른 스레드와 독립적으로 동작

 

3. 멀티 스레드(Multi-Thread)

멀티 스레드는 애플리케이션 내부에서 다수의 스레드가 존재하는 것입니다.

멀티 스레드는 다양한 곳에서 사용됩니다. 대용량 데이터의 처리시간을 줄이기 위해 데이터를 분할하여 병렬로 처리하는 데에 사용할 수도 있고, UI를 가지고 있는 애플리케이션에서 네트워크 통신을 하기 위해 사용할 수도 있습니다.

 

멀티 스레딩의 장점

프로세스를 이용하여 동시에 처리하던 일을 스레드로 구현할 경우, 메모리 공간과 시스템 자원의 소모가 줄어듭니다. 스레드 간의 통신이 필요한 경우에도 별도의 자원을 이용하는 것이 아니라, 전역 변수의 공간 또는 동적으로 할당된 공간인 Heap 영역을 이용합니다.

 

처리량(Throughput)이 향상되고 자원 소모가 줄어들어 자연스럽게 프로그램의 응답 시간이 단축됩니다.

이런 장점 때문에 여러 프로세스로 할 수 있는 작업을 하나의 프로세스에서 스레드로 나눠 수행합니다.

 

멀티 스레딩의 문제점

서로 다른 스레드가 같은 데이터에 접근하고, 힙 영역을 공유하기 때문에 서로 다른 스레드가 서로 사용 중인 변수나 자료구조에 접근하여 엉뚱한 값을 읽어오거나 수정하는 일이 발생할 수 있습니다.

 

그렇기 때문에 멀티스레딩 환경에서는 동기화 작업이 필요합니다. 동기화를 통해 작업 처리 순서를 제어하고, 공유 자원에 대한 접근을 제어해야 합니다.

 

4. 동시성과 병렬성의 차이

동시에 돌릴 수 있는 스레드 수는 컴퓨터에 있는 코어 개수로 제한됩니다. 운영체제(또는 가상 머신)는 각 스레드를 시간에 따라 분할하여, 여러 스레드가 일정 시간마다 돌아가면서 실행되도록 합니다. 이런 방식을 시분할이라고 합니다.

• Concurrency(동시성, 병행성): 여러 개의 스레드가 시분할 방식으로 동시에 수행되는 것처럼 착각을 불러일으킴
• Parallelism(병렬성): 멀티 코어 환경에서 여러 개의 스레드가 실제로 동시에 수행됨

Context Switching이란?

다른 태스크(프로세스, 스레드)가 시작할 수 있도록 이미 실행 중인 태스크(프로세스, 스레드)를 멈추는 것을 Context Switching이라고 합니다.

---

가비지 컬렉션이란?

가비지 컬렉션은 프로그램에서 더 이상 사용하지 않는 메모리를 자동으로 정리하는 것입니다. 이 기능을 가진 언어(혹은 엔진)는 자바, C#, 자바스크립트 등이 있습니다.

 

대표적인 가비지 컬렉션의 방법

• 트레이싱: 한 객체에 flag를 두고, 가비지 컬렉션 사이클마다 flag에 표시 후 삭제하는 mark and sweep 방법입니다.
  객체에 in-use flag를 두고, 사이클마다 메모리 관리자가 모든 객체를 추적해서 사용 중인지 아닌지를 표시(mark)합니다. 그 후 표시되지 않은 객체를 삭제(sweep)하는 단계를 통해 메모리를 해제합니다.
• 레퍼런스 카운팅: 한 객체를 참조하는 변수의 수를 추적하는 방법입니다.
  객체를 참조하는 변수는 처음에는 특정 메모리에 대해 레퍼런스가 하나뿐이지만, 변수의 레퍼런스가 복사될 때마다 레퍼런스 카운트가 늘어납니다. 객체를 참조하고 있던 변수의 값이 바뀌거나, 변수 스코프를 벗어나면 레퍼런스 카운트는 줄어듭니다. 레퍼런스 카운트가 0이 되면, 그 객체와 관련한 메모리는 비울 수 있습니다. 레퍼런스 카운트가 0이 된다는 말은 아무도 그 객체에 대한 레퍼런스를 가지고 있지 않다는 말과 같습니다.

자바스크립트에서는 변수의 영역에서 변수가 저장이 되고, 데이터 영역에서 값과 참조할 수 있는 주소가 저장이 됩니다. 변수는 데이터의 주소를 참조를 하는데, 데이터의 주소를 참조하는 변수가 없다면, 그 데이터는 가비지가 되고 가비지 컬렉터에 의해 정리가 될 수 있습니다. => sprint hour를 통해서 학습한 걸 정리해봤는데 추가적인 학습이 더 필요할 거 같습니다. 참고 자료 

---

캐시란 무엇인가요?

 

많은 시간이나 연산이 필요한 작업의 결과를 저장해두는 것을 의미합니다.
컴퓨팅에서 캐시는 일반적으로 일시적인(temporarily) 데이터를 저장하기 위한 목적으로 존재하는 고속의 데이터 저장 공간입니다. 첫 작업 이후에 이 데이터에 대한 요청이 있을 경우, 데이터의 기본 저장 공간에 접근할 때보다 더 빠르게 요청을 처리할 수 있습니다. 캐싱을 사용하면 이전에 검색하거나 계산한 데이터를 효율적으로 재사용할 수 있습니다.

 

캐시의 일반적인 작동원리

캐시의 데이터는 일반적으로 RAM(Random Access Memory)과 같이 빠르게 액세스할 수 있는 하드웨어에 저장되며, 소프트웨어 구성 요소와 함께 사용될 수도 있습니다. 캐시는 기본 스토리지 계층(SSD, HDD)에 액세스하여 데이터를 가져오는 더 느린 작업의 요구를 줄이고, 데이터 검색의 성능을 높입니다.

 

속도를 위해 용량을 절충하는 캐시는 일반적으로 데이터의 하위 집합을 일시적으로 저장합니다. 완전하고 영구적인 데이터가 있는 데이터베이스와는 대조적입니다.

 

캐시의 장점

• 애플리케이션 성능 개선
• 데이터베이스 비용 절감
• 백엔드 부하 감소
• 예측 가능한 성능
• 데이터베이스 핫스팟 제거
• 읽기 처리량 증가
  • 읽기 처리량: IOPS; Input/output operations per second. HDD, SSD 등의 컴퓨터 저장 장치의 성능 측정 단위

웹서비스에서 캐시가 적용되는 예제

• 클라이언트: HTTP 캐시 헤더, 브라우저
• 네트워크: DNS 서버, HTTP 캐시 헤더, CDN, 리버스 프록시
• 서버 및 데이터베이스: 키-값 데이터 스토어(e.g. Redis), 로컬 캐시(인-메모리, 디스크)

읽어볼 자료

 

-