소수 알고리즘 - 에라토스테네스 체 2부터 n까지 모든 수를 나열 -> 자기 자신을 제외한 배수를 모두 지운다. 위의 과정을 반복하면 소수가 남는다. 이중 for문을 사용해야 하지만, 값이 2일 때 N /2 , 3일 때 N / 3 점점 커지므로 O(logN)이 된다. 1 + 1/2 + 1/3 + ... 의 합이 O(logN)이라는 원리와 동일 2부터 자기자신까지 모두 비교하면 O(n^2) , 에라토스테네스의 체를 실행하면 O(logN)의 시간복잡도를 갖는다. 단, 1천만~1억 까지 소수는 없다 (문제에 따라 판단 필요) public static boolean isPrime(int num) { if(num == 1) return false; else { for (int i = 2; i * i

Security 보안 정책 (Policy) H/W 보안 (칩 등) S/W 보안 (보안 솔루션) 운영체제 네트워크 솔루션 프로그래밍 (보안 모듈, 리버스 엔지니어링(역공학)) Java Security 메시지를 주고받을 때 (같은 프로그램, 즉 같은 알고리즘 사용) 송신 : 암호화(Ciphertext + key)하여 송신 수신 : 받은 정보를 복호화하여 수신 공개키 : 암호화로 할때 사용한 키가 있어야 복호화가 가능한 방식 DES : 1977년 IBM에 의해 개발, 현재 기술론 충분히 해킹 가능 (64비트 text, 54비트의 키, 16rounds를 통한 암호화) AES(블록 알고리즘) : DES의 문제를 개선 - 128,193,256비트 등과 같은 가변적 비트길이, 키를 갖고 있어 복잡한 암호화된 결과물을..

DFS 합이 같은 부분 집합 import java.util.*; public class Main { static int n, total =0; static String answer ="NO"; boolean flag = false; public void dfs(int level, int sum, int[] arr) { if (flag) return; if (sum > total / 2) return; if (level == n) { if ((total-sum)==sum) { answer="YES"; flag = true; } } else { dfs(level+1, sum+arr[level], arr); dfs(level+1, sum, arr); } } public static void main(Strin..

Recursive 모든 함수는 기본적으로 스택 프레임을 가진다. 스택 안에는 매개변수, 지역변수, 복귀 주소 등을 가지고 있다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Main main = new Main(); int n = 3; main.solution(n); } public void solution(int n) { if (n==0) return; else { System.out.print(n +" "); // [출력] 3 2 1 solution(n-1); System.out.print(n +" "); // [출력] 1 2 3 } } } 스택에 계속 쌓이면서 solut..

Primitive Type 기본 자료형 : 메모리에 실제 값을 갖는 자료형 논리형 : boolean , 문자형 char, 정수형 (byte, short, int , long) , 실수형 (float, double) Non-Primitive Type 참조 자료형(비기본 자료형) : 실제 값이 아닌 객체의 주소를 갖고 있는 자료형 객체의 주소에 의해 참조 되며, new 키워드를 통해 생성된다. 클래스 (String, Integer 등), 인터페이스 (Collection, Map) 등, 배열 String fruit = "Apple"; fruit.toUpperCase(); 기본 자료형에는 String이 없다. 그래서 fruit은 인스턴스로 부르는게 맞지만, 자주 사용하기 때문에 변수명으로 부르기도 한다. (to..

정렬 종류 출처 : https://st-lab.tistory.com/179 버블 정렬 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 알고리즘 오름차순 기준으로 한 회전 당 제일 큰 값을 뒤로 보낸다. 선택 정렬 주어진 데이터 중, 최솟값을 찾아 맨 앞에 위치한 값과 교체 하는 알고리즘 교체 마다 시작 인덱스를 증가 시킨다. public class Chap01 { public static void main(String[] args) { int[] a = {20, 35, 10, 6, 94, 1}; int[] b = {20, 35, 10, 6, 94, 1 }; Chap01 main = new Chap01(); System.out.println("Bubble Sort..

약수 x에 대해 정수로 나누어떨어지는 수 소수 : 1과 자기자신으로만 나누어 떨어지는 수 최대공약수 2개 이상의 자연수가 공통된 약수를 갖는 수 유클리드 호제법 : 최대공약수를 구하는 알고리즘 2개의 자연수 a,b에 대해서 (a>b 일 때) a를 b로 나눈 나머지를 r a 와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 과정을 나머지가 0이 되었을 때 까지 반복하여 얻는 수가 최대공약수 static int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; } 유클리드 호제법 사용 - While 문으로 시간복잡도는 O(n) static int gcd2(int a, int b) { if (a % b == 0) r..

정규 표현식 Regular Expression 특정한 규칙을 가진 문자열의 집합 JDK 1.4부터 제공 검색 ^ : 문자열 시작부터 $ : 문자열 종료까지 . : 줄바꿈을 제외한 임의의 한 문자 *: 바로 앞에 문자가 없거나 하나 이상 있을 때 +: 바로 앞에 문자가 하나 이상 있을 때 [^] : ^ 이후의 괄호안 형식을 제외한 문자 [] : []안의 형식을 일치하는 문자열 {} : {} 앞의 문자열의 반복 개수 - ab{2,} : 2개 이상, ab{1,2} : 1부터 2까지 ( ) : () 안의 내용을 하나의 묶음으로 처리 | : OR 연산 [0-9] : 0~9 숫자, [a-z A-Z] : 모든 알파벳, [ㄱ-ㅎ|ㅏ-ㅣ|가-힣] : 모든 한글 \s : 모든 공백 문자, \S : 공백 문자 제외, \d ..