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..

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

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

Queue? 위 그림의 왼쪽처럼 식당에 입장하기 위해 줄을 서는 것을 생각해보면 가장 먼저 줄을 선 사람이 가장 먼저 입장한다. Queue도 이와 같은 방식으로 동작한다. 이처럼 먼저 들어간 것이 먼저 나오는 것을 선입선출(First In First Out, FIFO)라고 한다. Queue의 주요 연산 Enqueue와 Dequeue Enqueue(): 값을 집어넣는 것을 의미 Dequeue(): 값을 꺼내는 것을 의미 Java에서 Queue의 Enqueue와 Dequeue 메소드 Enqueue: add, offer Dequeue: remove, poll Queue의 시간복잡도 Enqueue(): O(1) Dequeue(): O(1) 탐색: O(n) Queue에서 값을 탐색하여 얻는 것은 부적절하다. 실제..

Stack? 위처럼 접시를 쌓으면 마지막에 쌓은 접시가 맨 위에 놓일 것이다. 그러면 당연하게도 가장 마지막에 쌓은 접시를 제일 먼저 꺼내게 된다. Stack도 이와 같은 방식으로 동작한다. 이처럼 마지막에 쌓은 것을 가장 먼저 꺼내게되는 것을 후입선출(Last In First Out, LIFO)이라고 한다. Stack의 주요 연산 Push와 Pop push(): 요소를 추가 pop(): 가장 최근에 추가된 요소를 제거 Stack의 시간복잡도 push(): O(1) pop(): O(1) get(): O(n) get(): 값을 조회하는 메소드 Appendix 1946년 앨런 튜링은 서브 루틴을 호출하는 과정을 bury, 되돌아오는 과정을 unbury라고 불렀는데 이것을 스택의 기원이라고도 한다. 스택은 콜..

■ Greedy는 한국말로 "탐욕스러운"이라는 뜻이다. 따라서 그리디 알고리즘은 말 그대로 눈앞의 이익만 쫓는 아주 탐욕스러운 알고리즘이라는 것이다. 그렇다면 Dynamic Programming(다이나믹 프로그래밍)과 Greedy(그리디)는 무엇이 다른 걸까?? 조금 딱딱하게 이론적으로 설명하자면 다이나믹 프로그래밍은 하위 문제에 대한 최적의 해결책을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션(global optimum solution)에 대한 선택을 하고 그리디는 각 단계마다 최적해를 찾는 문제로 접근해 문제를 작게 줄여나가는 형태이다. 이후 설명을 통해 좀 더 이해해보자. ■■ 대표적인 매우 유명한 문제인 배낭 문제를 예제로 그리디 알고리즘을 구현해보겠다. 위 그림과 같이 15k..

■ 슬라이딩 윈도우는 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 푸는 알고리즘이다. 정렬된 배열에 사용하는 투 포인터와 달리 정렬 여부와 상관 없이 사용된다. 크게 어렵지 않은 알고리즘이기때문에 바로 예제를 통해서 이해해보도록 하겠다. ■■ 다음 예제는 leetcode에서 가져왔다. 입력 : arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 출력 : [3, 3, 5, 5, 6, 7] k 크기의 슬라이딩 윈도우를 오른쪽 끝까지 이동하면서 최댓값들을 구하는 문제이다. 진행 순서는 다음과 같다. ■■■ 그럼 바로 코드 작성을 해보자 import sys from collections import deque def slidingwindow(arr:list, k..