DataScience

데크(Deque) : 앞ㆍ뒤 양쪽 방향에서 엘리먼트를 추가하거나 제거 보통의 큐(Queue)나 스택(Stack)의 경우 한방향으로 진행되지만 Deque의 경우 양쪽 방향으로 엘리먼트를 추가하거나 제거할수 있으며 일반적인 리스트가 삽입이나 제거를 할경우 O(n)이 걸리지만, Deque의 경우 O(1)로 굉장히 빠르다. 1. Deque의 특징 1. 시작점의 값을 넣고 빼거나, 끝 점의 값을 넣고 빼는 데 최적화된 연산 속도를 제공한다. 2. 삽입 / 삭제 연산이 빈번한 알고리즘에서 시간복잡도가 O(1)이므로 빠른 속도를 보여준다. 2. Deque 라이브러리 from collections import deque 3. 파이썬의 Deque 연산 1. deque.append(): Deque의 뒤에 엘리먼트를 삽입한..

구간 합(Prefix sum) : 합 배열을 이용하여 시간 복잡도를 줄이기 위한 목적 n개의 수들이 존재하고 0의 인덱스의 위치부터 n번째 인덱스까지의 합을 구한다고 했을때 다음과 같이 두가지 방법이 존재한다. 부분 합 (Partial sum) - 시간복잡도 O(N) 처음부터 특정인덱스까지의 합을 의미하며 반복분과 같은 누적합을 이용하여 처음위치부터 정해진 위치까지 n번 돌면서 더해주는것을 의미한다 구간 합(Prefix sum) - 시간복잡도 O(1) 특정 구간의 합을 의미하며, 각각의 숫자까지의 합을 계산하여 별도 리스트에 저장해 놓고 저장한값을 사용하는 것을 의미한다. 1. 합 배열 공식 # 합 배열 공식 S[i] = S[i-1] + A[i] # i번째까지의 합 = (i-1) 번째까지의 합 + i번째..

● 서로소[Disjoint] 집합 : 서로 중복 포함된 원소가 없는 집합 (교집합 x) 1. 서로소 집합의 특징 1. 서로소 집합을 표현하는 방법으론 연결 리스트와 트리 방식이 있다. 2. 서로소 집합의 자료구조는 Union-find 자료구조라고 불린다. 3. 두 집합의 서로소를 파악할수 있다면, 각 집합이 어떤 원소를 공통으로 가지고 있는지 알수 있다. 2. 서로소 집합 과정 1. make-set(x) : 모든 원소를 초기화시켜주어 새로운 집합을 생성하는 과정 for i in range(1, v+1): parent[i] = i # 맨 처음은 자기자신의 인덱스의 값을 부모로 가지도록 설정하여, 최종적인 루트노드를 찾아가면 바꿔준다. 2. find-set(x) : 특정 원소가 속한 집단이 어떤 집단이 찾는..

그래프 : 그래프는 노드와 엣지로 구성된 집합이며, 즉 서로 다른 객체가 연결되어 있다고 생각하면 된다. 1. 그래프 기초 노드 (node) : 독립된 개체로 동그라미로 표현 에지 (edge) : 노드와 노드를 연결하는 연결선 아크 (arc) : 방향성을 가진 엣지 인접 (adjacency) : 정점 v와 정점u에 간선이 있다면, '인접하다'고 한다. 차수 (Degree) : 진입차수(정점으로 들어오는 간선의 수)와 진출차수(정점을 나가는 간선의 수)의 합이다. 경로 (path) : 정점에서 다른 정점까지의 경로는 정점의 순서이다. 2. 그래프 구현 2.1. 인접 리스트 (adjacency list) : 파이썬의 리스트를 이용하여 노드 개수만큼 리스트를 선언하는 방식 정점 하나에 인접한 모든 정점을 순서..

● 병합[Merge] 정렬 : 데이터를 분활하고 분활한 집합을 정렬하여 합침 병합정렬의 경우 배열을 앞과 뒤로 나눠서 각각 최소 단위(1)까지 분활하고 분활한 집합을 정렬하며 합치는 알고리즘이다. 1. 병합 정렬의 특징 1. 병합 정렬의 시간 복잡도는 O(nlogn)으로 2. 병합 정렬은 n개의 개체가 있다면 O(n)만큼의 추가 공간이 필요 2. 병합 정렬 과정 1. Divide [O(1)] : n개의 값을 1개가 남을때까지 두 개의 n/2 keys로 계속 나눈다. 2. Merge [2T(n/2)] : 합병정렬을 사용하여 두 개의 배열을 정렬한다. 3. Combine [O(n)] : 두 개의 정렬된 배열을 원래 하나의 배열로 만든다. - 병합의 과정에서 투 포인터의 개념을 사용하며 반드시 숙지 할 것!!..

정렬 : 이름, 암호, 회사 등의 키를 항목값의 정해진 기준에 따라 데이터 집합을 일정한 순서로 바꾸어 재설정하는 것을 말한다. 일반적으로 작은 데이터부터 시작하는 것을 오름차순(ascending) 정렬이라 하고, 큰 데이터부터 시작하는 것을 내림차순(descending) 정렬이라고 합니다. 정렬 알고리즘의 경우 아래 그림과 같이 여러가지 있으며 각기 다른 방법과 효율성을 보여준다. 단순 정렬 (버블, 선택, 삽입) ● 버블[Bublle] 정렬 : 두 인접한 데이터의 크기를 비교해 정렬 = 단순 교환 정렬 1. 버블 정렬의 특징 1. 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 느린편이다. 2. 인접한 데이터의 크기만을 비교하므로 간단하게 구현이 가능하다. 2. 버블 정렬 과정 1. 비교 연산이..

탐색 : 주어진 많은 양의 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 의미한다. 주어진 데이터의 유형에 따라 적절한 탐색 알고리즘을 사용하는 것이 중요하며, 탐색의 대표적인 알고리즘으로 DFS와 BFS가 있다. 그런데 DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 필요하며 재귀함수 역시 사용하므로 선행학습이 필요하다. [자료구조] 스택(Stack)과 큐(Queue) ● 스택[Stack] : 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조 스택이란 프링글스의 과자를 위에서부터 꺼내 먹는 것처럼 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조를 말합니다. sjm2449.tistory.com DFS와 BFS의 근본 근본적인 것은 처음부터 끝까지 모든 노드들을..

● 스택[Stack] : 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조 스택이란 프링글스의 과자를 위에서부터 꺼내 먹는 것처럼 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조를 말합니다. 위의 그림을 보면 empty stack에 새값이 하나씩 들어가고, 스택에서 값을 빼낼 때는 제일 위에 있던 값이 나오게 되는 것을 볼수 있다. 파이썬에서는 리스트를 이용하여 쉽게 스택을 구현할수 있다. 1. 스택의 특징 1. 후입선출은 삽입과 삭제가 한 쪽으로만 일어나는 특징을 가지고 있다. 2. 스택에서 데이터에 바로 접근이 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1) 이다. 3. 파이썬에서 스택을 사용할때 별도의 라이브러리가 필요없다. 4. 깊이 우선 탐색[DFS], 백트래킹 등의 알고리..