https://www.acmicpc.net/problem/11437 워냑 유명한 유형이다보니 (나도 풀어보지는 않았지만 이 유형에 대해서 들어봤었다.) 정형화된 알고리즘이 있을 것 같은데, 우선 스스로의 고민으로 먼저 풀어보기로 했다. 어떤 트리가 주어질 때, 임의의 두 노드에 대해 그 두 노드의 최소 공통 조상 노드를 찾는 것이 문제의 요구사항이다.이때 트리의 루트는 1번 노드이다.(나는 이 조건을 못 보고 어떤 루트로 잡든 성립하는 문제인가보다~ 하고 1번 노드를 루트로 잡고 풀었는데, 생각해보면 두 노드 중에 한 노드를 매번 루트로 잡으면 그 노드가 최소 공통 조상이 되어버리니 루트는 정해져있어야 의미있는 문제였다.) 처음에는 특정 노드에서부터 루트를 향해 올라가면서 공통 조상 노드를 찾는 방법을 ..
https://www.acmicpc.net/problem/14442 자바로 한번 구현해봤더니 파이썬의 편리함을 다시 한번 깨닫게 해준 문제... 문제 풀이는 간단하다.(i, j) 위치에 k번의 벽 부수기 횟수가 남은 상태로 도착했을 때, 그때의 최단 이동 경로를 다 저장하면된다.최악의 경우 1000*1000*10 = 1000만 칸의 배열을 채워야 하는데, 2초 시간 제한과 512MB 의 메모리 제한이라면 충분히 채울 수 있다. 만약 이동하려는 칸이 벽이라면 현재 칸에서 남은 벽 부수기 횟수를 1 감소시켜서 이동시키고, 이동하려는 칸이 벽이 아니라면 남은 횟수를 그대로 가져가면서 이동하면 된다. import java.io.BufferedReader;import java.io.IOException;impor..
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점이 나왔고..
