뚝딱 뚝딱 개발일기

https://www.acmicpc.net/problem/1427 간단하지만 중요한 기본문제 해당 문제는 int 배열을 만들어 오름차순 정렬을 하면된다.물론 int 배열을 내림차순정렬하여 거꾸로 출력하는 방법도 있지만  오름차순 정렬를 하는 법을 활용해보겠다. 방법 1. 오름차순 직접 구현import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;class Main{ // 소트인사이드 백준 - 1427 public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new ..

0-1 KnapSack Problem대표적인 DP 문제 알고리즘 중 하나로 알려져 있다. DP 란, 큰 문제를 작은 문제로 나누어서 푸는 방법을 일컫는 말이다.최적 부분 구조를 가진다는 것은 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것입니다.처음에는 Brute Force 로 접근하였지만 시간 복잡도가 2 ^n 으로  시간 초과가 날것이 분명했다.DP 문제를 풀기 위해서는 '최적의 원리' (Principle of Optimality) 가 성립하는지를 확인해야 하는데,최적의 원리는 다음과 같다. "어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면.그 문제는 대하여 최적의 원리가 성립한다" 평범한 배낭 문제도 적용해 보자집합 A 를 n 개의 물..

https://www.acmicpc.net/problem/11729 알고리즘원반이 한개면 그냥 옮기면 끝이다.(종료조건)원반이 n 개 일때1번 기둥에 있는 n개 원반 중 n-1 개를 목적지가 아닌 보조기둥(2번)으로 옮긴다.1번 기둥에 남아 있는 가장 큰 원반을 목적지(3번) 기둥으로 옮긴다.2번 기둥에 있는 n-1 개 원반을 다시 목적지(3번) 기둥으로 옮긴다.원반이 1 개일 때가 '종료 조건' 에 해당한다. 원반 n 개 문제를 풀려면 n-1 개 원반 문제를 풀어야 하는데 이는 바로 '좀 더 작은 값으로 자기 자신을 호출하는 과정'이다. 따라서 이 문제는 전형적인 재귀 호출 알고리즘에 해당한다(이승찬, 2017) import java.io.BufferedReader;import java.io.Input..

정규표현식 문법과 예제^,$ - 문자열의 시작과 끝^regex : 문자열의 시작이 regex 에 해당하는 경우regex$ : 문자열의 끝이 regex에 해당하는 경우String result1, result2;String str = ".123!";result1 = str.replaceAll("^.", "*");System.out.println(result1);result2 = str.replaceAll("!$", "*");System.out.println(result2);// 출력*123!.123* [ ] - 문자의 집합 범위"." 는 일반적으로 모든 문자를 의미하지만 대괄호 '[]' 안에 있을 경우는 문자 그대로의 '.' 을 의미합니다/[abc] : a, b, c 중 문자 1개[abc][xyz] : a,..

max 값 찾기 ( for 문 활용 ) for(int i=0; i max 값 찾기 ( stream 활용 ) return Arrays.stream(triangle[triangle.length-1]).max().getAsInt();

List to String[] // 1. toArray() 배열 선언과 동시에 할당List arr = new ArrayList(); arr.add("a"); arr.add("b"); arr.add("c"); String[] answer = arr.toArray(new String[0]); System.out.println(Arrays.toString(answer)); // [a, b, c] // 2. toArray() 배열 선언 후 할당List arr = new ArrayList(); arr.add("a"); arr.add("b"); arr.add("c"); Stri..

1차원 배열 오름차순 정렬// 1차원 배열 오름차순 Sortint[] nums = { 2, 4, 9, 8};Arrays.sort(nums);System.out.println(Arrays.toString(nums));//결과 [2, 4, 8, 9] 1차원 배열 내림차순 정렬 (for문 활용)// 1차원 배열 내림차순 Sort   int[] nums = { 2, 4, 9, 8};        Arrays.sort(nums);        for(int i=0; i   1차원 배열 Stream 정렬 // 1차원 배열 내림차순 Sort   int[] nums = { 2, 4, 9, 8};   int[] descNums = Arrays.stream(nums)                   .boxed().sor..

Prime Number 소수 : 약수가 1과 자기 자신 밖에 없는 수 N 이 소수가 되려면, 2보다 크거나 같고 , N-1 보다 작거나 같은 자연수로 나누어 떨어지면 안된다. 1 부터 100 까지 소수 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 소수와 관련된 알고리즘은 두가지가 있다. 1. 어떤 수 N 이 소수인지 아닌지 판별하는 방법 2. N 보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법(N 이하의 소수를 찾아내는 방법) 방법 1.소수의 정의를 이용한 풀이_시간복잡도 O(N) public static boolean isPrime(int a){ if (a == 1){ return false; } for (in..

Least Common Multiple 최소공배수는 줄여서 LCM 이라고 한다. 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수이다. 최소 공배수는 GCD (최대 공약수)를 응용해서 구할 수 있다. A x B = GCD * LCM (두 수의 곱은 최소공배수와 최대공약수를 곱한 값과 같다.) 두 수 a,b 의 최대공약수를 g 라고 했을 때 최소공배수 I =(a*b)/g 이다. https://www.acmicpc.net/problem/2609

Greatest Common Divisor 최대 공약수를 줄여서 GCD 라고 쓴다. 두 수 A 와 B 이 최대공약수 G는 A 와 B 의 공통된 약수 중에서 가장 큰 정수이다. 최대공약수를 구하는 가장 쉬운 방법은 2 부터 min(A,B)까지 모든 정수로 나누어 보는 방법 최대공약수가 1인 두 수를 서로소(Comprime)라고 한다. 방법 1 . 작은 수 부터 차례로 계산해보기 int g =1; for (int i=2; i b) { small = b; }else { small = a; } for (int i=small; i > 0; i--) { if ((a % i == 0) && (b % i == 0) ){ return i; } } return -1; } 방법 3. 유클리드 호제법 위의 두 방법보다 빠른 ..