DailyStudyNote

최장 증가 부분 수열 (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(백만)을 넘지 않는 경우 → 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아진다...

조인(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. 대부분의 ..

세마포어(Semaphore)와 뮤텍스(Mutex) 동기화 도구인 세마포어(Semaphore)와 뮤텍스(Mutex) 공유된 자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다. 이러한 문제를 해결하기 위하여 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 두는 동기화 방식을 취해야한다. 동기화 도구에는 대표적으로 세마포어(Semaphore)와 뮤텍스(Mutex)가 있으며 이 두 방식은 모두 공유된 자원의 데이터를 여러 프로세스 또는 스레드가 접근하는 것을 막는 역할을 한다. 임계 영역(Critical Section) 멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유자원의 코드 영역이다. 즉 여러 프로세스가 동일한 자원을 동시에 참조하여 값이 ..

트랜잭션(Transaction) 트랜잭션(Transaction; TX) 란 ? 트랜잭션(Transaction)은 데이터 베이스 상태를 변환시키는 하나의 논리적 기능 수행 단위이다. 즉 한번에 수행되어야 할 일련의 연산을 의미한다(Unit Of Work in Database Language). * 데이터베이스의 상태를 변화시킨다는 의미 ? 질의어(SQL: SELECT, INSERT, DELETE, UPDATE)를 통해 데이터베이스에 접근하는 것을 의미한다. * 작업의 단위? 많은 SQL 명령문들을 사람이 정하는 기준에 따라 정하는 것을 의미한다. 예시) 사용자 A가 사용자 B에게 만원을 송금한다. [DB 작업] 1. 사용자 A의 계좌에서 만원을 차감한다: UPDATE 문을 사용해 사용자 A의 잔고를 변경한..