본문 바로가기

전체 글

 (164)
[그래프 이론] - Minimum Spanning Tree (최소 신장 트리) Spanning Tree는 그래프를 최소로 연결한 그래프입니다. 그렇기 때문에 N개 노드들이 있을때 모든 정점들이 연결 되어 있고 간선은 N-1개로 연결되어있습니다. 이때 사이클은 포함해서는 안됩니다. 최소 신장 트리는 Spanning Tree에서 사용된 간선들의 총 비용이 최소값을 가진 특수한 트리입니다. 최소 신장 트리가 최단 경로를 나타내지 않습니다. 최단 경로와 헷갈리면 안됩니다!! 예를 들어, N개의 정점에서 각 정점별 비용이 주어지고, 최소의 비용으로 모든 노드들간 서로 이동이 가능하도록 만드는 필요한 최소 비용을 구하라는 문제가 있을때 최소 신장 트리를 떠올려야 합니다. 최소 신장 트리를 만드는 방법은 두 가지 방법이 있습니다. 가장 많이 사용하는 방법으로 프림 알고리즘과 그 다음으로 크루스..
[백준] JAVA - 16926. 배열 돌리기 1 2차원 배열이 주어졌을때 배열을 R번 회전시킨 결과를 출력하는 문제입니다. 알고리즘 분류에는 구현이라고 정의되어있지만 요즘 재귀,DFS 문제를 계속 연습하는 중이라 이 문제도 재귀적으로 풀어보고 싶어서 도전했습니다! 1. 배열을 회전시킬 껍데기 개수를 구한다. 오른쪽 -> 위 -> 왼쪽 static int[] dx = {0,1,0,-1}; // 아래 -> 오른쪽 -> 위 -> 왼쪽 public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new Str..
[SWEA] JAVA - 1233. 사칙연산유효성검사 노드는 숫자이거나 연산자인 두 가지 경우가 있다. 만약 노드가 연산자일때 유효한 경우는 왼쪽자식 연산자 + 오른쪽자식 연산자 왼쪽자식 연산자 + 오른쪽자식 숫자 왼쪽자식 숫자 + 오른쪽자식 숫자 노드가 숫자일때 유효한 경우는 자식이 있으면 안됀다 (리프 노드여야 한다.) package com.ssafy.off; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class SWEA_1233_사칙연산유효성검사 { /** * 노드 개수 - N * 각줄마다 노드번호, 왼쪽자식 노드번호, 오른쪽자식 노드번호 * 경현님 코드 보고 이해했습니다 ㅠㅠ */ static String[] tre..
[백준] JAVA - 2563 색종이 모눈종이에 1*1 영역을 한칸씩(각 영역에 점을 찍는다라고 생각) 색칠한다고 생각하고 문제를 풀었습니다. 주어진 x,y 좌표에서 10씩 더한다음 그 영역에 1 표시가 되어있지 않다면 정답을 1씩 증가시켜줍니다. package com.ssafy.off; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Baekjoon_2563_색종이 { static int[][] map = new int[101][101]; static int cnt; public static void main(String[] args) throws NumberFormatException, IOExce..
탐색 알고리즘 정리 #3 - 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) Shortest path between all pairs of vertices, negative edges allowed. 모든 노드 간 최단 거리를 구하는 알고리즘입니다. 플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있습니다. Floyd-Warshall 로직 다익스트라 알고리즘과는 다르게 플로이드-워셜 알고리즘은 모든 정점을 경유지로 만든다는데에 있습니다. 우선, 모든 노드 간의 최단경로를 저장해야 하기 때문에 2차원 인접 행렬을 만듭니다. 거리값은 모두 무한대로 초기화 시켜줍니다. 하나의 정점에서 다른 정점으로 바로 갈 수 있으면 비용을 업데이트 시켜줍니다. 이때 갈수있는 경로가 여러개라면 최소값을 저장합니다. 경유지를 기준으로, 어떤 두 노드가 해당 경유지를 거처갈..
탐색 알고리즘 정리 #2 - 다익스트라 알고리즘(Dijkstra algorithm) 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. (shortest path from one node to every other node) 다익스트라의 개념은 출발점에서 이동 가능한 노드들을 찾고, 그 거리를 모두 기록합니다. 그리고 이 거리들 중 가장 짧은 것을 선택하고 이동하는것을 반복합니다. 마지막으로 한 노드까지의 경로를 리턴해주면 가장 짧은 경로를 알 수 있습니다. 이때 간선들은 모두 양의 간선들을 가져야 합니다. 하나의 정점에서 다른 모든 정점까지 각 정점별 최단 거리를 기록하는 배열이 있어야 합니다. 다익스트라 알고리즘은 첫 정점을 기준으로 연결되어있는 정점들을 추가해가며, 이전보다 최단 경로값이라면 최소값을 계속 업데이트 합니다. (각 정점간의 거리들은 모두 무..
JAVA - 10진수를 2진수, 8진수로 변환하기 public class NumberConversion { public static void main(String[] args) { int n0 = Integer.parseInt("11", 10); //10진수 -> 10진수 int n1 = Integer.parseInt("11", 2); //2진수 -> 10진수 int n2 = Integer.parseInt("11", 8); //8진수 -> 10진수 System.out.printf("%d, %d\n",n1, n2); String s1 = Integer.toBinaryString(15); // int -> 2진수 String s2 = Integer.toOctalString(8); // int -> 8진수 System.out.printf("%s, %s\n",..
[SWEA] JAVA - 1974. 스도쿠 검증 9*9 표에 가로방향, 세로방향, 각 영역별로 1부터 9까지 채워져있는지를 체크하는 문제입니다. 스도쿠 게임을 할 때 가로방향 합, 세로방향 합, 내부 영역의 합이 모두 45일때가 올바른 스도쿠 입니다. 1. 각 영역의 왼쪽상단 y좌표, x좌표를 받아 가로방향과 세로방향 내부 영역의 합이 모두 45인지를 체크하는 함수를 만들었습니다. 2. 위의 3가지 경우를 모두 만족했을때 true를 리턴합니다. 그렇지 않다면 false를 리턴합니다. 3. main 함수에서 이중 포문을 돌며 y좌표,x좌표를 3씩 증가시킵니다. 이때의 좌표값이 각 영역의 시작 좌표이므로 solve 함수의 파라미터로 넣어 확인합니다. package com.ssafy.makeupclass; import java.io.BufferedReade..

티스토리툴바