αλγριθμο

문제 www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 풀이 LCA(Lowest Common Ancestor)를 사용합니다. 먼저, 다음 4개의 배열을 만듭니다: \(graph[i][j].x,\ graph[i][j].y:\) \(i\)의 \(j\)번째 자식 노드와 그 노드까지의 거리. \(par[i][j]:\) \(i\)의 \(2^j\)번째 조상. \(depth[i]:\) \(i\)의 깊이. \(dist[i]:\) 루트로부터 \(i\)까지의 거리. 트..

문제 www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 LCA(Lowest Common Ancestor)를 사용합니다. 사실 이번 문제는 전에 풀었던 11438 - LCA 2문제와 거의 다를 것이 없습니다. 다만, 다른 점이라면 루트노드가 따로 주어지지 않기 때문에 직접 찾아야한다는 것입니다. 하지만 그건 어렵지 않습니다. ​ 먼저, 각 테스트케이스별 간선들의 정보를 입력받은 다음 노드 하나를 무작위로 ..

문제 www.acmicpc.net/problem/1949 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 풀이 트리DP를 사용합니다. 트리가 주어졌을 때, 배열 \(dp\)를 다음 두 가지 경우로 생각해 정의할 수 있습니다: \(dp[i][0]:\) \(i\)가 우수 마을이 아닐 경우의 마을 주민 수 합의 최대값. \(dp[i][1]:\) \(i\)가 우수 마을일 경우의 마을 주민 수 합의 최대값. \(i\)의 자식 노드들을 \(c_{1}, c_{2}, c_{3}, ... , c_{m}\)이라..

문제 www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 풀이 트리DP를 사용합니다. 트리가 주어졌을 때, 배열 \(dp\)를 다음과 같이 정의할 수 있습니다: \(dp[i]:\) \(i\)를 루트로 하는 서브트리에 속한 정점의 수. 트리를 순회하면서 \(i\)의 자식 노드들을 \(c_{1}, c_{2}, c_{3}, ... , c_{m}\)이라고 할 때, \(dp[i]\)에 다음 값을 저장합니다: ..

문제 www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 문제 제목 그대로 LCA(Lowest Common Ancestor)를 사용합니다. 각 노드의 자식 정보를 담은 배열 \(graph\)와 각 노드의 조상 정보를 담은 배열 \(par\), 그리고 각 노드의 깊이를 담은 배열 \(depth\)가 있을 때 주어진 트리를 순회하면서 다음 작업을 수행합니다. 현재 노드를 \(i\)라고 할 때: \(par[i][j]\)에 \(i\)의 \(2^j\)번째 ..

문제 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 DP를 사용합니다. 주어진 수열 \(A\)에 대하여 배열 \(dp\)를 다음과 같이 정의할 수 있습니다: \(dp[i][j]:\) \(A_{i}\)부터 \(A_{j}\)까지가 팰린드롬인지 아닌지 여부. (팰린드롬이면 1, 팰린드롬이 아니면 0) 다음 수열을 보겠습니다. 1 2 1 3 1 2 1 여기서 첫 번째 수 부터 마지막 수까지는 팰린드롬입니다. 또한, 2번째부터 6번째까지, 3번째부터 5번째까지, 그리고 4번째 모두 팰..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 DP를 사용합니다. 바이토닉 수열은 올라갔다 내려갈 수 있고, 올라가기만 할 수도 있으며, 내려가기만 할 수도 있습니다. 하지만, 내려갔다 올라갈 수는 없습니다. 그러므로, 두 가지 경우를 생각해 수열 \(A\)가 주어졌을 때 배열 \(dp\)를 다음과 같이 정의할 수 있습니다: \(dp[i][0]:\) \(A_{i}\)까지의 수열 중 바이토닉 부분 수열이 오름차순일 때 그 수열의 길이의 최대값. \(dp..

안녕하세요, 이번에 티스토리 블로그를 시작하게 된 GC망고라고 합니다. 저는 프로그래밍 알고리즘을 공부하는 학생이구요, 백준 같은 알고리즘 문제의 풀이를 올릴 예정입니다. 원래는 네이버 블로그를 이용했지만 알고리즘 고수분들이 다 티스토리를 하셔서 저도 여기로 이사왔습니다. ^^7 계정: BOJ: gcmango solved.ac: gcmango Codeforces: GCMango Github: GCMango