- 알고리즘 분류 : 다이나믹 프로그래밍, 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; //거리와 노..
Algorithm
- 알고리즘 분류 : 다이나믹 프로그래밍, 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..
- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식 - 사용 언어 : JAVA - 문제 요점 계단수 = 각 자릿수끼리 차이가 1이 나는 수 자릿수 별로 2차원 배열을 이용해 풀이 가능 0으로 시작하는 수는 계단 수가 아님 현재 자릿 수의 숫자에 +-1을 뒷 자리수에 대입하면 계단 수가 됨 ex) 10의 자리의 수가 2일 때, 즉 2? 일 때, 계단 수는 21, 23 0은 1, 8은 9로 고정(-1, 10이 되기 때문) 1000000000으로 나누는 것 잊지 않기 - 점화식 도출 * j가 0 d[i][0] = d[i-1][1]; * j가 9 d[i][9] = d[i-1][8]; * j가 1~8 d[i][j] = d[i-1][j-1] + d[i-1][j+1]; 소스 설명은 주석을 참고해주세요...
- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식 - 사용 언어 : JAVA - 문제 요점 높이가 2로 고정, 넓이가 N인 타일의 경우의 수를 도출 N이 1일 수도 있으니, 예외 처리 필요 10007로 나누는 거 잊지 않기 - 점화식 도출 d[i] = d[i-1]+d[i-2]; 2x1, 1x2의 2종류 타일이 존재한다. → 최대 2칸 전까지만 확인 1. 현재 기준 2칸 전까지 다 채워진 경우 1*2 타일 2개 채움 (2*1 타일 2개로도 채울 수 있지만, 그렇게 되면 2번과 같은 모양) 2. 현재 기준 1칸 전까지 다 채워진 경우 2*1 타일 1개 채움 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException..
