목록분류 전체보기 (105)
yoongrammer
목차 다음 순열(next permutation) 알고리즘 next permutation 은 현재 순열보다 큰 다음 순열을 찾는 알고리즘입니다. [1, 2, 3]이 최초 숫자 배열로 주어진 경우 사전순으로 배열된 모든 가능한 순열은 아래와 같습니다. 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 [1, 2, 3] = 다음으로 큰 순열은 [1, 3, 2]입니다. [1, 3, 2] = 다음으로 큰 순열은 [2, 1, 3]입니다. ... [3, 2, 1] = 가장 큰 순열이기 때문에 다음으로 큰 순열은 없습니다. 동작 방식 다음 순열을 얻으려면 피벗 포인트(Pivot Point)를 사용합니다. 피벗 포인트는 교환, 분할 등의 작업을 수행하기 위한 기준이 되는 위치나 값입니다. next perm..
목차 머신 러닝으로 시계열(Time Series) 데이터 예측하기 머신 러닝은 시계열 데이터를 예측하는데 자주 사용됩니다. 시계열(Time Series)란? Time series(시계열)란 일정 시간 간격으로 측정된 데이터의 시퀀스를 말합니다. 시간은 보통 초, 분, 시간, 일, 주, 월, 분기, 연도 등의 단위로 표현되며, 주식 가격, 기온, 수익률, 판매량, 웹 사이트 트래픽 등과 같은 많은 현실 세계의 데이터가 시계열로 표현됩니다. 다음은 책 판매량에 대한 시계열 데이터입니다. book_sales.head() plt.plot(book_sales) plt.ylabel('Book') plt.xlabel('Date') plt.title('Time Plot of Book Sales') Linear Regr..
목차 판다스(Pandas) 데이터 선택하기 (Selection) Pandas는 DataFrame 또는 Series 개체의 특정 부분을 검색하고 조작할 수 있는 다양한 데이터 선택 방법을 제공합니다. select를 설명하기 위해 사용하는 DataFrame은 다음과 같습니다. Selecting Columns DataFrame에서 열의 하위 집합을 선택하려면 다음 구문을 사용해야 합니다. df[column_list] column_list: 선택하려는 열 이름의 목록 다음은 A행을 가져오는 예입니다. df['A'] # output 2023-02-18 0.509482 2023-02-19 0.966399 2023-02-20 0.857979 2023-02-21 0.701611 2023-02-22 0.102038 20..
목차 판다스(Pandas) 데이터 구조 알아보기 판다스(Pandas)는 python으로 만들어진 데이터 처리 및 분석을 위한 라이브러리입니다. 판다스 데이터 구조를 알아보기 위해선 아래와 같이 모듈을 import 합니다. import pandas as pd import numpy as np 데이터 구조 Pandas에서 데이터를 저장하기 위한 객체로 DataFrame과 Series가 있습니다. DataFrame Pandas에서는 데이터 테이블을 DataFrame이라고 합니다. DataFrame은 column label과 row label(=index)를 가지고 있는 2차원 배열 구조입니다. 열에는 다양한 유형의 데이터(문자, 정수, 부동 소수점, 범주형 데이터 등)를 저장할 수 있습니다. DataFrame..
목차 Lower bound & Upper bound 개념 및 구현 Lower bound와 Upper bound는 경곗값을 찾는 알고리즘입니다. Lower bound와 Upper bound는 이진 탐색을 기반으로 하기 때문에 데이터가 정렬되어 있어야 합니다. 이진 탐색을 기반으로 하기 때문에 두 알고리즘의 시간 복잡도는 O(log n) 입니다. (n: 배열 길이) Lower bound Lower bound는 특정 값의 시작 위치를 찾는 알고리즘입니다. 동작 방식 Lower bound의 동작 방식은 다음과 같습니다. 초기에 left는 배열의 시작 위치로 right는 배열의 길이로 셋팅합니다. 배열의 중간 값(mid)을 가져옵니다. 중간 값과 검색 값을 비교합니다. 중간 값이 검색 값보다 작다면 left 값을..
목차 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT) 펜윅 트리(Fenwick Tree)는 세그먼트 트리의 변형으로 수열의 구간 합을 빠르게 구할 수 있도록 고안된 자료 구조입니다. 펜윅 트리는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. 펜윅 트리는 세그먼트 트리처럼 O(logN) 시간으로 구간 합을 구할 수 있으며 세그먼트 트리에 비해 적은 공간이 필요하고 구현하기 쉽다는 장점이 있습니다. 펜윅 트리 구성 배열 A를 가지고 세그먼트 트리를 만들면 다음과 같습니다. 각 노드에는 구간합 정보가 들어 있습니다. 위 세그먼트 트리에서 각 층에에서 짝수 인덱스를 무시하면 아래와 트리를 얻을 수 있습니다. 이러한 구조를 펜윅 트리라고 합니다. 주어..
목차 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree)는 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조입니다. 다음 예를 보겠습니다. A = {1, 2, 3, 4, 5 … ,N} 라는 배열에 아래 연산을 M번 수행한다고 생각해봅시다. 배열의 범위 합을 구하는 Query 연산 A[0] + A[1] + A[2] + … + A[N-1] i번째 배열 값을 v로 변경하는 Update 연산 A[i] = v 단순한 방법으로는 각각 배열에 접근하여 연산을 한다면 시간 복잡도는 1번 연산 O(N), 2번 연산 O(1)이 됩니다. 이 두 연산을 M번 수행한다면 총 시간 복잡도는 O(MN)+O(M) = O(MN)이 됩니다. 세그먼트 트리를 사용하면 범위 최소/최대 및 합계 Query 및..
목차 서로소 집합(Disjoint Set) & 유니온 파인드(Union find) 서로소 집합(Disjoint Set) Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말합니다. Disjoint set 자료구조를 사용하면 서로 다른 원소들이 같은 집합에 속해있는지, 혹은 속해있지 않은지를 판별하는 데에 유용하게 사용할 수 있습니다. Disjoint set 자료구조는 MakeSet, Union, Find라는 연산을 제공합니다. MakeSet MakeSet 연산은 주어진 요소만 포함하는 집합을 생성합니다. 이 연산에서 parent 배열을 생성합니다. parent 배열은 노드의 부모 노드를 저장하고 있습니다. 부모 노드가 없다면 자기 자신을 가리..
목차 캐시(Cache) 란? 캐시(Cache)는 자주 사용하는 데이터나 값을 미리 복사해 놓는 임시 저장소입니다. 속도 향상을 위해 캐시를 사용하며, 다음과 같은 상황에서 캐시를 주로 사용합니다. 원본 데이터보다 빠르게 접근 가능할 때 같은 데이터에 반복적으로 접근할 때 변하지 않은 데이터를 주로 사용할 때 레디스(Redis)는 단순한 구조와 in-memory저장소로 인한 빠른 성능 때문에 캐시에 주로 쓰입니다. 캐싱 전략(Caching Strategies) 캐시로 사용할 때 어떻게 배치하는지가 시스템 성능에 큰 영향을 끼치는데 이를 캐싱 전략(Caching Strtegies)이라고 합니다. Look-Aside Look-Aside는 데이터를 찾을 때 우선 캐시에서 데이터를 찾고 데이터가 있다면 캐시에서..
목차 의존성 역전 원칙 (DIP: Dependency Inversion Principle) 1. 상위 모듈은 하위 모듈에 의존해서는 안 되고 둘 다 추상화에 의존해야 한다. 2. 추상화는 세부 사항에 의존해서는 안 되고 세부사항(구체적인 구현)은 추상화에 의존해야 한다. 로버트 C. 마틴 의존성 역전 원칙(DIP)은 변화하기 쉬운 것에 의존하지 말라는 원칙입니다. DIP를 지킴으로써 하위 모듈(or 클래스)에 대한 상위 모듈(or 클래스)의 종속성을 줄일 수 있습니다. 상위 모듈(or 클래스): 도구로 작업을 실행하는 클래스 하위 모듈(or 클래스): 작업을 실행하는데 필요한 도구 DIP 적용 전 다음 예를 보겠습니다. Calculator 클래스가 Add클래스를 사용하여 덧셈을 하는 예입니다. 여기서 C..