- 알고리즘 분류 : 크루스칼 알고리즘 - 사용 언어 : JAVA - 문제 요점 최소 스패닝 트리(최소 신장 트리)를 구하는 문제 크루스칼 알고리즘(최소 신장 트리를 구하는 알고리즘)과 우선순위 큐(비용이 적은 것을 먼저 꺼내는 큐)를 이용하여 풀이 가능 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { // V : 정점의 개수 // M : 간선의 개수 public static int V, M; // 각 ..
코테 공부
- 알고리즘 분류 : DFS (BFS로도 풀이 가능) - 사용 언어 : JAVA - 문제 요점 DFS로 계속 깊은 곳을 가는 것이 아닌, 방문 가능한 노드를 다 확인하며 진행한다. 양보다 늑대의 수가 많거나 작으면 다 잡아 먹힌다. (DFS 탈출) 노드를 방문할 때마다 양과 늑대의 수를 체크하고 방문을 체크하며 DFS를 진행한다. 효율성 테스트가 없어 간단하게 작성한 코드입니다. (방문 체크 변수를 ArrayList로 추가하고 방문한 노드들만 추가하는 방향으로 하면 더욱 빠를 것이다.) 소스 설명은 주석을 참고해주세요. import java.util.*; class Solution { // map 변수 public static ArrayList map = new ArrayList(); // 양의 수 pu..
- 알고리즘 분류 : 그리디 알고리즘 - 사용 언어 : JAVA - 문제 요점 우선순위 큐를 이용하여 시간이 적게 걸리는 음식 순대로 확인 음식을 먹는데 시간이 적은 순서대로 확인하기 때문에, 뒤에 있는 음식들은 현재 음식보다 무조건 시간이 많거나 같다는 것을 인지하고 풀이 소스 설명은 주석을 참고해주세요. import java.util.*; // 음식 클래스 선언 class Food implements Comparable { // 먹는 시간 private int time; // 음식 번호 private int index; public Food(int time, int index) { this.time = time; this.index = index; } public int getTime() { retu..
- 알고리즘 분류 : BFS - 사용 언어 : JAVA - 문제 요점 최소 신장 트리를 구하는 문제 크루스칼 알고리즘(최소 신장 트리를 구하는 알고리즘)과 우선순위 큐(비용이 적은 것을 먼저 꺼내는 큐)를 이용하여 풀이 가능 마을을 2개로 나눈다는 의미 → 최소 신장 트리를 2개로 나눈다 → 하나의 최소 신장트리에서 간선을 하나 삭제하면 최소 신장 트리가 2개가 된다. (이 때, 최소 비용으로 나누기 위해서 가장 큰 비용의 간선을 제거 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java...
이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다. 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..
- 알고리즘 분류 : 다익스트라 알고리즘 - 사용 언어 : 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..
