https://www.acmicpc.net/problem/1949 지금까지 푼 트리 DP 문제와 같은 방법으로 풀면 된다.다만 3번 조건이 애매하게 마음 속에 걸렸다.뭔가 직감적으로는 내 풀이가 3번 조건을 자연스럽게 만족하는 정답을 도출할 것 같은데 확실하진 않은 느낌.. 우선 풀이는 다음과 같다.현재 노드를 루트로 하는 서브트리에 대해 현재 노드가 우수마을인 경우, 최적해와 우수마을이 아닌 경우 최적해를 저장하는 DP 테이블을 짜고 다음과 같이 점화식을 세운다. dp[node][우수마을o] = sum( dp[child][우수마을x], ... )dp[node][우수마을x] = sum( max(dp[child][우수마을o], dp[child][우수마을x]), ... ) 부모 노드가 우수마을이 아닌 경우,..

https://www.acmicpc.net/problem/2533 트리 DP 문제DP 테이블을 다음과 같이 정의한다. dp[i][j] = i 번째 노드가 루트인 트리에 대해 이 노드가 얼리어답터 인지 (j = 0) 아닌지 (j = 1) 에 따른 그 트리에서의 얼리어답터 최소 수 점화식은 다음과 같이 쓸 수 있다. dp[i][0] = i 번째 노드가 루트인 트리에 대해 이 노드가 얼리어답터인 경우, 모든 자식노드는 얼리어답터여도 되고, 아니어도 된다. 두 경우를 모두 구해서 최소 값을 취한다. 따라서 sum( min( dp[k][0], dp[k][1] ) ) + 1, ( k 는 직접 연결된 자식 노드들의 번호 ) dp[i][1] = i 번째 노드가 루트인 트리에 대해, 이 노드가 얼리어답터가 아닌 경우, ..

https://www.acmicpc.net/problem/2213 트리를 구성하는 정점에 가중치가 있을 때, 인접하지 않은 정점들로만 구성된 정점의 부분집합에 대해 가중치의 합이 최대가 되는 부분 집합을 구하는 문제이다. 그에 더해 이 문제는 이 가중치의 합의 최댓값에 더해, 그 값이 나오도록 하는 부분 집합의 원소까지 구해야 한다. 이 문제는 트리 DP 로 유명하다.트리는 그 형태가 이미 재귀적이기 때문에 DP 로 표현하기가 매우 좋다. 이 문제의 DP 테이블을 다음과 같이 정의해보자. DP[i][j] = i 번째 노드를 루트로 하는 트리에 대해, 이 노드를 정점에 포함 (j = 0) 또는 포함하지 않을 때 (j = 1) 의 가중치 합의 최댓값 이제 점화식을 세워보면 만약 i 번째 노드를 계산에 포함한..

https://www.acmicpc.net/problem/1135 트리 구조로 이루어진 조직도가 있을 때, 제일 높은 조직의 사람이 자신의 직속 부하들에게 한번에 한 명씩 전화를 돌리며 뉴스를 전파한다.직속 부하들도 전화를 받은 뒤엔 자신의 직속 부하에게 한번에 한 명씩 전화를 돌리며 뉴스를 전파한다.이때 모든 직원들에게 뉴스가 전파되는 최소 시간을 구하는 문제이다. 나는 트리디피와 그리디가 섞인..? 느낌으로 풀었다. (DP보다는 그리디에 가까운 것 같아서 기여할 때는 그리디로만 기여했다.) 문제 이해하기전화를 그냥 돌리면 간선의 수 만큼 시간이 소요되지 않을까? 왜 최소 시간을 구하라고 한 것일까?예제 입력 2번을 보면 알 수 있다. 상사가 1번과 2번 중 어떤 사람에게 먼저 전화를 돌리는지에 따라 ..

지금까지는 어떻게하면 여러개의 DNA 시퀀스에서 공통된 motif 를 찾고, 찾아낸 motif 를 기존 DNA 에서 어떻게 표현할 것인지 (정렬할 것인지) 다양한 방법에 대해 정리하였다. 이번 글부터는 각각의 DNA 조각들을 모아서 하나의 게놈을 만드는 방법을 정리해본다. 아이디어 100권의 책을 파쇄한 뒤, 각 조각들을 잘 조립해서 하나의 페이지를 복원하려고 한다.  각 조각들을 올바르게 조립해서 하나의 페이지로 복원할 때, 각 조각에서 겹치는 부분들을 이용해서 페이지를 복원할 수 있다. DNA 조각들을 모아서 하나의 게놈을 만들 때도 비슷한 방법을 사용하여 복원할 수 있다.이때 이 방법을 위해서 그래프를 정의할 필요가 있다. 그래프는 read fragment 를 정점으로 하고, 두 fragment 사..

Affine Gap 같은 정렬이어도, 왼쪽 것이 더 좋다.어떻게하면 왼쪽처럼 정렬하도록 만들 수 있을까?  여러개 정렬하기한번에 정렬하기 vs 2개씩 정렬하기 메모리 공간 최적화슬라이딩 윈도우분할 정복  ( 심화 내용이라는 느낌이 들어서 정리를 후순위로 미룸 )

지난 글까지는 여러개의 DNA 시퀀스에서 공통 motif (유사한 motif) 를 찾는 방법에 대해 정리하였다.이번 글부터는 지난 글에서 찾아낸 각 DNA 염기 서열 속 motif 들 또는 전체 DNA 염기 서열이 얼마나 유사한지를 확인하기 위해, 정렬하는 방법에 대해 정리한다.   예를 들어, 위 문자열은 사람, 개, 고양이, 돼지의 인슐린 단백질의 아미노산 서열을 나타낸 모습이다.이 서열은 얼마나 유사할까?  유사도를 측정하는 방법 중 하나는 각 문자열을 같은 문자끼리 '정렬' 하는 것이다.위 모습은 4개의 인슐린 단백질 아미노산 염기 서열을 직접 손으로 정렬한 모습을 보여준다.그리고 꽤나 긴 공통 서열이 나타나는 것을 알 수 있다. 그런데 이 공통 서열이 과연 우리가 찾을 수 있는 최적의 서열일까?..

Pruning Trees지난 글에서 정리했던 브루트포스 & Score 함수를 이용한 motif 탐색 알고리즘은 시간이 매우 오래 걸렸다.이는 각 Score 함수의 실행 시간은 짧았지만 motif 조합을 다 해봐야했기 때문에 Score 함수의 호출 횟수가 너무 많았기 때문이다.하지만 모든 경우에 대해 매번 Score 함수를 호출해야만할까? pruning tree 알고리즘을 사용하여 호출 횟수를 줄여보자.이 알고리즘은 현재까지 발견한 최적해와 비교하여, 현재 하려는 계산이 더 최적이 될 것 같지 않을 때 굳이 계산해보지 않고 과감하게 건너뛰는 방법이다. 예를 들어보자.10개의 DNA에서 공통적으로 등장하는 10-mer motif 를 찾으려고 한다.이때 4개 DNA 에 대해서 점수를 계산했더니 17점이 나왔고..

지난 글에서는 초기 코로나 바이러스의 DNA 패턴을 분석하는 방법으로 k-mers 라는 부분 문자열로 나누어서 분석하는 방법을 알아보았다. 지난 글 마지막에서 보았을 때는, 초기 코로나 바이러스의 스파이크 단백질 염기 서열을 알고 있었고, 그 단백질의 염기서열을 코돈으로 번역하여 아미노산 서열을 찾아보았다. 하지만 실제로는 지난 글과 같이 '염기서열을 알고있는' 상태에서 찾는 것이 아니라, 염기 서열 안에서 유전자를 찾아야 하는 상황이 더 많다.만약 우리가 찾아야 하는 유전자의 염기 서열을 모를 때 유전자를 어떻게 찾을 수 있을까? 우리는 모든 유전자가 특정 코돈 (AUG) 으로 시작하고 특정 코돈들 중 하나 (TAA, TAG, TGA) 로 끝나는 것을 알고있다.그렇다면 개시 코돈과 종결 코돈만으로 유전..

FASTA : 생물학적 서열에 대한 공통 포맷 각 FASTA 문자열은 '>' 로 시작하는 header line 으로 시작한다.그 다음에는 여러 줄의 문자열 데이터가 들어오는데,DNA 는 ACGT 로 구성된 문자열이RNA 는 ACGU 로 구성된 문자열이단백질은 ACDEFGHIKLMNOPQRSTUVWY 로 구성된 문자열이 주어진다. 하나의 문자열은 또 다른 header line 을 만나거나 EOF 신호를 만나면 끝난다.따라서 하나의 FASTA 파일에는 여러 시퀀스가 존재할 수 있다.또한 각 시퀀스는 0-index 가 아니라 1-index 형태를 따른다.  예를 들어 SARS-COV-2Wuhan.fasta 파일을 보면 첫 줄에는 > 로 시작하는 헤더라인이 있다.그 다음줄에는 ATCG 로 구성된 DNA 염기서열..