JADE's Repository

Key: 해시 테이블 접글을 위한 값 Hash Function: Key를 Hash Value로 매핑하는 연산 Hash Value: Hash Table의 인덱스 Hash Table: Key-Value를 연관시켜 저장하는 데이터 구조 해시 충돌 Hash Table의 같은 공간에 서로 다른 값을 저장하려는 경우, 서로 다른 Key가 해시 함수를 통해 생성된 Hash Value가 동일한 경우 해시 충돌이 있어날 수 있다. 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있다. 개방 주소법 (Open Address) 테이블에서 비어있는 공간의 Hash를 찾아 데이터를 저장 Hash와 Value는 1:1 관계를 유지 비어있는 공간 탐색 방법에 따라 선형 탐사법, 제곱 탐사법, 이중 해싱 등으로 분류 1..

배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법 두 개 포인터의 배치 방법 첫 번째 요소에 둘 다 위치 (Same direction pointers) Array에서의 중복 제거, 최소 길이의 합을 찾는 문제가 대표적 Array에서의 중복 제거 문제는 Slow, Fast 포인터로 나뉘며 Slow는 unique한 요소를 가리키고 Fast는 중복 체크를 하며 이동 첫 번째 요소와 마지막 요소에 위치 (Reverse direction pointers) 팰린드롬 문자열이 대표적인 문제 다중 for문의 복잡도를 좀 더 linear하게 해결할 수 있음 import java.util.*; public class Main { public static void main(String[] args) { int[]..

정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법 찾고자 하는 값과 데이터 중앙에 있는 값을 비교 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색 시간복잡도: O(logn) import java.util.*; public class Main { public static void main(String[] args) { int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60}; System.out.println(binarySearch(arr, 30)); System.out.println(binarySearch2(arr, 30, 0, arr.length - 1)); //자바 메소드 System.out.pr..

Algorithm Time Complexity Memory stability Bubble Sort O(n) 1 O Insertion Sort O(n) 1 O Selection Sort O(n) 1 X Merge Sort O(nlogn) n O Heap Sort O(nlogn) 1 X Quick Sort O(n) logn X Radix Sort O(dn) 1 n + k Counting Sort O(n + k) n + k O Shell Sort O(n) 1 X 안정 정렬 vs 불안정 정렬 Bubble Sort 인접한 데이터를 비교하며 자리를 바꾸는 방식 시간 복잡도: O(n) import java.util.*; public class Main { public static void main(String[] a..

문제 24174번: 알고리즘 수업 - 힙 정렬 2 2 5 1 4 3(heapify(A, 2, 5)) -> 2 3 1 4 5(heapify(A, 1, 5)) -> 1 3 2 4 5(A[1] A[5]) -> 5 3 2 4 1(heapify(A, 1, 4)) -> 2 3 5 4 1(A[1] A[4]) -> 4 3 5 2 1(heapify(A, 1, 3)) -> 3 4 5 2 1(A[1] A[3]) -> 5 4 3 2 1(heapify(A, www.acmicpc.net 풀이 문제에서 제시하는 다음 수도 코드를 그대로 구현하면 되는 문제이다. 단, K번 교환될때의 배열을 저장하는 부분만 추가해주어야한다. import java.util.*; import java.util.stream.Collectors; publ..

트리 기반의 자료구조 최소 힙은 부모가 항상 자식보다 작기 때문에 루트가 결국 가장 작은 값 주로 배열로 구현 부모, 자식 같의 관계만 정의할 뿐 좌우에 대한 관계는 정의하지 않음 완전 이진 트리의 형태 다익스트라 알고리즘에도 활용 삽입 업힙(Up-Heap) 연산을 수행 시간 복잡도: O(log n) 추출 다운힙(Down-Heap) 연산을 수행 시간 복잡도: O(log n) 추출 이후에 다시 힙의 특성을 유지하는 작업이 필요 PriorityQueue Java에서는 다음과 같이 PriorityQueue를 Heap으로 사용할 수 있다. PriorityQueue heap = new PriorityQueue(); PriorityQueue 의 코드 내부에서는 Object[] Array를 사용한다. 즉, 고정된 크..

문제 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 위처럼 앞에서 K-1개 만큼을 맨 뒤로 보낸 뒤 맨 앞에 있는 값을 뽑아주면 된다. import java.util.LinkedList; import java.util.Scanner; import java.util.stream.Collectors; import java.util.stream.IntStream; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int..

문제 26008번: 해시 해킹 첫째 줄에 비밀번호의 길이 $N$과 문자 종류의 개수 $M$, 정수 $A$가 주어진다. ($1 \le N, M, A \le 5\,000\,000$) 둘째 줄에 재현이가 알아낸 해시값 정수 $H$가 주어진다. ($0 \le H < M$) www.acmicpc.net 풀이 $P_1 \cdot A+...+P_{N-1}\cdot A^{N-1}$ 을 $x$라고 해보자 $x=2, M=5$일 때 $P_0$ 값을 변경함에 따라 해시 함수의 결과 값이 0 ~ M-1 으로 나오는 것을 확인할 수 있다. 즉, $P_0$ 값에 따라 $h(P)$의 결과를 원하는 값으로 만들 수 있다. 하지만 $h(P)$를 해시값 정수 H로 만들 수 있는 $P_0$는 딱 1개 밖에 없다. 대신 $P_1 \cdot ..

많은 수의 데이터를 다룰 때 사용하는 자료 구조 각 데이터를 인덱스와 1:1 대응 메모리 상에 연속적으로 저장 장점 인덱스를 이용하여 데이터에 빠르게 접근 Array의 요소에 접근하거나 할당할 때의 시간복잡도는 O(1)이다. 단점 데이터의 추가시 최대 길이를 정하여 생성 후 생성한 배열에 옮겨야함 배열의 크기를 변경할 때마다 새로운 배열 생성 Java에서 배열 생성시 요소의 초기값은 각각 다음과 같다. 정수형 (int, short, byte, long): 0 부동소수점형 (float, double): 0.0 논리형 (boolean): false 문자형 (char): '\u0000' 또는 null 참조형 (객체 배열): null

문제 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 1. 정렬을 통한 풀이 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int[] intArray = new int[N]; for (int i=0..