david의 CS Blog 자세히보기

백준 문제 풀이 3

BOJ 18251 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

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

BOJ 11000 강의실 배정

greedy로 회의 정렬 + 우선순위 큐를 이용해 강의실 개수 관리 우선순위 큐에 들어있는 원소를 ii번째 회의실을 마지막에 사용하는 시간이라고 정의하고 i번째 회의실에서 회의를 이어서 할 수 있다면 그 값을 바꾼다. #include #include #include #include using namespace std; struct info{ int s, e; }; int n; vector v; bool cmp(const info &a, const info &b) { return a.s==b.s ? a.e n; for(int i=0; i> a >> b; v.push_back({a, b}); } sort(v.begin(), v.end(), cmp); priority_queue pq; pq.push(-v[0..

[ dp ] LCS(Longest Common Substring)

Longest Common Substring  LCS(Longest Common Substring)은 두 문자열이 있을 때, 두 문자열의 최장 공통 부분 수열(공통되는 문자열 중, 최대 길이의 문자열)을 구하는 문제이다. 예를 들어 두 문자열 ACAYKP와 CAPCAK의 LCS는 ACAYKP, CAPCAK => ACAK임을 알 수 있다.  이는 간단한 dp로 풀 수 있는데, 두 문자열 a, b에 대하여 항 dp[i][j]dp[i][j]를 '첫 번째 문자열 a의 구간 [ i, 끝 ], 두 번째 문자열 b의 구간 [ j, 끝 ]에 속하는 LCS 길이'라고 정의하면 i) a[i]와 b[j]가 같을 때: dp(i,j)=dp(i+1,j+1)+1dp(i,j)=dp(i+1,j+1)+1ii) 같지 않을 때: $dp(i, j)=max( dp(i+1, j), d..