Dynamic Programming - Floyd's Algorithm
2020. 4. 21. 17:38
🕶 Algorithm/알고리즘
많은 경우 중에서 비용 혹은 길이가 최소인 경우는? i부터 j까지의 최단 경로
Dynamic Programming - The Binomial Coefficient
2020. 4. 21. 17:23
🕶 Algorithm/알고리즘
3.1 The Binomial Coefficient nCk 라고 배웠다. standard notation은 (nk) 라고 쓴다. 위. n개의 물건 중 k개를 선택하는 방법. 시간이 오래걸린다. 계속 중첩돼서 값을 구해야 하기 때문에 오래 걸린다. 했던 일 또하고 또하고 또하고 recursive call 일어나는 횟수를 세면 2 * nCk - 1 이다. 이게 시간복잡도이다. n값이 고정되어 있더라도 k값이 변한다. k값이 n/2일 때 값이 가장 크다. Algorithm 3.1의 시간복잡도가 나쁘다는 것을 알 수 있다. 그러면 어떻게 하냐? B라는 2차원 배열을 만들어서 i값은 0부터 n까지 j값은 0부터 k까지 ㄱ 형태로 더하면서 채운다. 맨아래쪽의 ㄱ 아래 값을 return 하면 된다. 시간 복잡도는 채..
07. Threads (1)
2020. 4. 21. 12:48
🚦 Server/Operating System
Thread 하나의 프로세스에는 하나의 control만 존재하기 때문에 프로세스는 한번에 하나의 일만 처리할 수 있다. 그러나 쓰레드를 사용함으로써 Parallelism하게 사용할 수 있다. 프로세스와 마친가지로 스케줄링 단위(Excution Unit)이다. 프로세스보다 더 작은 단위이다. 프로세스로부터 Excution state를 뽑아내서 만든다. 프로세스의 Code 영역, Data 영역, Heap 영역은 thread 간에 공유된다. 하지만 Stack은 쓰레드 각자 따로 있다. 상대 Stack을 읽을 순 있다. 쓰레드끼리는 IPC없이 통신할 수 있다. 같은 Address space를 공유한다. 쓰레드끼리는 같은 메모리를 사용하므로 switch 비용이 적다. Process들은 각자 자기의 Thread를 ..
유전공학 9장 - 중합효소 연쇄 반응(PCR:The polymerase chain reaction)
2020. 4. 20. 23:25
🧬 Bio/유전공학
Designing primer primer가 너무 짧다면 다양한 DNA가 만들어져 background가 커진다. primer가 너무 길다면 주형 DNA와 혼성화를 이루는 속도가 느려진다. 17mer 짜리 primer가 가장 적당하다. Tm = (4×[G+C]) + (2×[A+T])℃ Studying PCR product Agarose gel electrophoresis qPCR : 증폭과 정량을 동시에 하는 PCR The polymerase chain reaction (PCR) 1970년대에 gene cloning기술의 개발은 이전에 불가능했던 방법으로 유전자와 유전자 활성에 대한 연구를 가능하게 함으로써 신선한 자극으로 받아들여졌다. 두번째 혁신적인 방법 - polymerase chain reactio..
Determining Thresholds
2020. 4. 19. 22:31
🕶 Algorithm/알고리즘
2.7 Determining Thresholds threshold 란? : 단순한 알고리즘보다 Strassen의 알고리즘을 사용하는 편이 더 좋을 것이라고 예상되는 지점 n-1 : merge할 때 걸리는 시간. 실험을 통해 알아내야 한다. merge 알고리즘을 만든 다음에 넣어봐야 아는 것이다. merge 할 때 시간 복잡도가 32 n 이라면 시간복잡도가 32n logn 는 merge sort 알고리즘 시간복잡도 이고 exchange sort 했을 때 n(n-1)/2 이다. exchange sort 실행 시간 < merge sort 실행 시간인 지점을 봐보자. 이 부등식의 의미는 n=1 이 될 때까지 한 것. 등식보다 ≥ 부등식으로 풀어야 한다. 현재 배열의 사이즈 = t 개 t개의 원소를 t/2로 나눠..
Multiplication of Large Integers (아주 큰 정수의 곱셈)
2020. 4. 18. 12:04
🕶 Algorithm/알고리즘
2.6 Arithmetic with Large Integer 2.6.2 Multiplication of Large Integers 굉장히 큰 정수의 곱셈은 어떻게 할까? 배열로 표현 한다. n자리 정수의 곱 시간복잡도는? n자리 정수 2개 곱셈 = O(n^2) 그럼 Divide and conquer로 시간복잡도를 낮춰보자. n자리 정수를 절반으로 나눠서 계산하자 m은 n자리 정수를 2로 나눈 값이다. u와 v 는 n자리 정수이다. >>> integer 타입이 아니라 배열이다. if ( u 나 v 가 0이면 ) : 곱이 0이니까 0이고 else if ( threshold보다 작다면 ) : u와 v를 그냥 곱한다. else : m은 n을 2로 나눈 값이고 divide는 나눈 몫을 나타낸다. 이때 divde는..
미생물학 4장 (4) - 용균성, 용원성
2020. 4. 17. 17:03
🧬 Bio/미생물학
용원성 (lysogenic) 숙주가 휴지상태에 있을 때, 파지는 용원상태로 염색체 유지 Prophage : 파지의 DNA가 세균의 염색체 안으로 들어가버린 상태 프로파지 상태로 감염된 숙주 : 용원균 중복감염 면역성 : 용원균은 동일한 파지에 의해 재차 감염이 일어나지 않는다 그람음성 살모넬라균 : 파지감염이 되면 LPS가 수용체 역할을 못하면서 중복감염 면역성이 생긴다. 바이러스 감염의 종류 급성감염 : 들어가자마자 용균해서 바이러스를 방출시킨다. 비리온을 방출시킨다. 잠복감염 : 유전체는 존재하지만 세포가 죽지않음. 비리온을 방출시키지 않는다. 만성감염 : 평생 갖고 간다. 비리온 조금씩 방출 암세포 유도 : 바이러스가 암유발 유전자를 가지고와서 우리의 세포가 암으로 변형 종양억제유전자인 Rb, p5..
Strassen Algorithm
2020. 4. 17. 12:57
🕶 Algorithm/알고리즘
행렬의 곱셈 크기가 n x n인 두 행렬 A와B의 곱을 C로 나타내고자 한다. 의 원소를 라 하고, 는 가로 는 세로를 나타낸다. B와 C도 동일하게 표시한다. 행렬의 곱셈을 다음과 같이 표현할 수 있다. C하나의 원소를 구하는데 드는 비용은, 곱셈 번과 덧셈 번이다. 따라서, C 전체를 구할 경우 C의 크기는 n x n 이므로 곱셈을 번 그리고 덧셈을 번하게 된다. 따라서, 두행렬을 구하는 복잡도는 이 된다. 알고리즘 A와 B를 체 F에 대한 정사각행렬이라고 하자. 두 행렬의 곱 C는 다음과 같다. 만약 A와 B가 2ⁿ × 2ⁿ 꼴의 크기가 아니라면 먼저 모자라는 행과 열을 0으로 채운다. 이 경우 행렬 곱셈이 끝난 뒤 행렬에서 필요한 부분만 다시 잘라 내야 한다. 이제 A, B, C를 같은 크기의 정..
유전공학 8장 (2), 9장 - 유전자 및 유전체 구조 연구
2020. 4. 16. 11:47
🧬 Bio/유전공학
PCR Denaturation 95 ℃ 1 min DNA 분리 Annealing 50 ℃ - 60 ℃ 1 min 온도를 낮추어 primer가 서열 말단에 결합 Polymerization 72 ℃ 2 min Taq DNA polymerase가 주형 DNA의 상보적인 DNA 합성 2^(n-2) : 3번째 주기가 되어서야 비로소 내가 원하는 가닥 2개가 나온다. 30 Cycle 후 : 2^28 Annealing 온도 맞추기 염기 갯수를 센다. 두가닥이 헤어지는 온도 = Tm = [4 x (G+C)] + [2 x (A+T)] ℃ Annealing 온도 = Tm - (1~2℃) 1) Labelling with a biotinylated nucleotide Avidin이라 불리우는 단백질과 높은 친화도를 가진 유기..
미생물학 4장 (3) - 박테리오페이즈
2020. 4. 15. 14:01
🧬 Bio/미생물학
바이러스의 핵산 대부분의 세균바이러스는 dsDNA를 갖는다. 대부분의 RNA바이러스는 ssRNA를 갖는다. 대부분의 식물바이러스는 ssRNA를 갖는다. 인플루엔자, 사스, AIDS는 ssRNA를 갖는다. 대부분의 RNA바이러스는 분절유전체를 갖는다. 숙주 용균에 필요한 단백질 홀린 : 원형질막에 구멍을 내게 한다. 라이소자임 : 펩티도글리칸을 분해한다. 스파이크 단백질 = 페플로머 라고도 한다. 바이러스의 증식 흡착 → 침투 → 껍질 벗기 → 합성,복제 → 조립 → 방출 흡착 : 바이러스의 스파이크가 세포의 수용체와 결합 그람 음성 : 지질다당체가 수용체로 작용 그람 양성 : 테이코산, 선모, 편모가 수용체로 작용 동물바이러스 : 지질뗏목(lipid raft)가 수용체로 작용 침투 : 바이러스가 세포막에..
Homework_W5
2020. 4. 14. 12:09
📌 java/Object-oriented Programming
Submit your assignment using the following file format: LabNumber_StudentName_Student_ID.zip Example: Lab5_Hongkildong_201620505.zip The zip file will contain two types of files, namely: 1) report file with file format “Report_Lab number” (eg. report_5) to answer theory questions and to write the screen shot that display the output of your program 2) Source code file that contains classes to ans..
06. Inter-Process Communication
2020. 4. 14. 11:02
🚦 Server/Operating System
IPC : 프로세스들 간의 데이터 및 정보를 주고 받기 위한 메커니즘 커널에서 IPC를 위한 도구를 제공하며, System call 의 형태로 프로세스에게 제공된다. IPC에는 두가지 모델이 있다. Shared Memory Message Passing Shared Memory : 운영체제야 단톡방 파줘! 두개 이상의 프로세스들이 주소 공간의 일부를 공유하며, Read, Wirte를 통해 통신을 수행한다. Shared Memory가 설정되면 커널의 관여없이 진행된다. 장점 : 운영체제의 관여없이, 커널의 관여없이 메모리를 직접 사용하여 속도가 빠르다. 단점 : 여러 프로세스가 사용하므로 구현이 어렵고 관리가 힘들다. (부록) IPC를 많이한다고 context switching이 많이 일어나진 않는다. (부..
유전공학 7장 (2), 8장 - 특정 유전자의 클론을 얻는 방법
2020. 4. 13. 12:36
🧬 Bio/유전공학
어떻게 내가 원하는 Clone을 고를 것인가? Direct Selection Gene Library = Clone Library cosmid에 담고 packaging하여 만든다. cDNA Library 염색체 서열은 암호화 부위만 발현된다. 발현이 안되는 유전자는 Silent gene이다. DNA가 아니라 mRNA를 이용하여 발현되는 유전자들만 담는 Library Expression Library : 단백질까지 만들어지는 Library cDNA cloning : mRNA는 cDNA 합성에 의해 DNA로 전환될 수 있다. First strand synthesis : mRNA의 poly(A) tail에 oligo(dT) primer를 결합시킨다. 역전사효소(Reverse transcriptase) 첨가 RN..
java - try, catch
2020. 4. 10. 21:57
📌 java/java
객체 지향 이전까지가 프로그램을 동작하게 하는 법이라면 객체 지향은 웅장한 소프트웨어를 만들기 위한 방법이라고 할 수 있다. 그리고 필자는 이러한 지식을 성공하기 위한 지식이라고 부르고 싶다. 지금부터 배울 것은 예외라는 것이다. 예외는 실패하지 않는 법에 대한 수업이다. 아무리 좋은 기획, 좋은 구조 그리고 높은 성능을 가진 소프트웨어라도 심각한 오류나 보안 약점으로 인해서 모든 것을 잃어버릴 수 있다. 안타까운 것은 이러한 문제들이 소를 잃고 나서야 부각된다는 점이다. 어찌 보면 이것은 자연스러운 인간의 마음일 것이다. 또 그렇기 때문에 탁월한 성취라는 것이 흔치 않은 것이기도 할 것이다. 필자는 어렸을 때 합기도를 다녔다. 합기도에서 제일 처음 배우는 것은 무엇일까? 발차기일까? 호신술일까? 아니다..
미생물학 4장 (2) - 인플루엔자 바이러스
2020. 4. 10. 16:11
🧬 Bio/미생물학
코로나 바이러스 ACE2 : angiotensin 자르는 효소, 코로나의 수용체 역할 하는 단백질 스파이크 단백질 당단백질 sugar chain : 인체의 면역시스템 피해가는 기작 ACE2 의 binding interface에 붙는다. ACE2 와 binding 일어나는 부위 : 스파이크 단백질의 윗부분 원형질막과 융합이 일어나는 부위 : 스파이크 단백질의 뿌리부분 인플루엔자 바이러스 외피 O single strand RNA가 분절되어 있다 = 분절유전체 single strand RNA를 나선형캡시드가 감싸고 있다. 나선형캡시드 -> 유연성이 높다 -> 형태다형성 스파이크 단백질 2가지 헤마글루티닌 (H) : 적혈구 응집소 : 적혈구를 응집시킬 수 있다. (항원-항체) 시알산 결합시키는 단백질 세포에 들..
