본문 바로가기
728x90

전체 글259

[알고리즘] 그래프1 - 그래프란? 그래프란? 그래프는 정점(노드, Vertex)과 그 사이를 잇는 간선(Edge)로 이루어져 있다. G = (V, E)는 정점의 집합 V와 간선의 집합 E라고 할 때, 그래프 G는 V와 E의 집합 (V, E)라는 의미이다. 위의 그림에서, V(G) = {1, 2, 3, 4, 5}이고, E(G) = {(1, 2), (3, 1), (3, 2), (4, 1), (5, 2), (5, 4)} 이다. 그래프의 종류 무방향 그래프 이름 그대로 간선에 방향이 없는 그래프이다. 그렇기 때문에 정점 v와 정점 w를 잇는 간선 (v, w)가 있다고 하면 (w, v)도 같은 간선이 되는 것이다. 그러므로 정점이 n개일 때 무방향 그래프가 가질 수 있는 최대 간선 수는 n(n-1)/2개 이다. 방향 그래프 간선에 방향이 있는 그.. 2023. 9. 21.
[백준] 자바 문제 풀이 13334 : 골드2 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = .. 2023. 9. 21.
[백준] 자바 문제 풀이 1939 : 골드3 import java.util.*; import java.io.*; public class Main { static int n, m; static int start, end; static int left = 0, right = 0; static int ans; static List[] board = new ArrayList[10001]; static boolean[] visited = new boolean[10001]; static class Graph { int dest; int weight; Graph(int dest, int weight) { this.dest = dest; this.weight = weight; } } static boolean dfs(int s, int e, int w) { vi.. 2023. 9. 21.
[백준] 자바 문제 풀이 2812 : 골드3 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer str = new StringTokenizer(br.readLine(), " "); int n = Integer.parseInt(str.nextT.. 2023. 9. 21.
[백준] 자바 문제 풀이 17298 : 골드4 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] nlist = new int[n]; StringTokenizer str = new StringTokenizer(br.readLi.. 2023. 9. 21.
[백준] 자바 문제 풀이 16724 : 골드3 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer str = new StringTokenizer(br.readLine()); int n = Integer.parseInt(str.nextToken()); int m = Integer.parseInt(str.ne.. 2023. 9. 21.
[백준] 자바 문제 풀이 4195 : 골드2 import java.util.*; import java.io.*; public class Main { static int num = 0; static Map name = new HashMap(); static int[] parent; static int[] count; public static boolean union(int x, int y) { x = find(x); y = find(y); if(x == y) return false; if(x 2023. 9. 21.
[Java] 연산자 - SCE, 비트 Lazy Evaluation 직역하면 게으른 계산으로 Short-Circuit Evaluation(SCE)이라고도 한다. 이전 글에서 배운 논리연산자를 사용할 때 활용할 수 있는 방법이다. 논리연산자를 통해 조건식을 표현할 때, 뒤의 조건식을 보지 않더라도 전체 조건식의 리턴값을 알 수 있다면, 굳이 조건식에 포함되어 있는 모든 조건식을 검사할 필요가 없는 것이다. 그래서 자바는 이러한 상황에 Lazy Evaluation, SCE를 적용하여 결과값을 확실해지는 곳까지만 계산한다. A && B : A가 거짓이면 B가 무엇이 되든 거짓이 되기 때문에 B는 연산이 이루어지지 않는다. A || B : A가 참이면 B가 무엇이 되든 참이기 때문에 B는 연산이 이루어지지 않는다 비트연산자 비트 연산자는 말 그대로 .. 2023. 9. 20.
[Java]연산자 - 부호, 증감, 비교, 논리 부호 연산자 부호 연산자는 이름 그대로 피연산자의 부호를 나타내는 단항연산자이다. 부호를 나타내기 때문에 수에만 사용이 가능하다. int num1 = -10; int num2 = +num1; int num3 = -num1; 부호 연산자를 사용할 때 주의할 점은 수학에서의 부호와 동일하게 작용한다는 점이다. 위의 예시에서 보면 num1에 -10을 대입하고 num2에 +num1을 대입하게 되면 -10에 +를 하게 되면(+(-10)) 부호는 그대로이기 때문에 num2에도 똑같이 -10이 대입되는 것이다. + : 수의 부호(양, 음)이 바뀌지 않음 - : 수의 부호(양, 음)이 바뀜 증감 연산자 증감 연산자는 프로그래밍 언어에서는 많이 쓰이는 유용한 연산자이다. 바로 변수의 값을 1씩 증가 또는 감소시켜서 저장.. 2023. 9. 20.
[JAVA] 연산자 - 대입 연산자란 연산(Operation)이란, 주어진 식을 계산하여 결과를 얻어내는 과정을 연산이라고 한다. 연산을 수행하는 식에서 기호는 연산자(Operator)라고 하고 연산자에 의해 연산되는 연산자이외의 것을 피연산자(Operand)라고 지칭한다. 예를 들어, 사칙연산에서 +, -, /, * 가 연산자인 것이고 연산되는 숫자가 피연산자인 것이다. 연산자 종류 연산자는 피연산자의 개수에 따라 다음과 같이 구분되어 진다. 이항연산자(binary operator) : 피연산자가 2개인 연산자 단항연산자(unary operator) : 피연산자가 1개인 연산자 삼항연산자(ternary operator) : 피연산자가 3개인 연산자 연산자 특징 프로그래밍에서 연산자는 몇 가지 특징을 가지고 있는데 이러한 특징을 모.. 2023. 9. 20.
[알고리즘] 자바로 Union Find 구현하기 유니온 파인드란? 그래프/트리의 대표적 알고리즘 서로소인 부분집합의 표현 여러 노드가 있을 때, 두 노드가 같은 그래프에 속해 있는지 알 수 있는 알고리즘 두가지 메소드로 구현 가능 : union(x, y), find(x) 유니온 파인드 알고리즘이란, 하위 노드의 부모 노드를 배열에 저장하는 방식으로, 여러 노드들이 어떤 집합에 속해 있는지를 알 수 있는 유용한 알고리즘이다. 유니온 파인드를 능숙하게 사용할 수 있게 되면, 백준 등 여러 코딩 문제들도 손쉽게 풀 수 있다. 코드 구현 find find() 는 int 변수를 파라미터로 받는 재귀함수이다. 파라미터로 넘긴 노드의 젤 최상위 부모가 누구인지를 알려주는 함수이다. public int find(int x) { if(parent[x] == x) re.. 2023. 9. 20.
[백준] 자바 문제 풀이 10216 : 골드4 import java.util.*; import java.io.*; public class Main { static int[] parent; static class Point { int x; int y; int r; Point(int x, int y, int r) { this.x = x; this.y = y; this.r = r; } } public static boolean union(int x, int y) { x = find(x); y = find(y); if(x == y) return false; if(x 2023. 9. 20.
728x90
반응형

티스토리툴바