Algorithm (18) 썸네일형 리스트형 재귀 알고리즘 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)라고 한다 ex) 팩토리얼 static int factorial(int n){ if(n>0){ return n*factorial(n-1); } else{ return 1; } 유클리드 호제법 static int gcd(int x, int y){ if(y==0){ return x; } else{ return gcd(y, x%y); } } 재귀 알고리즘 예시 static void recur(int n){ if(n>0){ recur(n-1); System.out.println(n); recur(n-2); } } recur(4); 결과값 1 2 3 1 4 1 2 recur(4) recur(3) print(4) rec.. 큐(Queue) 큐(Queue) 데이터를 일시적으로 쌓아 두기 위한 자료구조 선입선출(First In First Out) 구조 인큐(enqueue) - 데이터를 넣는 작업 디큐(dequeue) - 데이터를 꺼내는 작업 프런트(front) - 데이터를 꺼내는 쪽 리어(rear) - 데이터를 넣는 쪽 offer() - 값 넣기 poll() - 값 꺼내기 큐 선언 ex) import java.util.Queue; import java.util.LinkedList; Queue queue = new LinkedList(); queue.offer(1); // 1넣기 queue.offer(2); // 2넣기 int num = queue.poll(); //queue의 맨 앞 값 꺼내기 queue.peek(); //맨 앞의 값 확인하기.. 스택(Stack) Stack 겹겹이 쌓음이라는 의미 데이터를 일시적으로 저장 Last in First Out 형식 접근은 언제나 목록의 끝에서 발생 push - 데이터를 넣는 작업 pop - 데이터를 꺼내는 작업 top - 푸쉬와 팝을 하는 위치 bottom - 스택의 가장 아랫부분 사용법 ex) Stack을 import해서 사용하기 import java.util.Stack; Stack stack = new Stack(); Stack stack = new Stack(); //값추가 stack.push(); //값삭제 stack.pop(); //값 초기화 stack.clear(); ex) Stack 클래스 만들기 public class IntStack { private int max; // 스택 용량 private int .. Arrays.binarySearch - java는 배열에서 이진 검색을 하는 메소드를 표준 라이브러리로 제공한다 - java.util.Arrays 클래스의 binarySearch메소드가 있다 import java.util.Arrays; import java.util.Scanner; public class BinarySearchTester { public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); System.out.print("요솟수 : "); int num = stdIn.nextInt(); int[] x = new int[num]; //배열생성 System.out.println("오름차순으로 입력하세요."); System.out.print("x[0].. 검색(선형 검색, 보초법,이진 검색 선형 검색 - 요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 앞부터 순서대로 요소를 검색하는 방식 ex) import java.util.Scanner; public class SeqSearch { static int seqSearch(int[] a, int n, int key) { for (int i = 0; i 다차원배열과 확장 for문의 장점 다차원배열 다차원 배열의 복제는 최상위 1레벨만 수행된다 ex) int[][] a ={{1,2,3,4},{5,6,7}}; int[][] b = a.clone(); 일때, a[0]과 a[1]만 복제되고 그 아래 레벨의 배열은 복제되지 않고 공유된다 . 즉, 1과5만 복제된다는 것이다. 확장 for문 ex) for (int i =0; i>>>>>>>> sum = sum+i; } } 장점 - 배열의 요솟수(길이)를 조사하는 수고를 덜 수 있다 - iterator와 같은 방법으로 스캔할 수 있다 - 스캔은 확장 for문에 의해 구현하는 것이 좋다 에라토스테네스의 체 자바 소수판별 알고리즘을 공부하다보니 에라토스테네스의 체에 관련된 알고리즘을 보고 공부를 하게 되었다. 코딩테스트를 위해 클린코드를 지향하는 나로서 매우 중요한 부분인거 같아서 정리해보고자 한다. 에라토스테네스의 체는 N이하의 수들이 소수인지 아닌지 판별할 때, n(임의의 수)의 배수들을 모두 지움으로써 시간복잡도를 저하시킨다는 장점을 가지고 있다. 아래의 코드를 직접 살펴보며 공부하도록 하자 예시로 N을 16이라고 해보자. 배열은 index값이 0,1,2....16까지 있는 17의 크기를 가진 Boolean타입의 배열이 생성되었을 것이다. 16의 제곱근 값은 4가 되고, i=2, i 소수 판별 알고리즘 1000이하의 소수 나열 알고리즘 구조 개선 전 구조개선 후 이전 1 2 3 다음