알고리즘
특정거리의 도시찾기
특정거리의 도시찾기
2020.11.07이 문제는 최단거리를 찾아내는 과정을 BFS알고리즘을 통해 해결할 수 있습니다. 알고리즘 개략적인 부분은 아래와 같습니다. pq에 시작위치와 depth를 저장 ans를 위한 pq선언 BFS depth가 우리가 찾는 depth라면 ans 에 node번호를 넣기(2의 pq에서 첫번째 요소) 그리고 continue 그게 아니라면 2의 pq 전체를 돌면서 현재 node의 사이즈만큼 돈다. next를 선언 방문하지 않았다면 방문체크해주고 pq에 넣어준다. next, cost+1 로 ans 의 사이즈가 0 이면 -1 그렇지않으면 ans 가 empty가 아닐때까지 poll 해서 정답을 유추한다. package programmers; import java.util.*; import java.io.*; public cl..
멀쩡한사각형
멀쩡한사각형
2020.11.07import java.util.*; import java.math.*; class Solution { public long solution(int w, int h) { int gcd = BigInteger.valueOf(w).gcd(BigInteger.valueOf(h)).intValue(); return ((long)w*(long)h)-(((long)(w/gcd)+(long)(h/gcd-1)))*gcd; } }
BOJ :: 1182(부분 수열의 합)
BOJ :: 1182(부분 수열의 합)
2020.10.261 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 package backjun; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.*; public class BOJ_1182_부분수열의합_백트래킹 { static int aim=0; static int[] arr; static int answer = 0; public stat..
알고리즘108 :: 구간합 (JAVA)
알고리즘108 :: 구간합 (JAVA)
2020.09.30구간의 합을 빠르게 구하고자 할때 Priefix sum을 미리 구해서 답을 도출해냅니다. 누적합이 특정배열에 담기는것으로 상수시간안에 답을 도출해낼 수 있습니다. 10, 20, 30, 40, 50 인 경우 10, 30, 60, 100, 150 으로 누적합 테이블을 생성할 수 있습니다. 이때 left가 1이고 rightrk 3인 구간의 합을 구하는 문제가 주어질 경우 간딴하게 Array[3] - Array[1-1] 의 값으로 답을 결정할 수 있습니다. (식 Array[right] - Array[Left-1]) package test; import java.util.*; public class 구간합알고리즘 { public static void main(String[] args) { // TODO Auto-..
알고리즘107 :: 투포인트 - BOJ_수들의합2
알고리즘107 :: 투포인트 - BOJ_수들의합2
2020.09.28선형 시간 알고리즘입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import java.util.*; public class 수들의합2_2 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] a = new int[n+1]; for(int i=0; i
알고리즘106 :: BOJ_11726_2XN타일링
알고리즘106 :: BOJ_11726_2XN타일링
2020.09.27두가지 접근 방식으로 문제를 해결하였습니다. 1) Bottom-up 과 2) Top-down 으로 접근하였습니다. 기본적으로 이 문제는 피보나치 수열에 대한 이해를 근본으로 하고 있습니다. 1) 바텀업 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 package backjun; import java.util.*; public class BOJ_11726_2n타일링 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] dp = new int[n+2]; dp[1] ..
알고리즘105 :: BOJ_2056_작업
알고리즘105 :: BOJ_2056_작업
2020.09.26위상정렬과 관련된 문제입니다. "몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다." 앞서 수행해야 하는 작업이 우선 수행한뒤 뒤에 노드들이 수행되어야 합니다. 따라서 위상정렬 알고리즘을 활용하여 해결할 수 있습니다. Scanner sc = new Scanner(System.in); int n = sc.nextInt(); ArrayList[] al = new ArrayList[n+1]; for(int i=1; i
알고리즘104 :: BOJ_1766_문제집
알고리즘104 :: BOJ_1766_문제집
2020.09.26import java.util.*; public class Main { static class Empty implements Comparator{ public int compare(int a, int b) { return Integer.compare(a, b); } @Override public int compare(Integer o1, Integer o2) { // TODO Auto-generated method stub return o1-o2; } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m ..
알고리즘104 :: 최소 스패닝 트리(MST)
알고리즘104 :: 최소 스패닝 트리(MST)
2020.09.24최소 스패닝 트리란 무엇일까요? 그래프가 트리형태 인것을 의미합니다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리 입니다. 여기서 최소 스패닝 트리는 스패닝 트리중에서 선택한 간선의 가중치의 합이 최소인 트리를 의미합니다. 대표적으로 MST를 구현하는 방법으로 프림, 크루스칼이 있습니다. 여기서 사이클을 제작하지 않는 범위에서 구현해야 합니다. 왜냐하면, 트리는 사이클이 존재하지 않기 때문입니다. 1)프림 초록색점은 선택한 노드 흰색은 선택하지 않은 노드 입니다. 선택과 선택하지 않은 노드 사이의 간선에서 가중치 값이 가장 작은 값을 갖는 2를 추가합니다. 간선2를 선택하게 됩니다. 선택한 노드와 선택하지 않은 노드 사이에 간선들은 3, 1, 3, 4 가 됩니다. 간선 1이 선택됩니다. 노드 5는 이..
알고리즘102 :: KAKAO_셔틀버스
알고리즘102 :: KAKAO_셔틀버스
2020.09.22몇번 읽고 문제가 잘 이해가 안되었습니다. ㅠ__ㅠ 그래서 몇 가지 검색해보다가 알게된 사실을 예제로 설명해 보겠습니다. example1) n=1, t=1, m=5, timetable=["08:00","08:01","08:02","08:03"] 셔틀은 09:00 부터 출발합니다. 셔틀은 1번 1분 간격으로 역에 도착하지만 한번에 5명을 태울 수 있으므로 08:00~08:03, (콘이 탈 시각 08:04) 모두 태울 수 있습니다. 따라서, example2) n=2, t=10, m=2, timetable=["09:10","09:09","08:00"] 마찬가지로 셔틀이 09:00 부터 출발하는것을 생각해보면 08:00 에 한명을 태웁니다. 셔틀이 총 2번 10분 간격으로 오기때문에 다음 올 셔틀은 09:10 ..
알고리즘101 :: 프로그래머스 - 소수찾기
알고리즘101 :: 프로그래머스 - 소수찾기
2020.09.21소수찾기는 크게 3가지 세션으로 나눠볼 수 있습니다. 1) 주어진 number를 문자로 쪼개기 2) 문자로 쪼갠것으로 모든 경우의 수를 만들기 3) 에라토스테네스체를 이용해 소수인지 검증하기 1의 경우에는 String str = "17" 인경우 String[] number = str.split("") 이용해서 1, 7로 쪼갤 수 있습니다. 2의 경우에는 string[] number, boolean[] picked, StringBuilder sb 를 활용합니다. number는 1의 경우에서 구한것이므로 넘어가고 boolean[] picked = new boolean[number.length]; 로 선언 StringBuilder sb = new StringBuilder() 로 선언 HashSet dff = ..
알고리즘 100 :: 백준 순열과 조합(N과M 시리즈)
알고리즘 100 :: 백준 순열과 조합(N과M 시리즈)
2020.09.21ㅡ. N과M(1) : 순열 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 package backjun; import java.io.*; import java.util.*; public class BOJ_15649_N_M_1{ static int[] k; static boolean[] c; public static void main(String[] args) throws Exception{ // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System...