백준 5582번 공통 부분 문자열 - C++ 풀이
1. dp(p, q) = S[p...]와 T[q...]가 앞에서부터 일치하는 최대 글자 수 2. S[p] = T[q]인 경우 dp(p, q) = 1 + dp(p+1, q+1)이고, 아닌 경우 0이다. 3. dp(p, q)의 최댓값이 최장 공통부분 문자열의 길이이다. 1. dp(p, q) = S[p...]와 T[q...]가 앞에서부터 일치하는 최대 글자 수 dp(p, q)를 위와 같이 정의하자. 2. S[p] = T[q]인 경우 dp(p, q) = 1 + dp(p+1, q+1)이고, 아닌 경우 0이다. S[p] = T[q]인 경우, 그다음 글자를 비교해야 하므로 dp(p, q) = 1 + dp(p+1, q+1)이 된다. dp(p, q)는 "앞에서부터" 일치하는 최대 글자 수이므로, S[p] != T[q]인..
2022. 8. 4.
백준 5214번 환승 - C++ 풀이
1. 하이퍼 튜브도 노드로 생각한다. 2. 일반 노드 -> 하이퍼 튜브 노드로 가는 간선의 가중치는 0으로 처리한다. 3. BFS를 이용해 1번 정점과 N번 정점 사이의 거리를 구한다. 1. 하이퍼튜브도 노드로 생각한다. 하나의 하이퍼튜브로 연결된 K개의 노드들을 전부 간선으로 이어주려면 O(KM^2)의 시간 복잡도와 공간 복잡도가 필요하다. K, M이 최대 1,000이므로 이 방법은 사용할 수 없다. 대신 하이퍼 튜브를 가상의 노드로 생각하는 방법을 사용한다. 하이퍼 튜브 H로 노드 1, 2, 3이 연결되어있다면 1, 2, 3번 노드 사이에 간선을 추가하지 않고 H번 노드와 각각 1, 2, 3번 노드로 가는 간선 3개 H-1, H-2, H-3만 추가해준다. 결과적으로 1, 2, 3번 노드 사이에 이동이..
2022. 8. 1.
