DNA로 돌아와서, 자주 반복되는 DNA motif 를 찾거나, 가장 자주 등장하는 k-mer를 찾거나, 특정한 k-mer가 얼마나 자주 등장하는지 알고 싶을 때 문자열 패턴 매칭 알고리즘을 사용할 수 있다. 제일 근본적인 패턴 매칭 문제는 문자열에 특정 패턴이 존재하는지 확인하고, 존재한다면 그 위치는 어디인지 찾는 것 제일 나이브한 방법은 문자열을 직접 순회하면서 찾는 것이다.이때는 패턴의 길이가 n이고, 문자열의 길이가 m일 때, O(mn) 의 시간이 걸린다.  근데 이걸 조금 더 최적화 해보면,위와 같은 문자열에서 ssi 를 찾는다고 할 때, SS까지 일치했는데, i가 m이랑 불일치해서 실패한 경우,우리는 그 다음에 시도할 위치를 한번 건너뛸 수 있다.우리가 찾는 패턴의 prefix ss가 지금 ..

(문해기는 시간이 없어서 간결하게 정리할 예정..) 지금까지는 DNA에 대한 이야기였다면 이번에는 단백질에 대한 이야기를 해보자.단백질은 아미노산들의 조합으로 구성된다.각각의 아미노산은 탈수결합을 통해 합쳐지며, 그 결과물을 residue 라고 부른다.이때 20가지 아미노산 residue 의 분자량은 이미 정확하게 잘 알려져 있다. PIT 라는 고분자에 대해, PIT, PTI, ITP 등 순서는 분자량에 영향을 주지 않는다.따라서 이들 각각을 2개로 쪼갰을 때, (PI, IT) 와 (PT, TI) 의 분자량 합은 같다 (?) 20가지 아미노산에 대해 결합에 참여했을 때 물이 빠진 상태의 분자량을 하나의 테이블에 저장할 수 있고,이를 Daltons 이라고 부른다.  더보기 AminoAcid = { '..

흐름을 다시 정리해보면 어떤 문장이 CFG에 포함되는지 판별하기 위해서 파싱을 활용할 수 있는데,CFG는 너무 자유도가 높아서 파싱 시간이 오래걸리고, 심지어 끝나지 않을 수도 있다. 따라서 이 문제를 해결하고자 지난 글에서는 CFG의 문법을 단순화하기 위해λ-production, unit-production, useless production 순으로 필요없는 프로덕션을 제거하였다. 이번 글에서는 CFG의 특수한 형태를 갖는 노말 폼 형태의 문법을 통해 간단하게 파싱할 수 있도록 표현하는 방법을 정리한다. Chomsky Normal Form모든 production 이 다음 형태를 가지면 참스키 노말 폼이다. 1. A → BC ( A, B, C 는 변수)2. A → a (a는 터미널)  예를 들어 6.7 ..

운영체제에서도 정리했지만, 조금씩 설명이 다른 부분이 있어서 DB에서도 추가로 정리한다. RAID여러 개의 디스크를 사용하여 장애에 대비하는 기법Redundant Array of Independent Disks 의 약자로, 여러 디스크의 배열을 두고, 데이터를 저장하는 방법이다.RAID는 논리적으로는 1개의 디스크로 보이지만, 실제 내부적으로는 여러 개의 디스크를 구성하는 것이다. RAID는 크게 2가지 개념이 있다. 1. 데이터 스트라이핑2. 중복 (redundant) 1번은 데이터를 여러 곳에 나누어 저장한다는 의미로 성능 향상에 효과적이다.2번은 데이터를 중복해서 저장한다는 의미로 장애에 강해져서 신뢰성 향상에 효과적이다.RAID는 데이터 스트라이핑과 중복을 구현한 디스크 배열이다.  사용자가 디스..

Sector 구조 하드디스크의 하나의 섹터는 위와 같은 포맷으로 되어있다.우선 실제 데이터가 들어가는 부분이 제일 중요할 것이고 그 앞 뒤로는 부가 정보를 저장한다.데이터는 보통 512byte 크기가 저장된다. Preamble : bit pattern 으로 시작하며, 이 부분이 섹터의 시작임을 나타낸다.또한 실런더 넘버와 섹터 넘버와 같은 정보가 들어있다. ECC : Error-Correcting Code, read error 가 발생했을 때 복구할 수 있도록, 여분 정보가 저장되어 있다. 디스크에는 일부 섹터가 망가지는 것을 대비해서 여분의 spare sector를 남겨둔다.그리고 이와 같이 초기 세팅을 하는 것을 low-level formatting 이라고 한다.   Cylinder Skew (★) ..

Hard Disk 하드디스크는 위 그림과 같이 여러 원판(플래터)이 겹겹이 쌓여있는 구조로 되어있다.그리고 원판의 앞/뒷 면에 데이터를 저장할 수 있다.이 원판이 쌓여있는 원통형 구조를 실린더라고 부른다. 플래터에서 데이터를 읽는 것은 헤드가 담당하며, 헤드는 디스크 arm 에 붙어있다.디스크 암은 좌우로 움직이면서 트랙을 이동할 수 있다.   플래터 하나는 여러개의 동심원으로 구성되어 있으며, 각각의 동심원으로 이루어진 영역을 트랙이라고 부른다.그리고 트랙은 중앙을 향하는 세로선에 의해 분할된 '섹터' 로 구성된다.왼쪽 그림을 보면 하드디스크 안쪽은 트랙당 섹터가 16개 이고, 바깥쪽은 트랙당 섹터가 32개로 되어있다.반지름의 길이가 달라지기 때문에 2가지 종류의 트랙으로 구성한 것이다. 오른쪽 그림은..

입출력 장치입출력 장치는 크게 3가지로 분류할 수 있다. - Block Device : 고정된 크기의 블록에 데이터를 저장하는 장치. 각각의 블록은 주소를 가지며 주로 512KB ~ 323768KB 의 크기를 갖는다. 대표젹인 예시는 Disk - Character Device : 운영체제와 character stream을 주고 받는 장치. 블록 구조가 없기에 주소 체계도 없고, 무언가를 찾는 동작도 하지 않는다. 대표적인 예시는 프린터, 마우스, 네트워크 인터페이스 - Other device : 기타 장치들. 클락, Memory-mapped screens 등이 있다.    위 그림은 대표적인 입출력 장치들의 데이터 전송속도를 보여준다.아래로 내려갈수록 입출력 속도가 빨라지며, 사용자와 직접 상호작용하는 ..

전자 상거래샘이 아마존에서 상품을 주문하면 TLS (SSL의 새로운 버전) 프로토콜을 사용해서 요청을 암호화하여 보낸다.이때 암호화를 하는 기본적인 방법은 이전 글에서 정리한 RSA를 사용하여 아마존이 제공하는 공개키를 통해 요청을 암호화한다.아마존은 수신한 요청을 자신의 비밀키로 복호화하여 내용을 확인하고 처리한다.따라서 내 요청이 다른 사람에게 탈취당하더라도 다른 사람은 내 요청 내용을 알아낼 수 없다. 그런데 아마존이 알려준 공개키를 어떻게 신뢰할 수 있을까?해커가 자신의 공개키를 대신 보내주고 마치 이게 아마존의 공개키인 것처럼 속일 수도 있지 않을까? 그래서 이를 보증하기 위해 verysign 과 같은 인증기관이 등장했다.이 기관은 이 공개키가 아마존의 공개키가 맞다는 것을 보증해준다. 아마존은..

암호학 : 비밀 메세지를 보내는 기법사이퍼 (chiper) : 원문 메세지의 내용을 훼손하지 않고 메세지의 각 문자를 다른 문자나 기호로 바꾸는 방법 시저 암호알파벳을 특정 key 숫자만큼 자리 이동시켜 재배열한 글자로 대체 3글자씩 뒤로 밀어서 abby를 deeb로 변환하였다. 이를 문자대신 숫자로 매칭해볼 수도 있다.  그러면 이렇게 3을 더한 값을 사용할 수 있다.물론 27은 범위를 벗어났으니 26으로 나눈 나머지를 취해서 1로 사용할 것이다.  키 값이 3이라는 것을 서로 알고 있다면, 복호화할 때는 역으로 그 값을 빼서 알파벳을 매칭시킨다.만약 음수가 나오면 26을 더한 값을 취하면 된다. (-1 + 26 = 25) 시저 암호를 사용하여 비밀 메세지를 주고 받을 때는 2가지 정보를 알아야 한다...

라이트닝 네트워크는 Fairness Protocol 이다.따라서 다음과 같은 특성을 갖는다. - Trustless operationLN에 존재하는 노드는 서로 믿을 필요가 없다.프로토콜 자체가 수학을 이용하여 치팅을 막아주는 것을 신뢰할 수 있기 때문이다. - Atomicity여러 payment channel 을 이어서 돈을 주고 받는 경우, 내가 보낸 돈은 상대방에게 전송되거나 전송되지 않거나, 둘 중 하나의 결과만 발생하는 원자성이 보장된다.중간에 보낸 돈이 멈춰서 안간다거나 하는 일은 발생하지 않는다.(만약 중간에 사기를 치는 사람이 있다면 돈을 돌려받을 방법이 있다.) - MultihopLN은 기본적으로 P2P 네트워크에서 시작했지만, 그 보안성이 end-to-end 로 확장되어 나와 직접 연결되..