[Alex] 데이터 장인의 블로그

출처 [Heee's Development Blog] 퀵 정렬은 많은 프로그래밍이 기본으로 채택하는 정렬 알고리즘이다. (프로그래밍 언어 차원에서의 기본적으로 지원되는 정렬함수.) 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법. 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 과정 설명 [참고] 예를 들어 다음과 같은 데이터가 있다고 가정한다. [6, 5, 1, 4, 7, 2, 3] 이때 4라는 피벗값(기준)을 설정하여 피벗 값 기준으로 왼쪽으로는 (피벗보다) 작은 값, 오른쪽으로는 (피벗보다) 큰 값을 위..

삽입 정렬 알고리즘 삽입 정렬은 리스트의 범위를 2 -> 3 -> 4개 씩 늘려나가면서 새롭게 추가된 인자를 기존 값들과 비교하는 알고리즘. 설명 1. 아래 인자들이 [2,1] 부터 차례대로 5, 4, 3 입력 받는다고 가정한다. [2, 1, 5, 4, 3] 2. 처음에 두 인자를 비교한 후에 정렬을 수행한다. [2, 1]: 2 > 1 => swap ^ ^ [1, 2] * * 3. 그 다음 기존의 정렬 범위에 한칸을 확장하여 세번째 값을 추가시키고 비교 진행한다. 5와 2를 비교하여 움직임이 없었다는 것은 1과의 비교도 진행할 필요가 없다는 것을 의미하므로 종료하고 다음 인자를 입력 받는다. [1, 2, 5]: 2 OK ^ ^ [1, 2, 5] * * * 4. 4를 입력받은 후에 스와핑을 진..

[출처 DaleSeo] 버블 정렬 알고리즘 버블 정렬은 선택 정렬과 유사한 정렬 방식이다. 선택 정렬은 '최소값'을 확정하고 난 후에 다음 비교로 넘어간 것에 반해 버블 정렬은 바로 직전, 직후 값들을 비교해 나가는 방식을 말한다. 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다. 선택 정렬과 마찬가지로 구현은 쉽지만, 시간복잡도로 봤을 때는 효율적이지 않은 정렬 방식이다. 설명 1. 먼저 4와 3을 비교, 3이 더 작음으로 서로 스와핑한다. [4, 3, 5, 1, 2] ^ ^ 4 > 3 => Swap [3, 4, 5, 1, 2] 2. 이후 4와 5를 비교, 바꿀 필요가 없음을 확인. [3, 4, 5, 1, 2] ^ ^ 4 No Swap 3. 5와 1을 비교, 1이 더 작음으로 서로 스..

항상 알고리즘을 공부해야지 맘잡고 책과 영상을 시작하게 되면 맞이하는 과목(?)이 있다. 바로 정렬이다. 이번 기회에 블로그에 정리하면서 복습하려고 한다. 주로 Google 선생과 Youtube 선생의 소스에서 자료를 얻지만 대표적으로는 [동빈나] 선생님, https://www.daleseo.com/ 블로그 자료를 주로 참고하였다는 것을 미리 밝힌다. '정렬'의 개념은 우리가 흔히 말하는 '오름차순' 이나 '내림차순'으로 데이터를 정리하는 방법들을 정의한다. 선택 정렬 알고리즘 배열 내 여러 인자 값이나 데이터가 있다고 가정해보자. 첫번째 값을 '기준'으로 두고 두번째, 세번째 값과 비교를 진행한다. 이때 뒤(N번째)의 값이 '기준'되는 값보다 작다면, 기준값과 자리를 바꾼다. 이 개념을 도입하여 코드를..

DAGs airflow에서는 워크플로우를 DAG(Directed Acyclic Graph)로 관리. DAGs : 비순환, 방향성을 가지고 있는 그래프를 뜻함. Airflow 웹서버에서 DAGs Task 확인. DAGs - Operator의 모음 DAGs는 Operator(Task) 의 모음이다. 개별 Task 상태 값을 확인하여 재실행, Failed 마킹, Success 마킹 등의 여러가지 개별 작업을 수행할 수 있다. DAGs 작성방법 (주의점) Scope 파이썬 파일 내에 DAG는 전역 스코프에 존재해야 함. dag_1 = DAG('this_dag_will_be_discovered') def my_function(): dag_2 = DAG('this_dag_will_not') my_function()..

데이터 파이프라인 자동화 데이터의 수집, 가공, 적재 프로세스를 자동화 하는 것. 대표적으로 리눅스의 crontab 등의 프로그램을 사용하여 '배치'화 할수있겠지만, 구동 실패시 재실행하는 과정에서 데이터의 규모나, 워크플로우의 규모가 커지게 된다면 점차 어려워짐. 이런 문제점을 보완하기 위해 우리가 자주 사용(?)하는 서비스인 에어비엔비에서 수많은 프로세스를 관리하기 위한 솔루션으로 시작되었음. 기존방식의 문제점 실패복구 - 언제 어떻게 다시 실행할 것인가? 모니터링, 의존성 관리(파이프라인 간 의존성) 확장성 - 분산된 환경에서 파이프라인 관리. Airflow - 워크플로우 관리 도구 워크플로우를 작성하고 스케줄링하고 모니터링하는 작업을 프로그래밍 할 수 있게 해주는 플랫폼 태스크를 정기적인 스케줄로..

이진탐색트리 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진트리. 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다. 트리 구조에 따라서 logN ~ N까지의 시간복잡도를 가질 수 있다. (편향된 이진 탐색트리인 경우, N(높이)만큼의 시간복잡도를 가짐.) 해당 경우를 방지하기 위해 자가 균형트리가 존재. 자가 균형트리 트리가 한쪽으로 편향되지 않도록 삽입, 삭제를 개선한 이진 탐색트리. AVL 트리와 Red black 트리가 존재. 해시 해시에 매핑하여 데이터를 저장하는 방법. '데이터를 저장하는 위치 = 인덱스'를 간단한 연산으로 구하는 것. 원소의 검색뿐만 아니라, 추가&삭제도 효율적으로..