요르딩딩

서로소 집합 자료구조 : 서로수 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 union과 find 연산으로 조작할 수 있다. 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 과정 1. 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다 - A와 B의 루트 노드 A′, B′를 각각 찾는다 - A′를 B′의 부모 노드로 설정한다 2. 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복한다 import java.util.*; public class Main { // 노드의 개수(V)와 간선(Union 연산)의 개수(E) /..

플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산합니다. 2차원 테이블에 최단 거리 정보를 저장합니다. 다이나믹 프로그래밍 유형에 속합니다. 시간복잡도 : O(N^3) = 2차원 리스트를 처리해야 하므로 거쳐가는 N번의 단계에서 매번 O(N^2)의 시간이 소요된다. 점화식 : Dab = min(Dab, Dak + Dkb) 각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인합니다. 비교 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 알고리즘 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우'에 사용할 수 있는 알고리즘 다익스트라 알고리즘은 그리디 알고리즘이고, 플로이드..

원리: 시간복잡도 : O(ElogN) import java.util.*; class Node implements Comparable { private int index; private int distance; public Node(int index, int distance) { this.index = index; this.distance = distance; } public int getIndex() { return this.index; } public int getDistance() { return this.distance; } // 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정 @Override public int compareTo(Node other) { if (this.distance <..

https://hidelookit.tistory.com/195 [백준 14890] 경사로 (자바) 백준 14890번 경사로 (자바) 출처 www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다.. hidelookit.tistory.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static int n, l; ..

이번문제는 문제를 이해하고, 어느정도 해결책까지는 접근할 수 있었으나, 아직 dfs(깊이우선탐색)에 대한 문제를 많이 풀어보지 않았기때문에, dfs관련 문제인지 파악하지 못했던거 같다. dfs는 자주 출제되는 문제유형이니 잘 공부하도록하자. 우선 처음 접근할때는 규칙을 찾으려고 노력했다. 하지만 모두 공통된 규칙을 찾기에는 쉽지 않았다. 찾아보니 dfs문제임을 알 수 있었다. 그 이유는 처음 한 조각을 고르면 4변에 붙일 수 있고, 붙이고 나면 그 다음블록에는 3변에 붙일 수 있고, 그 다음은 3블록 (4X3X3)이런식으로 붙일 수 있다는 규칙이 있었다. 하지만, 이게 왜 dfs인지 알아야한다. 처음 한칸을 시작으로 4가지 경우, 그리고 3가지 경우, 그리고 3가지 경우로 발생되며, 이때 나온 합들 중 ..

이번 문제는 나름 꽤 시간이 걸렸던 문제였습니다. 물론 시간날때마다 도전해서 그렇긴 하지만 String 문자를 char형으로 변환하여 증가/감소 시킬수 있다는 점과 변환하는 방법, 그리고 익숙하지만 잘 안쓰게 되는 swich문도 사용해 보았습니다. 1. 먼저 문제를 읽은 후 문제에 대한 이해가 중요합니다. 이번문제에서 헷갈렸던 부분은 돌을 언제 움직일 수 있느냐 였습니다. 문제를 보고 이해한 바로는 = 체스가 돌이 있는 위치로 이동하게 되면, 그 돌을 체스가 이동해온 방향으로 이동시킨다 였습니다. 문제를 풀어본 결과 다행이 제대로 이해한거 같습니다. 2. 이제 문제를 이해했으니, 규칙을 만드는 것이었습니다. 규칙을 만들어야 로직을 짤때 수월하기 때문입니다. 여기서 고민했던점은 "RT"로 이동할때 "R"로..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] a1 = br.readLine().split(" "); int count = Integer.parseInt(a1[0]); int len = Integer.parseInt(a1[1]); // 2차원 배열로 세팅 String[][] arr = new Strin..

import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] a = new String[2]; a = br.readLine().split(" "); int H = Integer.parseInt(a[0]); int M = Integer.parseInt(a[1]); int N = M-45; if(N>0) { M = M-45; } else if(N