전공공부

설명 피보나치 수열을 구현하는 코드입니다. 당연하게도 dynamic programming 방식을 채택했고 0 1 1 2 3 5 8 ... 이전 두 개의 값을 가져와서 현재의 값으로 초기화하는 방식을 그대로 구현해서 사용했습니다. 사실, DP 문제는 아이디어 싸움이라 구현상의 어려움은 없었습니다. 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); long[] dp = new long[n + 1]; dp[0] = 0; if (n > 0) { dp[1] = 1; } for (in..

설명 이 문제는 플로이드 워셜을 거꾸로 보면 됩니다. 즉, 이미 중간치를 거쳐서 초기화가 된 것인지 파악하면 되는 문제이므로 이를 거꾸로 돌려서 구현합니다. 그리고, 만일 이번에 돌렸는데 최소치가 갱신된다면 이는 모든 최소화된 도로가 연결된 것이 아니므로 조건에 따라서 -1을 출력합니다. 코드 package BOJ.shortest_path; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ_1507 { public static void main(String[] args) throws Exception{ B..

설명 웜홀 문제는 벨만 포드 알고리즘을 활용한 문제입니다. 누락된 조건 중 모든 그래프가 연결 그래프가 아닐 수 있음을 판단하고 문제를 풀어야 합니다. 그리고, 도로는 양방향이고 웜홀은 단방향임을 명심해야합니다. 그래서, 문제를 풀게 되면 아래와 같은 형태로 작성 할 수 있습니다. 그리고, 음수 사이클이 생기면 시간이 줄어들면서 원래 제자리로 돌아오는 것이니 음수 사이클 여부를 체크하면 됩니다. 코드 package BOJ.shortest_path; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; impo..

설명 제출 시 계속 틀렸습니다 가 남발해서 다른 사람의 블로그를 참고해서 푼 문제입니다. 해당 문제의 개념은 A,B,C 위치로 부터 각각 가장 가까운 곳으로 부터의 리스트 중 가장 먼 곳을 선택하는 문제입니다. 그래서, 각 A point , 각 B point, 각 C point로 부터 시작하는 위치로 부터의 각 길이를 모두 구하고 이에 대한 길이 중 가장 짧은 길이를 구하고 나서 그들 리스트 중 가장 먼 곳을 가져와서 가장 먼 곳의 위치(인덱스) 값을 리턴해줍니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static class Data implement..

설명 벨만 포드 알고리즘을 활용했고 dist 거리 부분을 long으로 바꾸지 않으면 오버플로 오류가 났습니다. 이런 작은 부분들을 체크하는 것이 어려웠습니다. 코드 package BOJ.shortest_path; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class BOJ_11657 { static int N,M; public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tk = n..

설명 특이한 알고리즘 기법이 사용된 문제는 아니고 일반적인 플로이드 와셜 문제인데요. 다만, 수의 비교를 통해서 갈 수 있는 곳을 찾아내는 문제다 보니 나 보다 큰 수는 어디까지 탐색 할 수 있는지 파악 할 수 있는 곳을 찾고 나 보다 작은 수는 어디까지 탐색 할 수 있는 지 탐색이 필요합니다. 따라서, 아래와 같이 코드 구현을 하였습니다. 코드 package BOJ.shortest_path; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ_10159 { static int N,M; public stat..

설명 플로이드 와셜 활용한 알고리즘이며 구현 부분이 상당히 귀찮은 문제입니다. char -> int 형으로 관리하고 이를 대소문자마다 다시 int 위치에 위치 시켜야 하므로 이런 부분이 구현 문제처럼 느껴지는 부분입니다. 사실 나머지 주요 로직은 플로이드 와셜을 이용해서 이미 갔던 위치를 다시 거쳐서 가면서 중간 위치에서 갈 수 있는 곳은 연결되었다는 로직으로 하면 됩니다. 코드 package shortest_path; import java.util.*; import java.io.*; public class BOJ_2224 { private static char itoa(int idx) { if (idx

설명 인접리스트 형태로 풀기 위해서 Map이라는 새로운 객체로 각 i,j 번째 행렬의 위치의 노드 위치 값을 저장하고 이를 이용해서 Dijkstra를 구현하였는데 double dist = Math.sqrt(Math.pow(distX, 2) + Math.pow(distY, 2)); //double dist = Math.sqrt(Math.abs(distX) * Math.abs(distX) + Math.abs(distY) * Math.abs(distY)); 위에 보이는 해당 코드 형태 때문에 계속 틀렸었습니다. 약간 어이 없는 문제인데 컴퓨터의 부동소수점 표현 방식에 따른 정밀도 문제로 인해서 그렇다고 합니다. 적어도 PS를 할 때는 API를 적극 이용하여야 겠습니다. 코드 import java.io.Buff..