https://www.acmicpc.net/problem/4315 재미있는 트리 연습 문제아이디어 + 구현 모두 깐깐한 문제였다.각 노드가 갖고 있는 구슬 개수가 모두 1개가 되도록 할 때 구슬을 옮기는 최소 횟수를 구하는 문제이다. 내가 생각한 풀이 흐름은 다음과 같다. 1. 전체 트리를 DFS 돌면서 현재 자신을 root 로 하는 서브트리에 대해 이 서브 트리가 가지고 있는 모든 구슬의 개수, 필요한 구슬의 개수를 구한다. 만약 가지고 있는 구슬이 필요한 구슬보다 많다면, 그 차이를 return 하여 부모 노드로 여분 구슬을 넘긴다. DFS 실행이 끝나면 모든 노드는 자신을 루트로 하는 서브트리 모두를 채울 수 있도록 딱 맞게 구슬을 갖고 있거나, 모자라거나 둘 중 하나의 상태가 된다. 2. 두번째로..

https://www.acmicpc.net/problem/4436 가볍게 브론즈 문제를 하나 풀어봤다. (솔브드 마라톤 시스템 추천 문제)모든 k 값을 1부터 다 시도해보면서 브루트포스로 구현하면 되는 문제다. 근데 푸는데 생각보다 시간이 오래 걸렸다.. 그 이유는 set 연산자를 착각해서 그렇다.나는 s.union() 메서드가 기존 집합에 자동적으로 더해주는 줄 알았는데, 기존 집합이 변하지 않고, 새로운 합집합을 반환한다는 점을 프린트로 찍으면서 디버깅하느라 10분정도 걸려서 푼 것 같다.. 이 문제 덕분에 파이썬 집합 연산은 새로운 집합을 반환하므로 기존 집합을 덮어써야 한다는 것을 깨달을 수 있었다. import sysinput = sys.stdin.readlinewhile True: try..

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개씩 정렬하기 메모리 공간 최적화슬라이딩 윈도우분할 정복  ( 심화 내용이라는 느낌이 들어서 정리를 후순위로 미룸 )