Hello, There

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 점화식을 세워서 간단하게 해결할 수 있다. N = 5 인 경우 를 예를 들어 보면, 5개을 타일을 채우기 전, 4개의 타일을 채웠다고 생각해보면, 남은 칸은 1*2 한칸밖에 없어 선택지가 없다. 따라서 A[5] = A[4] + ??? 임을 알 수 있다. 3개의 타일을 채웠다고 생각해보면 가로로 두개를 쌓는 방법과, 세로로 두개를 채우는 방법이 있다. 그런데 세로로 두개를 채우는 방법은 이미 A[4]에 포함되어있으므로 ..

https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 5개 중 3개를 뽑는 조합의 수는 4개 중 2개를 뽑는 조합의 수와 4개중 3개를 뽑는 조합의 수의 합과 같다. 5개 중 3개를 선택할 때, 앞선 4개는 모두 선택되거나 선택되지 않았을 경우, 마지막 남은 1개 역시 선택되거나 선택되지 않는 두 가지 경우의 수 뿐이다. 마지막 남은 1개가 선택되는 경우는 앞선 4개 중 2개를 뽑은 경우이며, 선택되지 않은 경우는 앞선 4개 중 3개를 뽑은 경우이다. 따라서 i개중 j개를 뽑는 경우의 수를 arr[i][j]로 배열에서 나타낸..

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제에서 루트노드와 노드간의 연결 관계는 알려주었으나 누가 부모노드인지, 노드의 깊이인지 파악이 되지 않는다. 따라서 BFS를 통해 그래프를 탐색하여 부모노드, 깊이를 파악한다. 이후 두 노드 a, b에서 출발 하여 공통 조상 노드를 파악할 때는, 두 노드의 깊이가 같다면 두 노드가 같은 곳에서 만날 때 까지 함께 위로 올라가고 (위로 올라가는 것은 해당 노드를 해당노드의 부모노드로 바꿔치기..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net import java.io.*; import java.util.*; public class Main { static int T; static int N; static int[] parent; //i번 노드의 부모 인덱스를 저장한 배열. static boolean[] visit; public static void main(String[] args)..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제에서 말하는 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리로, 최소 신장 트리 (MST)를 말한다. 그래프에서 모든 노드를 연결 시, 사용되는 에지들의 가중치 합이 최소인 경우, 일단 모든 노드를 연결하였기 때문에 N개의 노드가 있을 경우, N - 1개의 에지를 사용하게 된다. 만약 ..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 최소비용 배열 전체를 구하는 문제로, 플로이드-와샬 알고리즘을 적용하여 푼다. 전체 경로가 최단 경로이기 위해서는 전체 경로를 이루는 부분 경로들 역시 최단 경로를 이뤄야 한다는 점을 이용한다. 다익스트라는 인접리스트를, 벨만-포드는 간선배열을 활용했지만 플로이드-워셜은 인접행렬을 통해 문제를 푼다. 인접 행렬에 i노드에서 j노드까지의 가중치를 표시하고, 간선이 연결되지 않은 경우에는 무한대를 표..