- 알고리즘 분류 : 다익스트라 알고리즘 - 사용 언어 : 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..
- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식 - 사용 언어 : JAVA - 문제 요점 다익스트라 알고리즘 이해 필요 X마을에서 각자 마을로 돌아가는 건 다익스트라 알고리즘을 사용 각자 마을에서 X마을로 가는 건, 방향을 반대로 가정한 후 다익스트라 알고리즘을 사용 소스 설명은 주석을 참고해주세요. 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; //거리와 노..
- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식 - 사용 언어 : JAVA - 문제 요점 플로이드 워셜 알고리즘에 대한 이해 필요 서로 연결되어 있으니 2차원 배열에서 서로 연결 필자는 2차원 배열을 이용해 0과 1을 구분 - 플로이드 워셜 알고리즘 중요 부분 for(int temp=1; temp
이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다. 1. 미래 도시 워셜 플로이드 알고리즘을 이용하여 풀이할 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static int[][] graph; public static final int INF = (int)1e9; public static int[] visited; // 최단 ..
- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식 - 사용 언어 : JAVA - 문제 요점 피보나치 함수에 대해 이해가 필요 주어진 테스트 케이스 중 가장 MAX 값 까지 확인 필자는 2차원 배열을 이용해 0과 1을 구분 - 점화식 도출 d[i][0] = d[i-1][0] + d[i-2][0]; d[i][1] = d[i-1][1] + d[i-2][1]; 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException{..
- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식 - 사용 언어 : JAVA - 문제 요점 주어진 수를 아래의 연산을 반복하여 1로 만들기 1을 빼기 2로 나누기 3으로 나누기 1로 만드는 연산 횟수가 가장 적은 횟수를 출력 - 점화식 도출 int min = d[i-1] + 1; if(i % 2 == 0) { min = Math.min(min, d[i/2] + 1); } if(i % 3 == 0) { min = Math.min(min, d[i/3] + 1); } 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Mai..
이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다. 1. 최단 경로(Shortest Path) - 말 그대로 가장 짧은 경로를 찾는 알고리즘. - 최단 경로 문제는 보통 그래프를 이용해 표현하며, 각 지점은 노드로 표현되고 지점 간 연결된 도로는 간선으로 표현 - 코딩테스트에서는 다익스트라 최단 경로와 플로이드 워셜 알고리즘 유형이 자주 등장 2. 다익스트라(Dijkstra) 최단 경로 알고리즘 - 그래프에서 여러 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘. - 이 알고리즘은 '음의 간선'(0보다 작은 값을 가지는 간선)이 없을 때 정상적으로 동작하며, 현실 세계 또한 음의 간선으로 표현되지 않아 GPS..
