CS

LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

Longest Common Subsequence? Substring? LCS는 주로 최장 공통 부분수열(Longest Common Subsequence) 또는, 최장 공통 문자열(Longest Common Substring)을 뜻한다. 해당 예시에서 최장 공통 부분수열(Longest Common Subsequence)은 BCDF, BCDE가 될 수 있다. 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다. 최장 공통 문자열(Longest Common Substring)은 BCD입니다. 부분문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능하다. 최장 공통 문자열(Longest Common Substring) 최장 공통 부분수열(Longest Common Subse..

바이오스 (BIOS - Basic Input/Output System)

정의 본래 펌웨어는 제품 생산 시에 탑재된 이후에는 내용 변경을 하지 않는 것이 관례였지만, 최근에는 지속적인 제품의 성능 향상 및 오류 개선을 위해 제품 출시 이후에도 제조사에서 새로운 펌웨어를 배포해 소비자들에게 업데이트 할 것을 권하는 경우가 늘어나고 있다. 이런 경우는 특히 스마트폰이나 휴대용 게임기와 같은 모바일 컴퓨팅 기기에서 흔히 볼 수 있다. PC용 펌웨어는 바이오스(BIOS: Basic Input/Ouput System)라고 하며, 해당 PC의 기본적인 데이터의 입력과 출력을 관리하는 것이 주된 역할이다. 바이오스는 메인보드(main board: 주기판) 상에 위치한 이피롬(EPROM), 혹은 플래시메모리(flashmemory) 칩에 저장되어 있다. 넓은 의미에서는 메인보드 외의 다른 하..

펌웨어 (Firmware)

펌웨어는 일반적으로 롬(ROM)에 저장된 하드웨어를 제어하는 마이크로 프로그램을 의미한다. 어떤 기능을 발휘하는 하드웨어를 만든다고 할 때, 그것을 제어하는 모든 회로를 하드웨어로만 만들면, 그 구조도 대단히 복잡해지고 심지어는 논리적인 표현을 하기가 어려운 부분도 발생한다. 이런 경우 상당부분을 소프트웨어로 대체하되 그 소프트웨어가 저장된 기억장치를 하드웨어의 제어 회로중의 중심부분으로 구성하면, 매우 간단하면서도 적은 비용으로 문제를 해결할 수 있게 된다. 이렇게 할 경우 하드웨어의 입장에서는 별도의 논리회로를 가진 것이 아니기 때문에 소프트웨어적인 특성을 가지고 있지만, 소프트웨어 입장에서는 마이크로 프로그램이 하드웨어를 제어하기 때문에 하드웨어적인 특성을 가진다고 설명할 수 있다. 소프트웨어의 기..

Overlapped (비동기) I/O, epoll, iocp 정의 및 코드

Overlapped I/O 논블록 소켓 단점을 보완한 네트워크 통신 방법이 Overlapped I/ 논블로킹 소켓 프로세스 소켓 I/O 함수가 리턴한 코드 would block 인 경우 재시도 호출 낭비 발생. 소켓 I/O 함수를 호출할 때 입력하는 데이터 블록에 대한 복사 연산 발생. CPU 안에 있는 캐시 메모리에 메모리 내용이 복사되어 있으면 데이터 액세스는 매우 빠르지만 캐시에 없는 데이터를 액세스할 때는 메인 메모리 RAM을 액세스하는데, 이 속도는 매우 느림. 물론 하드디스크나 네트워크 데이터보다는 빠르지만 고성능 서버 개발 시 이 복사 연산 무시할 수 없음. TCP, UDP 논블록 소켓에서 재시도용 호출 낭비 TCP 소켓 send() 함수를 호출하면 would block 은 절대 발생하지 않..

TCP와 UDP의 특징과 차이

전송계층은 송신자와 수신자를 연결하는 통신서비스를 제공하는 계층으로, 쉽게 말해 데이터의 전달을 담당한다. 그리고 데이터를 보내기 위해 사용하는 프로토콜이 있는데, 그 프로콜들이 바로 TCP와 UDP다. 1. TCP(Transmission Control Protocol) 인터넷상에서 데이터를 메세지의 형태로 보내기 위해 IP와 함께 사용하는 프로토콜. 일반적으로 TCP와 IP를 함께 사용하는데, IP가 데이터의 배달을 처리한다면 TCP는 *패킷을 추적 및 관리하게 된다. TCP는 연결형 서비스를 지원하는 프로토콜로 인터넷 환경에서 기본으로 사용한다. [ TCP 특징 ] 연결 지향 방식이다. 3-way handshaking과정을 통해 연결을 설정하고 4-way handshaking을 통해 해제한다. 흐름 ..

해시 함수의 종류

MD4 와 MD5 ① MD(Message Digest)4 Rivest 가 1990년에 만든 일방향 해시 함수로 128비트의 해시 값을 갖는다. 그러나 Dobbertin에 의해 MD4의 해시 값의 충돌을 발견하는 방법이 고안되어 현재는 안전하다고 할 수 없다. ② MD(Message Digest)5 MD4 를 만든 Rivest 가 1991년에 만든 일방향 해시 함수로 128비트의 해시 값을 갖는다. 여기서 입력은 512-비트 블록들로 처리된다. 전수 공격과 암호해독에 대한 우려가 심각해진 최근 몇 년을 제외하면 MD5 는 가장 널리 사용되던 안전한 해시 함수이었다. (2005년 깨졌으나, 사용은 되고 있음) ③ MD4 와 MD5 의 비교 - MD4 는 16단계의 3라운드를 사용하나 MD5 는 16단계의 4..

내부 및 외부 단편화 (Internal/External Fragmentation)

내부 단편화 (Internal Fragmentation) 내부 단편화란 주기억장치 내 사용자 영역이 실행 프로그램보다 커서 프로그램의 사용 공간을 할당 후 사용되지 않고 남게 되는 현상을 말한다. 위와 같이 100MB의 메모리에 80MB 크기의 프로세스를 올리게 되면, 20MB의 내부 단편화가 발생하게 된다. 즉, 적은 크기의 잔여 메모리가 발생해 해당 메모리를 사용할 수 없게 된다. 외부 단편화 (External Fragmentation) 외부 단편화란 남아있는 총 메모리 공간이 요청한 메모리 공간보다 크지만, 남아있는 공간이 연속적(contiguous)이지 않아 발생하는 현상이다. 위와 같이 남아있는 메모리 공간은 50MB+50MB =100MB로 요청한 메모리 공간 80MB보다 크지만, 남아있는 공간..

OS가 하는 일 및 컴퓨터 구조

OS가 하는일 OS는 응용프로그램간 하드웨어 사용을 조정하고 데이터를 관리한다. 사용자 관점 사용자가 어떻게 사용하느냐에 따라 달라진다. 예를 들어 데스크탑 같은 범용 컴퓨터는 주로 사용의 용이성에 집중하고, 스마트폰 같은 경우는 배터리와 낮은 퍼포먼스 때문에 연산을 적게하고 들고다니며 사용하기 쉽게하기 위해 인터페이스를 간소화한다. 시스템 관점 자원을 어떻게 해야 효율적으로 관리할 지를 결정하는 역할을 한다. Computer System Operation 현대의 컴퓨터 구조는 CPU, 메모리, 디스크, USB, 그래픽 어댑터로 구성된다. 컴퓨터가 구동을 하기 위해선 하드웨어를 초기화 하고 OS를 메모리에 적재할 프로그램에 가지고 있어야하는데 이를 bootstrap program이라 부른다. bootst..

Overflow (오버플로우)

오버플로우(overflow)의 의미 - 각 데이터타입은 자료형에 맞는 저장의 최대/최소 범위가 존재한다. int number; 라고 선언하자. number는 변수의 이름이며 그 앞에 있는 int는 변수의 타입이다. int형 자료형은 4바이트의 정수형 타입으로 음수를 고려하고 있기 때문에 number가 저장할 수 있는 최대값은 2의31승-1이고, 이 값은 곧 2147483647 이다. (약 21억) 따라서 number 변수에는 약 21억까지 저장이 가능하다. 그런데 만일 코드에서 number 변수에 저 최대 숫자 이상을 넣는다면 어떻게 될까? 이와 같이 저장할 수 있는 최대범위를 넘어설때 이를 "오버플로우(overflow)" 라고 부른다. 오버플로우(overflow)의 법칙 - number의 최대저장가능값..

프로세서, 메모리, 캐시 개념 및 원리 (메모리 및 버스/연결 관한)

시스템 버스 시스템 버스는 하드웨어를 물리적으로 연결하여 서로 데이터를 주고받을 수 있게하는 통로 역할을 한다. 이때 버스는 데이터 버스, 주소 버스, 제어 버스로 나뉜다. 데이터 버스 프로세서와 메인 메모리 그리고 주변 장치들 사이에서 데이터를 전송할 때 쓰인다. 이때 버스는 데이터를 주고받아야 하므로 양방향이다. 주소 버스 프로세서에서 메모리의 주소를 지정할 때, 그 주소가 어디인지에 대한 정보를 보내는 버스이다. 즉, 프로세서에서 01110011이라는 위치에 데이터를 보내려면 데이터 뿐만 아니라 데이터의 목적지인 01110011도 버스를 통해 보내는데 이를 주소 버스를 통해 보낸다. 결국 프로세서가 주소를 지정하면서 보내는 버스이다. 이 버스는 주소를 보내면 되니 단방향이다. 제어 버스 프로세서가 ..