david의 CS Blog

https://www.acmicpc.net/problem/18251 18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 www.acmicpc.net 노드의 개수와 각각의 노드의 가중치를 입력받고 포화이진트리 모양을 만들었을 때 직사각형 영역을 그려서 영역 내에 있는 가중치들의 합을 최대로 만드는 문제이다. 만약 노드들의 좌표가 주어져 있다면 문제처럼 해결할 수 있을 것이다. 따라서 우리는 노드들의 좌표를 정해줄 것이다. 노드들의 $x$좌표는 트리를 전위 순회하는 순서로 ..

LCS란? 두 문자열이 있을 때 최장 공통 부분 수열(공통되는 문자열의 최대 길이)을 구하는 문제이다. 예를 들어 두 문자열 ACAYKP와 CAPCAK의 LCS는 ACAYKP, CAPCAK => ACAK이므로 4이다. 이는 간단한 dp로 풀 수 있는데, 두 문자열 a, b에 대하여 배열 $dp[i][j]$를 첫 번째 문자열 a의 구간 [ i, 끝 ], 두 번째 문자열 b의 구간 [ j, 끝 ]에 속하는 LCS 길이라고 정의하면 i) a[i]와 b[j]가 같을 때: $dp(i, j)=dp(i+1, j+1)+1$ ii) 같지 않을 때: $dp(i, j)=max( dp(i+1, j), dp(i, j+1) )$ 라고 할 수 있다. 탑다운으로 푼 코드 #include using namespace std; stri..