Stitchhhh

https://www.acmicpc.net/problem/15681  이번 문제는 하나의 트리에서 서브트리의 루트를 정했을 때 그 트리에 포함된 정점을 출력하는 문제입니다. 기본적인 트리 문제에 조금 더 생각을 하면 될 것 같습니다. 매번 서브 트리 루트가 정해질 때 마다 계산을 하기에는 정점의 수가 최대 500,000 쿼리의 수가 500,000 이고 트리 전체는 변하지 않기 때문에 dp를 통해 미리 계산을 하는 식으로 해결을 하였습니다. import java.io.*;import java.util.*;public class Backjoon_15681_트리와_쿼리 { public static void main(String[] args) throws IOException { Buffere..

https://www.acmicpc.net/problem/2623  이번 알고리즘은 위상정렬입니다. 위상 정렬은 그래프에서 방향을 가지는 간선으로 이루어져 있으며 사이클이 없는 것을 말합니다.간단하게 설명을 하자면 A를 하기 위해서 B를 우선 해야 한다는 가정이 있다면 A, B와의 관계를 B -> A로 나타낼 수 있습니다. 문제에서는 위의 개념만 적용하면 바로 풀이를 할 수 있습니다. 서로의 관계를 M번 만큼 제시하는 것 말고는 크게 신경 써야 하는 부분은 없습니다. 우선 시 하는 것이 없는 것을 먼저 큐로 넣고 큐에서 나오면서 자신을 필요로 하는 정점을 가져오고 이 정점의 우선 시 하는 갯수에 -1을 하면 됩니다. 여기서 0이 되면 우선 시 하는 정점을 모두 진행했기 때문에 큐에 넣어주는 방식으로 해결..

https://www.acmicpc.net/problem/21276 해당 문제에서는 제일 먼저 가문의 개수와 가문의 시조를 구해야 합니다. 가문의 개수를 구하는 방법은 자신을 바라보는 정점이 없는 정점 즉 루트가 몇 개인지 확인하고 그 값을 출력을 하면 됩니다. 그래서 가문의 시조를 관리하는 리스트를 만들어 이를 해결하여습니다. 위 말을 조금 더 쉽게 생각하면 부모가 있어야 자식이 있기 때문에 부모 -> 자식 관계로 생각을 하면 합니다. 즉 최상위 조상은 누구도 자신을 바라보지 않습니다. 그리고 자식들을 출력을 해야하는데 이 또한 리스트를 활용하여 각 정점마다 자식을 추가 해주었습니다.for(int i = 0 ; i q = new LinkedList(); int idx = map2.get(strArr[..

https://www.acmicpc.net/problem/1647 이번 문제로 MST 알고리즘입니다. 다만 MST에서 살짝 변형을 준 문제라고 생각해도 될 것 같습니다. MST인 경우에는 모든 집을 연결하는 최소한의 간선 합을 구하는 것인데 여기서는 집을 두 개의 집단으로 나눠야 하기 때문에 최소한의 간선들 중 제일 큰 값을 빼면 됩니다. 그러면 A구역 B구역으로 자연스럽게 나누어질 것 입니다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.PriorityQueue;import java.util.StringTokeniz..

https://www.acmicpc.net/problem/1197 이 번에 풀어본 문제의 종류는 MST(최소 신장 트리)입니다. 최소 신장은 주어진 그래프의 부분 그래프 중 모든 정점을 포함하는 트리를 말합니다. 여기서 MST란 이를 최소한의 비용(기존 간선)으로 이루어진 그래프입니다. MST 알고리즘을 풀이는 2가지 대표 알고리즘이 있습니다. 크루스칼 알고리즘과 프림 알고리즘이 존재하는데 크루스칼을 활용해 문제를 풀이해보겠습니다. 크루스칼 알고리즘은 유니온 파인드라는 알고리즘을 사용합니다. 유니온 파인드는 서로의 집합을 확인하는 알고리즘입니다. parent[] 배열을 통해 최상위를 확인하여 서로 같은 집단인지 확인하며 문제를 풀이하면 됩니다. import java.io.BufferedReader;imp..

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Backjoon_14938_서강그라운드 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); ..

https://www.acmicpc.net/problem/21940  이번 알고리즘은 플로이드입니다. 플로이드 알고리즘은 모든 정점 쌍 사이의 최단 거리를 구해주는 알고리즘으로 알려져 있습니다. 위 문제는 정점마다 제일 값이 큰 친구의 집까지 왕복거리를 저장을 하고, 이 저장된 값 중에 제일 최소값을 반환하면 됩니다. 제일 최소값이 여러 개 일 수있으니 리스트로 저장을 하고 반환하면 됩니다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.StringTokenizer;pub..

https://www.acmicpc.net/problem/1238  이번 문제는 다익스트라 문제입니다. 다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구해주는 알고리즘으로 O(ElgE)의 시간복잡도를 가지고 있습니다. 문제를 조금 더 분석해보면 1~N 까지의 정점으로부터 X까지의 최소 거리와 X로부터 1~N 까지의 최소거리의 합 에서 제일 큰 값을 반환하면 됩니다. 정점이 하나로 정해진 것이 아니기 때문에 2차원 배열을 통해 정점을 기준으로 다른 정점을 가는 최소거리를 저장하였습니다. 배열의 형식은 [시작지점][목적지점] 으로 이루어져 있습니다. import java.io.BufferedReader;import java.io.IOException;import java.io...

https://www.acmicpc.net/problem/1504 문제에서는 시작점이 무조건 1, 도착점이 무조건 N으로 되어있으며 경유해야할 정점이 2개 주어집니다. 그래서 케이스로만 확인해보면 다음과 같습니다.1 -> V1 -> V2 -> N1 -> V2 -> V2 -> N그리고 다익스트라 알고리즘을 통해 해당 정점에서 다음 정점까지의 최소거리를 구하면 됩니다.정점 까지의 최대거리는 2억이기 때문에 모든 값을 2억으로 초기화를 해준 후 1번의 경우와 2번의 경우 모두를 계산을 합니다. 1번 계산이나 2번 계산의 결과값이 기존에 설정한 2억이상이면 갈 수 없는 길이 존재하는 것 이기 때문에 조건을 처리해주면 됩니다. import java.io.BufferedReader;import java.io.IOE..

https://www.acmicpc.net/problem/2457  이번 문제는 그리디 알고리즘입니다. 문제에서 3월1일부터 11월 30일까지는 꽃이 하나 이상 피어있어야 된다고 했으므로 초기값은3월1일을 포함하여 이 전까지 핀 꽃 중에 제일 오래사는 꽃이 필요합니다. 그리고 제일 오래사는 꽃을 찾게 된다면 그 꽃이 죽는 날을 기준으로 위 행동을 반복하면 됩니다. 여기서 해당 꽃이 11월 31일까지 살게 된다면 기록했던 꽃의 수를 반환을 하고 최종적으로 11월 31일까지 못갔다면 0을 반환하면 됩니다. 그리고 만약 꽃이 없는 기간이 생기게 되면 이 또한 바로 0을 반환하면 됩니다. import java.io.BufferedReader;import java.io.IOException;import java...