본문 바로가기

LCs2

[백준/C++] 10838. 트리 문제 https://www.acmicpc.net/problem/10838 N개의 노드로 구성된 루트가 있는 트리가 다음과 같이 주어진다. 각 노드는 0부터 N-1까지의 번호로 구별되고, 0번 노드는 루트 노드이고, 나머지 노드 각각은 0번 노드의 자식 노드이다. 트리에 적용할 수 있는 연산은 세 종류이며, 이를 통해 트리의 모양을 바꾸거나 트리 에지에 색칠을 할 수 있다. 각 연산과 그 의미는 다음과 같다. paint(a, b, c): a번 노드와 b번 노드를 잇는 최단 경로를 찾은 후, 경로 상에 있는 모든 에지를 색깔 c로 칠한다. move(a, b): a번 노드의 부모 노드를 b번 노드로 바꾼다. 단, b번 노드는 a번 노드를 루트로 하는 부트리(subtree)에 속하지 않는다. 부모 노드를 바꾸기.. 2021. 7. 20.

[알고리즘 스터디] 백준 #9251 LCS 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. => 연속하지 않아도 된다는 것이 포인트. 풀이 2차원 cache를 이용한 DP 방식으로 풀면 된다. 말로 풀어 쓴 것은 이해하기 힘드므로 그림을 그려보았다. s1 = ACAYKP s2 = CAPCAK 를 입력했을 때 cache의 모습이다. cache[i][j]에는 s1의 i 번째와 s2의 j 번째가 같을 때 값이 채워진다. (같지 않은 경우에는 0이 채워진다) 둘이 같을 때, 그냥 1을 채우는 것이 아니라 지난 구역에서 가장 큰 값+1을 채운다. 첫 번째 그림에서 빨.. 2020. 4. 19.

이전 1 다음

티스토리툴바