[생각의 흐름] 1. 수열의 앞에서 부터 하나하나 더하면서 수열의 연속 된 특정 범위 내에서 K값을 찾는다. 2. 수열이 연속해야하기 때문에 맨 앞의 수열은 빼고 맨 뒤의 수열은 넣는 방법 두 가지가 있다. 3. K보다 값이 크면 맨 앞의 수열을 빼고(Pop) K보다 값이 작으면 맨 뒤에 수열을 추가한다(Push). 4. K와 값이 같으면 cnt++; * 맨 처음에는 수열(signal A)를 배열에 초기화 하여 사용하려 했으나 메모리 초과가 발생하여 그때 그때 값을 만들어 내는 방식을 택함. /* https://www.algospot.com/judge/problem/read/ITES */ #include #include #include using namespace std; const long MOD = ..
[생각의 흐름] 1. 모든 경로(or 경우의수)를 완전 탐색 해본다. 2. 교도소의 인접한 마을(시작점)에서 탐색을 시작하는 경우 앞의 과정에서 계산한 확률 값이 필요하다. -> 까다로운 점 3. 시작점과 끝점을 뒤집어서 생각해 본다. 4. 끝점에서 시작해서 교됴소의 인접한 마을(시작점)으로 가는 경우만 구해서 확률을 계산한다. /* https://www.algospot.com/judge/problem/read/NUMB3RS# */ #include #include const int MAX_TOWN = 51; const int MAX_DAY = 101; int townMap[MAX_TOWN][MAX_TOWN]; double cache[MAX_DAY][MAX_TOWN]; int numOfConnectedTo..
[생각의 흐름] 1. 위에서 아래로 정사각형을 x개씩 채워나간다. 2. 직전 윗칸에서 채운(사용한) 사각형의 갯수와 현재 칸에 채우려는 사각형의 갯수를 알면 경우의 수를 구할 수 있다. ( 윗칸에서 채운 사각형의 수 + 현재 칸을 채우려는 사각형의 수 - 1) 3. 재귀함수를 통해 모든 경우의 수를 구한다. 4. 직전 윗칸에서 채운(사용한) 사각형의 갯수와 현재 사용할 수 있는 남은 사각형(leftBlock)의 갯수를 통해 메모이제이션이 가능하다. /* https://www.algospot.com/judge/problem/read/POLY */ #include #include const int MAX_BLOCK = 101; const int MOD = 10000000; int cache[MAX_BLOCK..
[생각의 흐름] 1. 전체 타일설치 경우의 수를 구한다. 2. 대칭인 타일설치 경우의 수를 구해서 뺀다. 3. 대칭인 타일의 경우의 수를 구하는 방법을 n이 짝수일때 홀수일때로 나눈다. 4. n이 짝수인 경우 다시 두가지 경우로 나눌 수 있는데 하나는 n/2로 대칭인 경우와 다른 하나는 전체 타일 가운데를 2x2타일을 배치한 뒤 절반으로 나누는 방법이다. (n-2)/2 n이 홀수인 경우는 자연스럽게 정가운데 타일 하나는 무조건 2x1타일을 배치해야 하기 때문에 (n-1)/2이 된다. 5. 타일의 경우의 수를 나눈 뒤 왼쪽 타일만 채워주면 모든 대칭 타일의 경우의 수를 구할 수 있다. 6. modulo연산에서 주의 할 점이 있는데 (전체 타일의 경우의 수 % MOD) - (대칭인 타일의 경우의 수 % MO..
1. MLflow란 무엇이고 왜 쓰는 것인가? MLflow는 통상적인 머신러닝 워크플로우에서 모델링 및 훈련, 평가, 배포 부분을 도와주는 툴이라고 생각하면 쉽다. 아래의 그림에서 형광색 사각형의 부분을 주로 도와준다고 볼 수 있다. 2. MLflow에서 제공하는 기능 MLflow는 4가지 컴포넌트로 구성되어 있고 각각의 컴포넌트는 다음과 같은 기능을 제공한다. Tracking : 트래킹은 모델 트레이닝 실험 과정에서 나오는 메타데이터, 데이터, 결과물등을 저장할 수 있는 기능이다. 저장 된 내용을 통해 실험을 추적 할 수 있게 도와준다. Projects : MLflow를 사용한 프로젝트를 yaml파일을 통해 패키징 하여 다른 플랫폼에서도 쉽게 사용할 수 있도록 도와준다. Models : 다양한 ML라이..
머신러닝에서 모델을 학습할 때 Raw Data(db, parquet, BigQuery등)에서 Feature를 뽑아서 사용한다. Feature란 테이블의 컬럼 중에서 설명변수(=예측변수)에 해당한다. 1. Feature Store가 필요한 이유 Feature Store가 없는 경우 아래와 같이 ML모델과 RawData간에 직접적인 의존성이 생긴다. 이렇게 될 경우 Feature를 재사용하기 힘들고 ML개발자가 직접 Feature까지 신경써야하는 문제점이 있다. 이러한 문제를 해결하기 위해 도입된게 Feature Store이다. 아래의 그림처럼 ML모델과 RawData사이에 Feature Store를 도입함으로써 이미 정의한 Feature를 재사용하고 ML모델과 RawDatat사이의 직접적인 의존성을 제거할..
[생각의 흐름] 1. 비오는날(75%)와 비가오지 않는날(25%)을 구분한다. 2. 비오는날과 비가오지 않는 날의 확률을 각각 곱하면서 목적지 (n)에 도달할 때까지 반복해 본다. => 완전탐색 3. 중복되는 경로의 확률을 메모이제이션 한다. 4. m일 안에 목적지 n에 도달했을 경우 1을 리턴하여 모든 경로의 확률을 곱하고 그렇지 않은 경우 0을 리턴하여 경우를 무효화 시킨다. 5. 절대 도달할 수 없는 경우( 예) 1000미터 우물을 100일 안에 도달)는 sol함수를 호출하지 않고 수식으로 가지치기 한다. /* https://www.algospot.com/judge/problem/read/SNAIL */ #include const int MAX_DAYS = 1001; const int MAX_MET..
[생각의 흐름] 1. 최대 경로를 먼저 cache한다. (https://d-yong.tistory.com/107 와 동일) 2. 아래로 가는 경우 / 오른쪽 아래로 가는 경우 중 최대 경로가 큰 값을 경우의 수에 추가한다.(단, 두 값이 같은 경우 두 경우의 수를 모두 더한다.) /* https://www.algospot.com/judge/problem/read/TRIPATHCNT */ #include #include #include using namespace std; const int MAX_SIZE = 101; int n; int triangle[MAX_SIZE][MAX_SIZE]; int cache[MAX_SIZE][MAX_SIZE]; int cacheCnt[MAX_SIZE][MAX_SIZE]; ..
[생각의 흐름] 1. 타일을 채우는 방법은 2개이다. 1) 세로로 채우는 방법 2) 가로로 채우는 방법 -> 결국 4X4타일이 됨 2. 타일을 n번째 까지 채웠을 때 그 이후 n+1 타일 부터 채우는 경우의 수를 개싱할 수 있다. #include #include const int MOD = 1000000007; const int MAX_TILE_SIZE = 111; int N; int cache[MAX_TILE_SIZE]; int sol(int n) { if(n == N) return 1; if(n > N) return 0; int &ret = cache[n]; if(ret != -1) return ret; // 타일을 세로로 쓰는 경우 + 타일을 가로로 2개 쓰는 경우 ret = (sol(n+1) % ..
[생각의 흐름] 1. 주어진 입력을 정렬하면 구현이 더 편해진다. 2. 정렬한 뒤 어떠한 기준에 따라 S개로 묶는다(양자화) 3. 어떠한 기준을 정의한다. -> a번째 부터 b번째 까지의 수열에 있는 모든 자연수 중 하나를 선택하여 오차 제곱의 합이 최소가 되는 값을 구한다. (minQuan 함수) /* https://www.algospot.com/judge/problem/read/QUANTIZE */ #include #include #include #include using namespace std; const int MAX_SEQ_SIZE = 111; const int MAX_QUAN_SIZE = 11; const int INF = 987654321; int N, S; int num[MAX_SEQ_S..
