DailyStudyNote

이진 탐색(Binary Search) 이진 탐색(Binary Search) 란? 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X 와 비교한다. X 가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터를 대상으로, X 가 중간 값보다 크면 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다. 코드(Python) # 반복 알고리즘 def binary_search(arr, target): low, high = 0, len(arr) - 1 while low target: high = mid - 1 if arr[mid] == target: return mi..

최장 증가 부분 수열 (LIS, Longest Increasing Sequence) 최장 증가 부분 수열(LIS) 란? 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거하여 부분 수열을 만들 수 있다. 이 때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. 예를 들어, [6,2,5,1,7,4,8,3] 라는 수열이 존재하는 경우 LIS는 [2,5,7,8] 이 된다. [2,5], [2,7] 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 [2,5,7,8] 이기 때문이다. LIS(최장 증가 부분 수열)의 길이를 구하는 방법에는 두 가지가 있다. (1) DP(Dynamic Programing, 동적 계획법) - O(N^2) 알고리즘 (2) Lo..

계수 정렬(Counting Sort) 계수 정렬(Counting Sort) 계수 정렬(Counting Sort)란 숫자들간 비교를 하지 않고 정렬하는 알고리즘이다. 각 숫자가 몇개 있는지 개수를 세어 저장한 후에 정렬하는 방식이다. 계수 정렬은 특정한 조건이 부합될 때만 사용할 수 있는데 조건은 다음과 같다. ▶ 데이터의 크기 범위가 제한된 경우 → 0~100 까지의 점수를 정렬하는 경우가 이 조건에 해당하는 예가 될 수 있다. ▶ 데이터가 양의 정수인 경우 → 데이터가 실수인 경우 무한의 범위를 가질 수 있으므로 1번 조건에 부합하지 못한다. ▶ 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000(백만)을 넘지 않는 경우 → 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아진다...

힙(Heaps) 힙(Heap)이란? 이진 트리의 한 종류 (이진 힙-binary heap)이다. 1. 루트(root) 노드가 언제나 최댓값 또는 최솟값을 가진다. 최대 힙(max heap) 최소 힙(min heap) 2. 완전 이진 트리 완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조 로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다. 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 한다. 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 한다. 최대 힙(max heap)의 추상적 자료 구조 재귀적으로도 정의된다. 즉, 어느 노드를 루트로 하는 서브 트리도 모두 최대 힙 이다. 연산의 정의 __init__(): 빈..

조인(Join) 조인(Join) 이란? 두개 이상의 테이블이나 데이터베이스를 연결하여 데이터를 검색하는 방법이다. 자신이 검색하고 싶은 컬럼이 다른 테이블에 있을 경우 주로 사용하며 여러 개의 테이블을 마치 하나의 테이블인 것처럼 활용하는 방법이다. 보통 Primary Key 혹은 Foreign Key 로 두 테이블을 연결한다. 테이블을 연결하려면 적어도 하나의 컬럼은 서로 공유되고 있어야 한다. Inner Join 기준 테이블과 조인한 테이블의 중복된 값을 보여준다. 쉽게 말해 교집합이라고 생각하면 된다. 결과 값은 A의 테이블과 B테이블이 모두 가지고 있는 데이터만 검색이 된다. --문법-- SELECT 테이블별칭.조회할칼럼, 테이블별칭.조회할칼럼 FROM 기준테이블 별칭 INNER JOIN 조인테이..

퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort) 이란? 퀵 정렬은 평균적으로 매우 빠른 수행속도를 자랑하는 정렬 방법으로 분할정복(Divide and Conquer) 알고리즘이다. 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 또한 병합 정렬과는 다르게 퀵 정렬은 배열을 비 균등하게 분할한다. 분할(Divide) → 정복(Conquer) → 결합(Combine) 퀵 정렬은 pivot 을 선정하여 pivot 을 기준으로 좌측과 우측으로 pivot 보다 작은 값은 왼쪽 pivot 보다 큰 값은 오른쪽으로 재배치를 하고 계속해서 분할하여 정렬하는 알고리즘이다. * 분할정복(Divide and Conquer) 문제를 작은 2개의 문제로 분리하고 각각..

레디스(Redis) 레디스(Redis) 란? Redis(레디스)는 REmote DIctionary Server 의 약자로 오픈소스(BSD licensed) DBMS 이다. In-memory(인 메모리) 데이터 저장소이며, Key-Value 기반의 NoSQL DBMS 이다. 문자열 뿐만 아니라 리스트, 해시, 셋 등 다양한 데이터 형식을 지원한다. 1ms 이하 빠른 응답시간 지원한다. Redis 서버의 모든 데이터는 하드 드라이브에 저장되지 않고 메모리에 저장되게 된다. 메모리에 데이터를 저장한다는 것은 서버가 충돌할 경우 모든 데이터가 손실될 위험이 있다는 의미이기도 하는데 이런 상황을 막기위해 Redis 는 정기적으로 모든 데이터를 백업 하드 드라이브로 복사 또는 재 생성에 필요한 모든 명령을 로그 파..

삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 란? 삽입 정렬(Insertion Sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치에 삽입함으로써 정렬을 완성하는 알고리즘이다. 삽입 정렬은 처음 Key 값을 두 번째 요소부터 시작하게 되며 그 앞쪽 요소들과 비교하여 삽입할 위치를 지정한 후 요소를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 삽입 정렬(Insertion Sort) 시간 복잡도 ▶ 최악의 경우(입력 자료가 역순일 경우) T(n) = O(n^2) ▶ 최선의 경우(입력 자료가 정렬되어 있는 경우) T(n) = O(n) 삽입 정렬(Insertion Sort) 알고리즘의 특징 1. 대부분의 ..