- 알고리즘 분류 : BFS - 사용 언어 : JAVA - 문제 요점 최소 신장 트리를 구하는 문제 크루스칼 알고리즘(최소 신장 트리를 구하는 알고리즘)과 우선순위 큐(비용이 적은 것을 먼저 꺼내는 큐)를 이용하여 풀이 가능 마을을 2개로 나눈다는 의미 → 최소 신장 트리를 2개로 나눈다 → 하나의 최소 신장트리에서 간선을 하나 삭제하면 최소 신장 트리가 2개가 된다. (이 때, 최소 비용으로 나누기 위해서 가장 큰 비용의 간선을 제거 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java...
Algorithm
이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다. 1. 팀 결성 - 서로소 집합 자료구조를 이용해서 풀이 가능 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { // N : 학생 수 // M : 연산의 수 public static int N, M; // 부모 변수 public static int[] parent; // 결과 변수 public static ArrayList result = new A..
- 알고리즘 분류 : BFS - 사용 언어 : JAVA - 문제 요점 검은 방도 갈 수 있다고 생각 입력과 반대로 검은 방을 1, 흰 방을 0으로 입력받기 BFS를 이용해 상하좌우로 이동하며 각 좌표로 이동하는 동안 만난 검은 방의 최소 갯수를 기록 끝방에 대한 검은 방의 최소 갯수를 출력 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; public class Main { // 그래프 변수 public static i..
이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다. (원본 소스코드 : https://github.com/ndb796/python-for-coding-test/) 1. 이전에 공부했던 그래프 복습 1) 그래프(Graph) : 노드와 노드 사이에 연결된 간선 정보를 가지는 자료구조 (서로 다른 개체가 연결 or 여러 도시가 연결 과 같은 경우는 그래프 알고리즘 의심) - 다익스트라 알고리즘 : 시작점에서부터 다른 각각의 노드로 가는 최단 경로를 구하는 알고리즘. (우선순위 큐를 이용하면 효율적) - 워셜-플로이드 알고리즘 : 모든 노드에서 각각의 다른 노드까지 최단 경로를 구하는 알고리즘. (인접 행렬을 이용, 노드의 갯수가 적으면 유용) - 그래프 표현 방..
- 알고리즘 분류 : 다익스트라 알고리즘 - 사용 언어 : JAVA - 문제 요점 다익스트라 알고리즘을 이용하여 풀이 0을 입력받을 때까지 계속해서 입력받는 것을 반복해야함 상하좌우로만 움직일 수 있음(상하좌우 x,y 이동 배열을 미리 선언하여 배열을 이용하여 위치 변경) 노드끼리 연결된 것이 아닌, x와 y좌표로 입력하기에 필자는 2차원 배열을 이용하였음 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; ..
- 알고리즘 분류 : BFS(너비 우선 탐색) - 사용 언어 : JAVA - 문제 요점 너비 우선 탐색을 이용하여 쉽게 풀이 우선순위 큐를 이용하여 소요 시간이 적게 걸리는 것을 먼저 가져오기 범위는 0~100000이니 이 안에서 움직이도록 설정 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { public static class Node implements Comparable{ // 현재 위치 int p..
- 알고리즘 분류 : 다익스트라 알고리즘 - 사용 언어 : JAVA - 문제 요점 다익스트라 알고리즘을 이용하여 쉽게 풀이가 가능 다익스트라 알고리즘의 기초적인 문제 목표지점을 받고, 해당 목표지점에 대한 거리만 출력하면 되는 간단한 문제 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; // 노드 클래스 선언 class Node implement..
- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식 - 사용 언어 : JAVA - 문제 요점 다익스트라 알고리즘을 이용하여 쉽게 풀이가 가능 다익스트라 알고리즘의 기초적인 문제 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; // 노드 클래스 선언 class Node implements Comparable{ // 지점 private..
