🌏 주제 : 10 - 해시법 (자바편) 🌏 해시법 해시법은 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하여 검색,추가,삭제를 효율적으로 수행 🌏 충돌(Collision) 만약 333이라는 값이 인덱스 14에 저장되어있는데 이후에 130이라는 값(나머지 14)을 저장한다고 가정 -> 이렇게 저장할 버킷이 중복되는 현상을 충돌이라고 한다. -> 해시 함수는 가능하면 해시값이 치우치지 않도록 고르게 분포된 값을 만들어야 한다. 충돌 대처법 2가지 1. 체인법 : 해시값이 같은 요소를 연결 리스트로 관리 2. 오픈 주소법 : 빈 버킷을 찾을때 까지 해시 반복 🌏 오픈 주소법 충돌이 발생했을 때 재해시를 수행하여 비어있는 버킷을 찾는 방법 -> 닫힌 해시법이라고도 함 18 삽입 하고자 할때 18 % 13 ..
🌏 주제 : 09 - 이진검색트리 (자바편) 🌏 이진검색트리 (자바편) 이진탐색트리(Binary Search Tree)는 이진 트리 기반의 탐색을 위한 자료구조이다. 전화번호부에서 전화번호를 찾거나, 사전에서 단어를 찾는 탐색 작업을 효율적으로 하기 위한 자료구조이다. 탐색작업을 하기에 앞서, 이진탐색트리의 정의에 대해 알아보면 다음과 같다. 1. 모든 노드의 키는 유일하다. 2. 왼쪽 서브트리의 키들은 루트의 키보다 작다. 3. 오른쪽 서브트리의 키들은 루트의 키보다 크다. 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다. 🌏 이진탐색트리의 삭제연산 1. 삭제하려는 노드가 단말노드인경우 2. 삭제하려는 노드가 두개의 서브트리중 하나만 가지고 있는 경우 3. 삭제하려는 노드가 두개의 서브트리를 모두 가..
🌏 주제 : 08 - 원형 이중 연결 리스트 만들기 (자바편) 🌏 원형 연결 리스트 원형 연결 리스트 : 연결 리스트의 맨 끝 노드를 첫 번째 노드와 연결시켜 원형으로 만든 리스트이다. 맨 끝 링크는 맨 앞 노드를 가리킨다. 포인터는 맨 끝 노드를 가리킨다. 맨 끝과 맨 앞을 바로 찾을 수 있다. 🌏 원형 이중 연결 리스트 이중 연결 리스트란 연결 리스트의 각 노드에 링크를 2개 만들어 하나는 뒷 노드를 하나는 앞 노드를 가리키는 연결 리스트이다. 기존의 단순 연결 리스트는 노드 포인터를 알고 있을 때 노드의 다음 노드는 찾아갈 수 있지만, 노드 앞의 노드는 찾아갈 수 없다. 앞의 노드를 찾으려면 리스트의 처음부터 거슬러 올라가야 한다. 따라서 단순 연결 리스트의 각 노드에 두 개의 노드 포인터를 두어 ..
🌏 주제 : 07 - 보이어 . 무어법 (자바편) 🌏 보이어 . 무어법 (자바편) 보이어-무어 알고리즘 KMP 알고리즘의 개선판이라고 할 수 있습니다. 시간복잡도는 최악의 경우 O(N)이지만 평균 O(N/M)의 시간복잡도를 가진다고 합니다. O(N+M)인 KMP 알고리즘보다 향상된 성능을 기대할 수 있습니다. 보이어-무어 알고리즘의 작동은 KMP 알고리즘과 유사하게 불필요한 비교는 건너뛰고 유의미한 비교만 진행하겠다는 것입니다. KMP 알고리즘의 경우에는 접두사와 접미사가 같은 최대길이를 저장하는 배열을 만들어 앞에서부터 검사를 진행하였다면, 보이어-무어 알고리즘은 문자열을 검색할때 주로 뒤에서 부터 확인합니다. 보이어-무어 알고리즘은 두가지 이동 방법이 존재하지만 주로 사용하는 bad match tab..
🌏 주제 : 배열을 힙으로 만들기 힙(Heap)? 힙 자료구조는 완전 이진 트리를 기초로 하는 자료구조입니다. 완전 이진트리는 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리를 말합니다. 힙은 최대힙(Max heap)과 최소힙(Min Heap)으로 나눠집니다. 최대힙은 부모노드의 값이 자식노드들의 값보다 항상 크고, 최소힙은 부모노드의 값이 자식노드의 값보다 항상 작습니다. (위 그림은 최대힙의 예시) 이러한 성질 때문에 항상 느슨한 정렬상태(반정렬 상태)를 유지합니다. 힙은 중복값을 허용합니다. 힙은 최댓값 또는 최솟값을 쉽게 뽑기 위한 자료구조 임으로 중복을 허용합니다. 🌏 힙 정렬 예제 package Chapter6; import java.util.Scanner; public class ..
🌏 주제 : 재귀 알고리즘 재귀란? - 어떤 사건이 자기 자신을 포함하고 있거나, 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적이라고 한다. 🌏 유클리드 호제법 두 정수의 최대공약수(greatest common divisor)를 재귀적으로 구하는 방법 package Chapter5; import java.util.Scanner; public class ex5_2 { // 정수 x,y의 최대공약수를 구하여 반환 static int gcd(int x, int y) { if (y == 0) return x; else return gcd(y, x % y); } public static void main(String[] args) { // 유클리드 호제법으로 최대공약수를 구함 Scanner scan =..
🌏 주제 : 큐란? 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO: first in first out) 🌏 링 버퍼로 큐 만들기 배열 요소를 앞쪽으로 옮기지 않는 큐. 배열의 맨 뒤가 맨 앞과 연결되어있는 자료구조. 맨 앞 - front 맨 뒤 - rear 링 버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다. 🌏 예제 package Chapter4; import java.util.Scanner; public class LastNElements { public static void main(String[] args) { // 원하는 개수만큼 값을 계속 입력받고 요솟수가 N인 배열에 마지막 N개를 저장 Scanner scan = new Scanner(System.in); final int..
🌱 오늘의 주제 : 스택이란? 🌱 스택이란? 후입선출 (LIFO: Last In First Out) 🌱 스택 코드 package Chapter4; public class IntStack { // int형 고정 길이 스택 private int[] stk; // 스택용 배열 private int capacity; // 스택 용량 private int ptr; // 스택 포인터 // 실행 시 예외 : 스택이 비어있음 public class EmptyIntStackException extends RuntimeException { public EmptyIntStackException() {} } // 실행 시 예외: 스택이 가득참 public class OverflowIntStackException extends..
🌏 주제 : 이진 검색 🌏 문제 요솟수가 n개인 배열 a에서 key와 같은 요소를 이진 검색 🌏 문제 분석 package Chapter3; import java.util.Scanner; public class BinSearch { // 요솟수가 n개인 배열a에서 key와 같은 요소를 이진 검색 static int binSearch(int[]a, int n, int key) { int pl = 0; // 검색 범위의 첫 인덱스 int pr = n - 1; // 검색 범위의 끝 인덱스 do { int pc = (pl + pr) / 2; // 중앙 요소의 인덱스 if(a[pc] == key) return pc; // 검색 성공 else if (a[pc] < key) pl = pc + 1; // 검색 범위를 뒤..
🌏 주제 : 보초법으로 선형 검색 구현하기 🌏 문제 선형 검색(보초법으로)으로 판단 횟수 줄이기. 🌏 문제 분석 package Chapter3; import java.util.Scanner; public class Ex3_1 { // 실습 3-1 static int seqSearch(int[]a, int n, int key) { int i = 0; //1. 방법 //while(true) { //if (i == n) //return -1; //if (a[i] == key) //return i; //i++; //} //2. 방법 (보초법) a[n] = key; // 보초를 추가; while (true) { if (a[i] == key) // 검색 성공 break; i++; } return i == n ? -..
