CS/자료구조와 알고리즘9 이진 탐색 / 이분 탐색 - Binary Search 이진 탐색이라고 하며, 이분 탐색이라고도 하는 Binary Search는 배열의 원소가 오름차순이나, 내림 차순으로 정렬되어 있는 경우에 빠르게(log N) 값을 찾아낼 수 있는 알고리즘이다. 우리는 일상생활에서 Binary Search를 한번쯤 경험해본 적이 있을 것이다. 어렸을 때 많이 했던, 업 다운 게임이 대표적으로 Binary Search의 알고리즘을 이용하는 놀이이다. 1부터 10까지의 임의 수를 정하고 크다면 업, 작다면 다운을 외치는 놀이이다. 여기서 우리는 최소한의 횟수로 숫자를 맞추기 위해 1부터 10 사이의 중간값을 계산해 값을 유추할 수 있다. 1 2 3 4 5 6 7 8 9 10 항상 중간값을 선택해 값을 유추한다. -> 5보다 크다면, 8 을 선택 -> 5보다 작다면, 3을 선택.. 2022. 11. 1. ArrayList ArrayList ArrayList는 자바에서 동적 배열을 생성하기위해 자주 사용하는 클래스이다. ArrayList는 List 클래스로 부터 상속을 받은 클래스들 중 하나로, 일반 정적 배열과 같이 연속되어진 메모리 공간을 사용하며, 인덱스 또한 0부터 시작하게 된다. ArrayList의 생성 HTML 삽입 미리보기할 수 없는 소스 ArrayList의 값 추가 HTML 삽입 미리보기할 수 없는 소스 ArrayList의 값 제거 HTML 삽입 미리보기할 수 없는 소스 ArrayList의 값 변경 HTML 삽입 미리보기할 수 없는 소스 ArrayList의 원소의 개수 HTML 삽입 미리보기할 수 없는 소스 ArrayList의 초기화 HTML 삽입 미리보기할 수 없는 소스 ArrayList의 값 출력 HTML.. 2022. 10. 28. 제곱근 소수 판별 제곱근 소수 탐색 소소를 판별하는 방법은 다양하게 있지만.. 일반적인 알고리즘을 배우는 사람은 단계적으로 소수를 판별하는 법을 알게된다. 1. for문을 이용한 소수 판별 // isPrime(29); public static boolean isPrime(int prime){ for(int i = 2; i < prime; i++){ if(prime % i == 0){ return false; } } return true; } 소수 일경우 1과 자기자신을 제외한 모든 수를 나누었을 때 나머지가 0으로 나누어지지 않는 다면 그 수는 소수이다. 허나 숫자 100만개를 각각 소수인지 판단하라고 할 때에는 시간이 오래 걸리게 된다. 2. 에라토스테네스의 체 에라토스테네스의 체는 소수를 한개가 아닌 여러개를 판별할 .. 2022. 10. 27. Set Set Set은 집합이란 의미로 중복 값을 허용하지 않는 클래스이다. 또한 값을 저장 할 때 에는 순서를 유지하지 않고 저장하므로 주의 해야한다. 만약 중복 값을 허용하지 않으면서 순서대로 값을 넣고 싶다면 LinkedHashSet을 사용해야한다. 또한 중복 값을 허용하지 않으면서 정렬된 순서로 값을 넣고 싶다면 SortedSet을 사용해야한다. Set 생성 // Set의 생성 Set set = new HashSet(); HashSet set = new HashSet(); // 순서를 유지하는 Set 집합 Set set = new LinkedHashSet(); LinkedHashSet set = new LinkedHashSet(); // 정렬된 순서를 가지는 Set집합 Sorted set = new Tr.. 2022. 10. 26. Map Map은 Key와 Value로 구성된다. 키값을 통해 그 키값에 해당하는 Value값을 얻을 수 있는데, 대응 관계에 있는 것들을 표현할 때 사용한다. Map은 배열과 달리 순차적인 인덱스로 접근하는 것이 아니기에 인덱스로 구하는 것을 원한다면 List를 이용해야한다. Map의 생성 HashMap m = new HashMap(); Map m = new HashMap(); Map의 키와 값을 넣기 // Key가 String, Value가 Integer일 때의 put map.put("김국진", 58); map.put("김나얼", 55); map.put("김소월", 98); map.put("김한국", 48); // Key가 중복이고, Key의 개수를 새어 줄 때 map.put("A", m.getOrDefaul.. 2022. 10. 25. 에라토스테네스의 체 <쉽게> 에라토스테네스의 체는 소수를 판별하는데 쓰이는 방법 중 하나이다. 고대 수학자 에라토스테네스가 발견하였고, 이 알고리즘을 이용하면 소수를 구하는 문제를 쉽고 빠르게 구할 수 있다. 1. 2부터 시작하여, 2를 제외한 2의 배수를 모두 칠한다. 2. 2 다음인 3을 제외한 3의 배수를 모두 칠한다. 3. 4는 2의 배수이고, 칠해져있으므로 다음으로 건넌다. 4. 5는 2의 배수도 3의 배수도 아니므로 5를 제외한 5의 배수를 모두 칠한다. .... .... 이로서 자기 자신을 제외한 모든 배수가 칠해졌다. 칠해지지 않은 수는 모두 소수이다. 그렇다면 위 알고리즘을 코드로 풀어서 쓴다면 어떻게 쓸 수 있을까? boolean[] prime = new boolean[10000001]; // 천만 까지의 수 중 .. 2022. 10. 24. Deque Deque Deque는 Stack과 Queue를 합쳐 놓은 것과 같다고 보면 편하다. Queue는 선입 선출을 Stack은 후입 선출이라면 Deque의 경우 둘다 가능하다. Deque의 생성 LinkedList의 생성과 ArrayDeque의 차이는 Queue부분에 자세하게 써놓았습니다. 궁금하시다면 Queue부분도 보시길 바랍니다. Deque deque = new LinkedList(); Deque deque = new ArrayDeque(); Deque의 선입 deque.offerFirst(1); // 1 deque.offerFirst(2); // 2 1 deque.offerFirst(3); // 3 2 1 Deque의 선출 deque.pollFirst(); // 3이 빠지고 2 1 만 남은 상태 de.. 2022. 10. 23. Queue 큐 Queue는 선입 선출를 가진 자료구조이다. FIFO(First In First Out)으로 먼저 큐에 삽입된 값이 값을 뽑을 때 먼저나오게 된다. 일반적으로 큐는 은행과 우체국과 같이 대기자가 있고, 순서가 있는 곳에 사용된다. 번호표를 뽑을 경우 나보다 번호가 늦은 사람이 먼저가는 경우는 없다. 또한 게임에서도 찾아볼 수 있는데, 게이머와 게이머의 매칭 게임의 경우 게임 시작을 누르면 매칭이 되고, 매칭이 될 경우 게임을 시작하게 된다. 동일한 조건에서 내가 먼저 누를 경우 먼저 게임에 들어가는게 큐의 원리이다. 실제로 매칭을 돌릴 때에도 우리는 큐 잡혔냐 라고 말할 정도로 일상생활에서 큐를 자주 사용하곤한다. 큐의 생성 //큐의 생성 Queue queue = new LinkedList(); //.. 2022. 10. 22. Stack 스택은 언어에서 제공하는 자료구조로 LIFO(Last IN First Out) 의 형태를 가지고 있다. 스택의 생성 스택은 기본적으로 Stack class와 new 연산을 통해 객체로 생성된다. Stack name = new Stack(); 이다. 스택의 값 넣기 스택에서 넣을 때 사용하는 연산은 push()이다. 값을 넣을 때에는 가장 먼저 들어온 것이 가장 늦게 나가기 때문에 바닥부터 탑을 촘촘히 쌓아간다고 하면 편하다. 스택의 경우 제일 위에 있는 값이 아닌 중간 값을 임의로 뺄수 없다. 스택의 값 빼기 스택에서 값을 뺄때 사용하는 연산은 pop()이다. 1, 2, 3을 순차적으로 넣었을 때 가장 늦게 push된 3이 pop을 할경우 가장 먼저 나간다. 스택의 최상단에 있는 값 보기 스택의 최상단에.. 2022. 10. 21. 이전 1 다음
