알고리즘
알고리즘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...
알고리즘 99 :: 2019 카카오 블라인드 코딩테스트 - 후보키
알고리즘 99 :: 2019 카카오 블라인드 코딩테스트 - 후보키
2020.09.072019 카카오 블라인드 코딩테스트 연습으로 풀어보았습니다. 유일성 : 한 컬럼에 대한 값이 유일하게 존재하는 것 최소성 : 유일성을 만족했음에도 다른 유일한 칼럼들을 추가해서 최소성을 깨뜨리면 안됩니다. e.g) 나이, 학년 조합으로 최소성을 만족할 수 있는데 학번이라는 칼럼을 가지고 와서 굳이 나이, 학년, 학번 으로 후보키를 만들필요가 없다는것입니다. 후보키 푸는 로직은 후보키를 만들 수 있는 조합 -> (생성된 후보키 그룹) 포함 관계 여부 -> 유일성 검사 이후 후보키 그룹에 포함으로 해결할 수 있습니다. ㅡ. 후보키를 만들 수 있는 조합 for(int i=1; i
알고리즘98 :: swea_3431_준환이의 운동관리
알고리즘98 :: swea_3431_준환이의 운동관리
2020.09.051234567891011121314151617181920212223242526272829303132package swea모음; import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer; public class swea_3431_준환이의운동관리 { public static void main(String[] args) throws Exception { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int total = Integer.parseInt(..
알고리즘97 ::거북이 카드만들기
알고리즘97 ::거북이 카드만들기
2020.08.30ㅡ. 컨셉 거북이는 10이라는 숫자를 만들려고 한다. 그런데, 주어진 카드가 1,2,5 밖에 없다. 이럴 경우에 1을 10번 골라서 10을 만들거나 2를 두번 고르고 1을 고른뒤 5를 고르면 10이 만들어진다. 하지만 선택하는 수를 최소로 하고 싶다. 이런 경우 어떻게 해야 할까? 방법 : DP를 사용한다. int num = 10; int arr[] = new int[num+1]; int cards[] = {1,2,5}; for(int i=0; i