본문 바로가기

분류 전체보기

 (106)
[알고리즘] 백준17472 - 다리만들기2 java package a0401; import java.util.*; import java.io.*; /* 사방탐색->크루스칼 쓰면 될듯? 1) 각 지역마다 숫자 다르게 기입 2) 각 지역별로 사방탐색 돌려서 다른지역 만나면 list(from, to, weight)에 추가 3) 사방탐색 끝나면 크루스칼로 모든지역 연결 */ public class 백준17472다리만들기2 { static int sero ; static int garo ; static int[][] arr ; static int[][] visit ; static int tmpcnt = 0; static int placecnt = 0; static ArrayListlist = new ArrayList();//넘버링 별 좌표저장하는 리스트 publi..
[알고리즘] 백준4485 - 녹색 옷 입은 애가 젤다지? java풀이 처음에 DP 누적합 처럼 풀으려고 착각함. 시간초과 안나게 풀려면 다익스트라만 가능한듯 package a0401; import java.io.*; import java.util.*; /* dp인줄 알았는데 다익스트라로 해야됨 */ public class 백준4485녹색옷젤다 { static int[][] arr; static int[][] sumarr; static int size; static class node implements Comparable{ int xidx; int yidx; int weight; node(int xidx, int yidx, int weight){ this.xidx = xidx; this.yidx = yidx; this.weight = weight; } @Override p..
[알고리즘] 백준2667- 단지 번호 붙이기 java import java.util.*; import java.io.*; public class 백준2667단지번호붙이기 { static int tmpcnt = 0 ; static int size; static int[][] arr ; static int[][] visit ; static boolean check(int i, int j) { if(0
[알고리즘] SW expert - 최소 스패닝 트리 java (Prim 풀이) import java.util.*; import java.io.*; /* Node class를 만들어서 Node형 배열을 선언한다 Node class에는 인접 정점의 번호, 그 정점까지의 거리를 변수로 갖는다 */ public class swea최소스패닝트리_prim버전 { static class Node implements Comparable{ int nodenum; int len; Node(int nodenum, int len){ this.nodenum = nodenum; this.len = len; } @Override public int compareTo(Node o) { return this.len - o.len; } } public static void main(String[] args) th..
[알고리즘] SW expert - 최소 스패닝 트리 java (크루스칼 풀이) import java.util.*; import java.io.*; public class swea최소스패닝트리_크루스칼버전 { static class Edge implements Comparable{ int from; int to; int weight; Edge(int from, int to, int weight){ this.from = from; this.to = to; this.weight = weight; } @Override public int compareTo(Edge o) { return this.weight-o.weight; } } static int nodenum ; static int edgenum ; static int[] v_parent; static void makeset() { ..
[알고리즘] 크루스칼(Kruskal) 알고리즘이란? 크루스칼(Kruskal) 알고리즘 간선의 가중치 정보를 이용해 MST(최소신장트리)를 구현하는 알고리즘 이다. 이용되는 알고리즘은 Union Find, 우선순위 큐가 있다. 1) 전체 로직 순서 Comparable을 상속받아 Edge 클래스(정점1, 정점2, 가중치)를 선언한다. compareTo를 오버라이딩 하여 가중치를 기준으로 오름차순 정렬을 조건을 추가한다. Edge형 우선순위큐를 선언하고 주어진 간선의 정보를 이용해 새로운 edge 객체를 우선순위큐에 넣어준다. 우선순위큐에서 간선을 순서대로 빼온다. 빼온 간선에 해당하는 두 정점이 같은 Union인지 확인한다. 같은 Union이라면 -> 이미 추가된 정점들이므로 다음 간선을 빼낸다 다른 Union이라면 -> 해당 정점의 부모노드를 이용해 같은 ..
[알고리즘] 최소신장트리, MST란? MST란? Minimum Spanning Tree의 약자로 최소신장트리 라고 불린다. 위 그림과 같이 그냥 Spanning Tree는 모든 정점이 연결되어 있는 Tree이다. 조금 더 구체적으로 말하면 모든 정점이 임의의 간선들을 거쳐 만날 수 있는 Tree이다. 따라서 MST는 최소한의 가중치로 모든 정점을 연결시킨 Tree이다. MST를 만들 수 있는 알고리즘은 크게 2가지가 있는데 다음과 같다. 1) 크루스칼(kruskal) 알고리즘 2) 프림(prim) 알고리즘 1) 크루스칼 알고리즘 이란? 크루스칼 알고리즘이란 주어진 간선의 가중치를 기준으로 MST를 찾는 알고리즘이다. 크루스칼 알고리즘 구현을 위해 쓰이는 자료구조 및 개념 -> 우선순위큐, Union Find 2) 프림 알고리즘이란? 프림 알..
[알고리즘] 백준21610 - 마법사 상어와 비바라기 java package a0324; import java.util.*; import java.io.*; public class 백준21610_마법사상어와비바라기 { static int[][] arr; static int[][] dirinfo; static int[] di = {0, -1, -1, -1, 0, 1, 1, 1}; static int[] dj = {-1, -1, 0, 1, 1, 1, 0, -1}; static int nowdir; static int movelen; static int[][] nowcloud; static int size; static int dirsize; public static void main(String[] args) throws Exception{ BufferedReader ..

티스토리툴바