0과 1의 쉼터

[백준 03584] 가장 가까운 공통 조상 [Java]

문제https://www.acmicpc.net/problem/3584풀이문제에서 주어지는 간선이 부모-자식 관계를 나타내고 있기 때문에 별도의 알고리즘 없이 dfs으로 선형탐색하면 된다. 우선 정점 u에 대해 루트 노드까지 탐색하며 방문 표시를 해주자.정점 v에 대해 루트 노드까지 방문하지 않은 노드까지 탐색하면 된다.소스코드보기

문제https://www.acmicpc.net/problem/2533풀이우선, 주어지는 루트가 없으며, 어디서 탐색해도 상관없다.그래프를 구성 후 dfs를 진행하자. 얼리 어답터의 수가 최소가 되도록 만드는 방법에 대해 알아보자.맨 처음 리프노드는 자기 자신이 얼리 어답터라고 가정해야 한다.하지만, 부모 노드가 존재한다면 리프 노드는 얼리 어답터가 아닌 상태가 정답이다.여기서 dp는 두 상태(EARAY, GENERAL)에 대해 고려해야 한다.dp[i][j] : 상태가 i일때 j ~ N에 필요한 최소 얼리 어답터의 수dfs를 통해 방문을 진행하면 방문 표시와 함께 현재 정점이 얼리 어답터인 경우를 세주자.리프 노드까지 도달 후 리프 노드들이 얼리 어답터라고 표시된 후 부모 노드로 돌아와서 부모 노드의 두 ..

문제https://www.acmicpc.net/problem/11437풀이DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.이를 위해서 양방향 그래프를 구성해야 합니다.문제에서 트리의 루트는 1번이라 언급되어 있으니, 1번 정점부터DFS를 통해 모든 노드의 부모 노드와, 깊이를 구해주면 된다.이제 LCA를 구해야 하는 두 노드 u, v에 대해 깊이가 다르다면 부모 노드로 올라가며 깊이를 맞춰주고,깊이가 동일한 두 노드의 부모노드가 같을 때까지, 즉 LCA를 찾아주면 된다.소스코드보기

문제https://www.acmicpc.net/problem/3584풀이주어지는 트리에 대해 두 정점의 공통 조상을 찾는 문제다.이미 부모-자식에 대한 정보가 주어지므로, 입력과 동시에 parent를 바로 구성할 수 있다. 공통 조상을 구해야하는 두 정점 중 한 정점으로부터 루트노드까지 방문해주고,다른 정점도 동일하게 방문하지 않은 부모 노드를 따라 방문하면 된다.이미 방문한 적 있는 부모노드는 공통 조상 노드이므로 탐색을 중단하고 반환해주면 된다.소스코드보기

문제https://www.acmicpc.net/problem/2294풀이N가지 종류의 동전이 주어질 때, 동전의 합이 K가 되는 최소 개수를 구하는 문제다.N은 최대 100이므로, 모든 동전에 대해 K를 만들어보는 경우를 전부 계산해볼 수 있다.dp[i] : 현재까지 살펴본 동전들로 i원을 만들기 위한 최소 개수우선 K의 최대는 10,000이므로 dp를 10,001, dp[0] = 0으로 초기화하자.이제 입력받은 동전에 대해 최소 동전 개수를 갱신하면 된다.범위 coin ~ K에 대해 현재 동전의 액수를 뺀 기록( dp[i - coin] )에 현재 동전 더하는 수가 적은 경우로 갱신해주면 된다. 만약 dp[K]가 초기값인 10,001이라면 K를 만드는 경우의 수가 존재하지 않는 경우이므로 -1을 출력하자..

문제https://www.acmicpc.net/problem/1520풀이최대 500 X 500 크기의 보드에 대해 상하좌우 움직이면서 이전 위치보다 숫자가 작은 방향으로만 움직여 왼쪽 위에서 오른쪽 아래로 도착하는 경우의 수를 구하는 문제다.단순히 그래프 탐색으로 모든 경우의 수를 탐색하면 시간초과가 발생한다.중복 방문을 하지 않으면서도, 모든 경우의 수를 계산해야 한다.DP[i][j] = (i, j)에서 도착지 (M - 1, N - 1)까지 이동하는 경우의 수우선 입력을 받자.모든 지점이 도착지에 도달한다는 보장이 없으므로, dp는 -1로 초기화하자.dfs를 하며 만약 도착지에 도달했다면 1을. 이미 방문한 곳이라면 dp[x][y]를 반환해주자.그게 아니라면 새로운 탐색을 시작해야 하므로 dp[x][y..

문제https://www.acmicpc.net/problem/6593풀이L, R, C로 이루어진 직육면체에서 상하좌우, 위, 아래로만 이동하며 출발지 S에서 도착지 E로 도착하는데 걸리는 최단 시간을 구하는 문제다.BFS를 3차원으로 확장하면 되는 기본 문제다.우선 시작 전 문자나 상태를 정의해주자.상위 그래프 문제로 갈수록 이처럼 문제에서 주어지는 문자들을 자신의 언어로 변환해주는게 실수를 방지하는데 도움이 된다.L, R, C가 모두 0이 아닐 때 까지 입력을 받으며 탐색을 진행하면 된다.그래프 정보를 입력받으며 벽을 표시해주고, 시작점과 종료점의 위치를 파악해주자.(sl, sr, sc, el, er, ec)각 층마다 한 줄 공백 입력이 주어진다는 점에 유의하자.기본 BFS를 3차원으로 확장해 구현해주..

문제https://www.acmicpc.net/problem/2482풀이바텀업보다 탑다운 방식으로 접근하면 쉬워지는 문제다. 원형을 이루는 N개의 색상환 표에 대해 인접하지 않은 색을 K개 선택하는 경우의 수를 구해야 한다.경우의 수가 너무 커지지 않게 1e9 + 3으로 나눈 나머지를 출력해야 한다. dp[N][K] : N개의 색상에 대해 인접하지 않는 K개의 색을 선택하는 경우의 수문제를 단순화해보자. 다음이 성립한다.dp[N][1] = Nif K > N / 2, dp[N][K] = 0문제에서 주어진 그림을 예시로 설명하겠다.우선 빨강색(N번째)을 선택해보자.N번째 색을 선택할 때, 인접한 N - 1번(다홍색)은 선택할 수 없다. N - 2번(주황)을 선택해야하고, 이 때 K - 1개의 색을 선택하면 ..

문제https://www.acmicpc.net/problem/2011풀이대문자 알파벳을 1 ~ 26으로 암호화한 문자열에 대해 해석 가능한 경우의 수를 출력하는 문제다.우선 주어진 입력의 유효성부터 판별해보자.입력이 0인 경우 암호를 해석할 수 없다. 0을 출력하고 종료하자. 이제 점화식을 세워보자.dp[i] : i번째 까지 해석 가능한 경우의 수N이 1의 자리인 경우, dp[1] = 1탐색 대상의 수( N[i - 1] )가 0보다 크다면, 기존 경우의 수만큼 가질 수 있다. dp[i] = dp[i - 1]N[i - 2], N[i - 1]로 이루어진 두 자릿수가 10 이상, 26이하라면, 두 수를 하나의 수로 볼 수 있다. dp[i] = (dp[i] + dp[i - 2]) % MOD소스코드보기

문제어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.예를 들어, {1,1,5}는 {3,1,4,1,5,9}의 부분 수열이지만, {1,5,1}의 부분 수열은 아닙니다.또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.길이가 0인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.양의 정수로 이루어진 길이가 N인 수열 {A1,⋯,AN}이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 M인 수열 {B..