PS/백준

https://www.acmicpc.net/problem/12919 S에서 T로 진행되도록 하면 종단점을 설정하는 것이 어려워T에서 S로 가도록 했다. BFS 문제 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;//A//BA q = new LinkedList(); q.add(T); while(!q.isEmpty()){ String str = q.poll(); if(S.length() > str.length()){ ..

https://www.acmicpc.net/problem/4179 불이 여러개가 존재한다는 것을 잘 생각해야 하는 문제. BFS 사용 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br..

Union-Find 알고리즘 유니온 파인드 알고리즘을 사용하는 문제이다.오랜만에 유니온 파인드를 사용한 것 같다. 이 문제는 연결을 끊거나 연결을 생성함으로 하나의 트리를 형성하는 것이다. 따라서, 입력받을 때 사이클이 존재한다면 해당 연결을 끊어야 하므로, 값을 증가시켜주고만약, 연결이 끊어져있는 곳이 있다면 이어줘야 하므로 union으로 합처준 뒤 값을 증가시킨다. 이때, 나는 1(최소값)으로 유니온 파인드가 진행되게 했으므로, 1이 아닌 경우 이어주게 해줬다.  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public clas..

문제를 올바르게 이해하는 것이 중요하다. 시간복잡도BFS를 Q번 반복하는 문제이다. 인접리스트 BFS의 시간복잡도는 통상적으로 O(V+E)">O(V+E)이므로, 시간복잡도는 O(Q×(V+E))">O(Q×(V+E))가 된다. V와 E는 각각 최대 5000이고, Q는 최대 5000이다.(5000+5000)×5000=104×5×103=5×107<108">(5000+5000)×5000 10^8 == 100000000(1억)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class BOJ1..

# 8 3# 1 5 4 6 2 1 3 7# [1, 1, 2, 3, 4, 5, 6, 7]import sysinput = sys.stdin.readlinedef check(target): global arr, M now_min = now_max = arr[0] count = 1 for i in range(len(arr)): now_min = min(now_min, arr[i]) now_max = max(now_max, arr[i]) if now_max - now_min > target: count += 1 now_max = now_min = arr[i] # print("count", count, targe..

# 5# 3 5 2 5 9## 2 3 5 5 9#import sysinput = sys.stdin.readlineT = int(input().rstrip())nums = list(map(int, input().split()))nums.sort()result = sys.maxsizefor i in range(len(nums)): for j in range(i + 3, len(nums)): l = i + 1 r = j - 1 while l abs(temp): result = abs(temp) if temp