Heap이란? 👉 개념 우선순위큐(Priority Queue)에서 사용되는 자료구조이며, 최대값이나 최솟값을 찾는 데 소요되는 시간이 O(1)이다. 하지만 노드 수정시, 힙구조 유지하기 위해 heapify과정을 거쳐 구조를 유지한다. 이는 결국 O(log n)의 시간 복잡도를 가진다. 👉 특징 Tree 중 배열에 기반한 완전 이진 트리 형식(왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리)을 가지며, 최대힙/최소힙 두 종류가 있다. 최대 힙 key(부모 노드) ≥ key(자식 노드) 최소 힙 key(부모 노드) ≤ key(자식 모드) 완전 이진 트리이기 때문에 삽입/삭제 연산이 배열의 가장 끝에서 발생한다. BST의 경우 삽입/삭제를 위해서 값을 찾아주는 과정이 필요했지만, 힙은 일단 배열의 맨 ..

Binary Search Tree란? 👉 개념 Binary Search Tree(BST)는 효율적인 탐색을 위한 데이터 저장 방법이다. 👉 규칙 노드에 저장되는 키는 유일하다. 부모의 키 값이 왼쪽 자식 노드의 키 값보다 크다. 부모의 키 값이 오른쪽 자식 노드의 키 값보다 작다. 왼쪽과 오른쪽 서브트리도 BST이다. 👉 장단점 장점 탐색 연산 시간복잡도가 O(log N)이다. (명확히 말하면 O(h)) 단점 편향 트리의 경우 저장 순서에 따라서 한 쪽으로만 노드가 추가되는 경우가 발생한다. 최악의 경우는 탐색 시간복잡도가 O(N)이다. 배열보다 많은 메모리를 사용한다. Leetcode 문제를 통한 BST 구현 BST를 직접 구현하는 것이 도움이 될 것이라 생각하여 아래 문제를 풀어보았다. 1. 탐색: ..

데이터를 다룸에 있어서 SQL과 NoSQL을 필수적으로 접해야하는 언어이고, 그 차이도 분명히 할 필요가 있다고 생각했다. 이 전에 정리를 했지만, 좀 더 자세히 정리를 해보기로 했다! 😤 https://deep-flame.tistory.com/7 [DB] 데이터베이스 기초 데이터베이스란? 데이터베이스란 여러 사람들이 공유하고, 사용될 목적으로 통합하여 관리되는 데이터의 집합 데이터 베이스를 사용하기 이전에는 파일 시스템을 이용하여 데이터를 관리했다. deep-flame.tistory.com SQL Structured Query Language의 줄임말로, 관계형 데이터베이스 시스템(RDBMS)에서 자료를 관리 및 처리하기 위해 설계된 언어이다. 👉 SQL 문법의 종류 DDL (Data Definitio..

Cloud를 공부하다보면 컨테이너/도커/쿠버네티스라는 개념이 자주 등장한다. 간단히 말하면 과거 가상머신의 불편함을 해결하고자 컨테이너와 도커라는 개념이 생겨났고, 컴퓨팅 파워가 늘어나다보니 다수의 도커와 컨테이너를 운영해야하는 상황이 발생하여 쿠버네티스가 생겨났다. 해당 글에서는 이 항목들에 대해서 살펴볼 것이다. 도커와 컨테이너 소프트웨어는 OS와 라이브러리에 의존한다. 따라서 성격이 다른 컴퓨터(OS, 라이브러리 버전이 다름)에서 같은 소프트웨어를 실행할 때 어려움을 느낄 수 있다. Docker는 Container기반의 가상화 플랫폼이다. Docker를 사용하여 Container를 생성할 수 있으며, 같은 Container를 여러 개 생성하는 것도 가능하다. 이렇게 위의 문제를 해결할 수 있는 것이..

Spark는 Hadoop의 연산 프레임 워크 중 하나로서, 대규모 통합 분석 엔진으로 가장 범용적으로 쓰이는 기술 중 하나이다. 이에 동작 단계에 대해 좀 더 상세히 알아보기 위해 블로그에 정리해보기로 했다. 해당 자료는 이전에 작성했던 글이다. https://deep-flame.tistory.com/10 [Hadoop] 연산 프레임워크 (feat. MapReduce, Spark, Flink) 대다수 프레임워크는 사용자가 정의하거나 합성한 임의의 연산을 잘게 나눠서 분산 실행한다. Hadoop MapReduce 대용량의 데이터를 분산/병렬 컴퓨팅 환경에서 처리하기 위해 제작된 모델이다. 단순 deep-flame.tistory.com Spark의 동작 단계 크게 5단계로 이루어진다. DataFrame이나 ..

객체 지향 프로그래밍 이란? 현실 세계는 사물(객체)로 이루어져있고, 발생하는 사건들은 사물간의 상호작용을 통해 이루어진다. 여기에서 착안하여 클래스를 이용해 연관있는 객체의 속성과 행위를 하나로 묶고, 그 객체들 간의 상호작용을 구현하는 프로그래밍 방법이다. 장단점 장점 재사용성 남이 만든 클래스를 가져와서 그 속의 속성과 함수를 사용할 수 있고, 상속을 통해 확장하여 사용할 수 있다. 코드 중복 제거 코드의 중복을 제거하여 코드 불일치를 방지할 수 있다. 유지보수 많은 인스턴스들이 한 클래스 내 변수와 함수를 사용한다. 함수에 버그가 있다면 그 부분만 수정하면 따로 인스턴스들의 수정이 필요 없다. 단점 개체 수가 증가하면 용량이 커질 수 있고, 처리 속도가 상대적으로 느리다. 5가지 키워드 1. 추상..

데이터 추출 배치 작업과 데이터 분석 파이프라인은 독립적인 여러 단계로 구성되어있으며, 각 단계마다 다른 기술이 사용될 수 있다. 이런 파이프라인 작업에 대한 오케스트레이션 및 스케줄링과 같은 복잡한 상호 의존 관계를 나타낼 방법이 필요하다. Oozie 하둡에서 사용되는 작업 스케줄링 및 실행 프레임워크이다. 우지서버는 하둡 작업을 직접 실행하지 않고, 하둡 클러스터에 맡기는 아키텍처 덕분에 가볍다 따라서 수백 개의 액션을 동시에 쉽게 실행할 수 있다. 프로세스 Client: XML 파일로 정의된 작업을 제출한다. 처리 과정이 플로우 차트와 비슷하다고 볼 수 있다. Workflow Engine: 기본 실행단위인 액션을 구성하고, 연쇄적으로 함께 실행돼야 하는 액션을 묶어 워크플로우를 구성한다. Sched..

🤔 문제. Palindromic Substring: 거꾸로 뒤집어도 같은 문자열, 예를들어 aaa, baaab 등. 🤗 풀이. 문자열 DP 문제이다. start포인트와 길이를 담을 변수를 지정한다. (기존 Palindromic Substring의 정보를 저장할 용도) for문을 실행하여 end포인트를 이동시켜준다. 특정 조건일 때 start 포인트와 길이를 변경한다. 기존 Palindromic Substring에 end포인트의 문자를 포함했을 때, Palindromic을 만족한다. Ex. aaa 기존 Palindromic Substring에 end포인트의 문자와 Substring의 앞의 문자를 포함했을 때, Palindromic을 만족한다. Ex. baaab HTML 삽입 미리보기할 수 없는 소스

🤔 문제. 2차원 배열을 시계방향으로 돌리는 간단한 문제입니다. 🤗 풀이. [단순 구현] 처음 풀었던 방식은 순수한 구현이었다. 끝에서 부터 한 바퀴씩 돌며 좌표를 담는 xy_list와 값을 담는 v_list를 만든 뒤, v_list 값을 수정해서 matrix를 재구성하였다. 통과는 했지만, 실행 시간이 오래걸렸다. HTML 삽입 미리보기할 수 없는 소스 [간단한 방법] 위에서는 2차원 배열을 1차원 배열로 바꿔서 풀려는 시도를 했다. 하지만 2차원 배열을 전체적으로 움직이며 푸는 방법이 있었다. matrix를 행을 중심으로 뒤집는다. matrix를 대각선을 중심으로 뒤집는다. HTML 삽입 미리보기할 수 없는 소스 실행속도는 2배 정도 차이난다... 역시 알고리즘 문제는 구현 전에 생각을 해야한다! 😓

맵리듀스와 스파크가 아주 유연하고 강력한 프레임워크이긴하지만, 이를 사용하려면 개발/배포/운영에 익숙해야한다. 하지만 대부분의 분석 기법은 SQL을 기반으로 하며, 복잡한 절차없이 분석 작업이 선호될 때가 있다. 그래서 하둡에 저장되는 데이터를 SQL과 비슷한 인터페이스로 사용할 수 있게 해주는 도구를 들이 생겨났다. 이들은 내부적으로 맵리듀스나 스파크를 근간으로하지만, 독자적인 연산 엔진을 갖춘 것도 있다. 각 엔진은 데이터를 쿼리하거나 대량 데이터를 저장하는 데 중점을 둔다. Hive 하둡에 사용되는 데이터 웨어하우징 기술이다. HDFS에 저장된 정형 데이터를 하이브QL로 쿼리할 수 있게 만든 최초의 기술이다. 이는 ETL, 대용량 데이터 처리, 오프라인 배치 작업, 보고서 데이터 생성 등에 적합하다..