힙(Heap) 힙 자료구조는 일종의 트리다. 힙은 형태 속성과 힙 속성을 만족해야 하는데, 즉 힙은 완전이진트리 구조여야 하며 힙 속성을 가져야 한다. 완전이진트리는 이전 글에서 작성한 것처럼 마지막 레벨을 제외한 모든 노드가 다 채워져 있는 이진 트리이며, 마지막 레벨은 왼쪽에서 오른쪽으로 채워져 있는 트리이다. 힙 속성은 각 노드의 데이터들은 각각의 자식 노드의 데이터보다 크거나 같은 속성을 말한다. 힙 구현하기 힙 자료구조 또한 완전이진트리 형태를 가지고 있으므로 동적 배열로 나타낼 수 있다. 즉, 파이썬에서는 리스트로 힙 자료구조를 표현할 수 있다. 아래는 최대힙을 구현한 코드이다. 간단하게 heapify, heappop, heappush함수를 구현했다. def _swap(arr, index_1,..

분리 집합 (Disjoint Set) 분리 집합은 서로소 집합이라고도 한다. 전체 집합 U에 대해 U의 분리 집합 A, B는 다음 조건을 만족한다. A, B는 U의 부분집합이다 A, B는 서로 공통 원소를 가지지 않는다 A, B의 합집합이 곧 전체집합 U이다. 즉, 전체 집합 U를 겹치는 부분이 발생하지 않도록 모든 원소를 분리시킨 집합을 분리 집합이라고 한다. 분리 집합은 일반적으로 두 원소가 같은 집합에 속하는지 빠르게 여부를 확인하거나, 두 집합을 합치는 등의 연산을 할 때 사용된다. 예를 들면 SNS에서 A라는 사람과 B라는 사람이 친구 관계인지 여부를 확인하거나, 친구를 맺었다면 두 집합을 합치는 연산을 할 수 있다. 분리 집합은 대표적으로 트리 자료 구조와 Union-Find 알고리즘으로 구현..

1. 분석기획 방향성 도출 01. 분석기획의 특징 가. 분석기획이란? 실제 분석을 수행하기에 앞서 분석을 수행할 과제를 정의하고, 의도했던 결과를 도출할 수 있도록 이를 적절하게 관리하는 방안을 사전에 계획하는 작업 어떠한 목표(What)를 달성하기 위해(Why) 어떠한 데이터를 가지고 어떤 방식으로(How) 수행할 지에 대한 일련의 계획을 수립하는 작업이므로 성공적인 분석 결과를 도출하기 위한 중요한 사전 작업임 02. 분석 대상과 방법에 따른 네가지 분석 주제 유형 분석은 분석의 대상(What)과 분석의 방법(How)에 따라 4가지로 나누어진다 특정한 분석 주제를 대상으로 진행할 경우에도, 분석 주제 및 기법의 특성 상 4가지 유형을 넘나들면서 분석을 수행하고 결과를 도출하는 과정을 반복함 (1) O..

문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 커서를 L, D, B, P 명령어를 통해 이동하거나 커서 왼쪽에 문자를 삭제하고 추가하고 최종 결과를 출력하는 문제 전략 01. 리스트 import sys string = list(sys.stdin.readline().rstrip()) M = int(sys.stdin.readline().rstrip()) cursor = len(string) for _ in range(M): ins = sys...

일반 트리(General Tree) 일반적인 트리는 노드들의 집합으로, 하나의 루트 노드와 서로 겹치지 않는 여러 개의 부분 집합으로 이루어진 나머지 노드들로 구성되어 있다. 트리에서는 노드들 간에 상하관계인 부모-자식 관계가 만들어진다. 즉 부모와 자식 간의 레퍼런스가 있어 서로의 노드를 식별할 수 있다. 일반 트리는 자식 노드 수의 제한이 없기 때문에 무한정 늘어날 수 있는 특징이 있으며, 이로 인해 노드의 수를 파악하기 어려우므로 알고리즘을 적절하게 사용하기 어렵다. 따라서 주로 일반 트리를 이진 트리로 변환해 사용한다. class Node: def __init__(self, data) -> None: self.data = data self.children = [] root = Node(1) nod..

1. 빅데이터 분석과 전략 인사이트 01. 빅데이터 열풍과 회의론 빅데이터 열풍으로 인한 회의론도 있는데, 이런 회의론으로 인해 실제 우리가 빅데이터 분석에서 찾을 수 있는 수많은 가치들을 제대로 발굴해 보기도 전에 그 활용 자체를 사전에 차단해버릴 수도 있음. 02. 빅데이터 회의론의 원인 및 진단 가. 투자효과를 거두지 못했던 부정적 학습효과 과거 거액을 들여 고객관계관리(CRM)을 도입했던 기업들이 어떻게 활용하고 어떻게 가치를 뽑아내야 할지 난감해 했으며 생각 이상의 효과를 거두지 못했음 나. 빅데이터 성공사례 중 기존 분석 프로젝트를 포함해 놓은 것이 많다 국내 빅데이터 업체들이 CRM분석 성과를 빅데이터 분석으로 과대포장 03. 일차원적인 분석 vs 전략도출을 위한 가치기반 분석 일차적인 분석..

해시 테이블(Hash Table) 해시 테이블은 key-value형태로 데이터를 저장하는 자료구조로, 일반적인 경우 O(1)의 시간복잡도로 값을 탐색할 수 있다. 1. Direct Access Table 우리가 저장할 key-value 쌍들이 있을 때 key값 중 가장 큰 숫자만큼의 배열을 생성한 뒤 해당 인덱스에 value를 저장하면, value에 접근하고 싶을 때 key를 통해 바로 접근할 수 있으므로 O(n)의 시간복잡도를 가진다. 이를 Direct Access Table이라고 한다. data = [(57, "고영희"), (208, "강아지"), (900, "고릴라")] max_index = 0 for key, value in data: if key > max_index: max_index = ke..

1. 빅데이터의 이해 01. 빅데이터의 이해 가. 빅데이터의 정의 특징 설명 3V 양 (Volume) - 데이터의 크기 - 생성되는 모든 데이터를 수집 다양성 (Variety) - 데이터의 다양성 - 정형화된 데이터를 넘어 텍스트, 오디오, 비디오와 같은 모든 유형의 데이터를 분석 대상으로 함 속도 (Velocity) - 데이터의 수집과 처리의 속도 4V 가치 (Value) - 빅데이터를 활용해 유용한 가치를 끌어낼 수 있음 5V 신뢰성 (Veracity) - 방대한 양의 데이터에서 오류 제거를 통해 데이터 품질 및 신뢰성 재고 필요 7V 정확성 (Validity) - 아무리 규모가 큰 데이터라도 질 높은 분석을 통한 데이터 타당성이 중요 휘발성 (Volatility) - 데이터가 얼마나 오래, 타당하게..

1. 데이터와 정보 01. 데이터의 정의와 특성 가. 데이터의 정의 데이터는 추론과 추정의 근거를 이루는 사실임 데이터는 단순한 객체로서의 가치뿐만 아니라 다른 객체와의 상호관계 속에서 가치를 갖는다 나. 데이터의 특성 구분 특성 존재적 특성 객관적 사실(Fact, Raw Material) 당위적 특성 추론, 예측, 전망, 추정을 위한 근거(Basis) ❗"객관적 사실로서 개별 데이터는 중요하지 않다" 데이터가 축적되고 서로 비교가 가능할 때 그 의미가 있음 02. 데이터의 구분과 유형 가. 데이터의 구분 구분 형태 예 특징 정성적 데이터(Qualitative Data) - 언어, 문자 등 형식이 정해져 있지 않음 - 회사 매출이 증가함 - 설문 조사 주관식 응답 - 비정형 데이터 - 주관적 내용 - 통..

큐(Queue) 선입선출(First-In First-Out, FIFO)특징을 가진 자료구조다. 즉, 가장 나중에 들어온 자료가 가장 먼저 나가도록 되어 있다. 커스텀 큐 구현 싱글리 링크드 리스트로 큐를 구현해보자. 스택과 차이점은 한쪽 끝에서 연산이 이루어 지는 게 아니라 양쪽에서 각각 삽입과 인출이 일어난다는 것이다. 따라서 레퍼런스를 front와 rear로 두고 rear측에 새로운 노드가 삽입되고, front측에서 노드가 나가는 형태로 구현을 해야 한다. from typing import Iterable, Optional class Node: """싱글리 링크드 리스트 노드""" def __init__(self, data) -> None: self.data = data self.next = None..