1. 동적계획법? 다이나믹 프로그래밍(dynamic programming) ‘하나의 문제는 단 1번만 풀도록 하는 알고리즘’ 2개의 가정 하에 사용할 수 있다 1-1) 큰 문제를 작은 문제로 나눌 수 있다. 1-2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 각각을 처리한 다음 나중에 전체의 답을 구하는 것 이 과정에서 이미 계산한 결과는 배열에 따로 저장한다음 나중에 동일한 계산을 할때 저장된 값을 단순히 호출하여 반환하기만 하면 된다 2. 피보나치 수열 피보나치 수열의 점화식은 $$a_{n}=a_{n-1}+a_{n-2}$$ 특정한 위치의 숫자를 구하기 위해 바로 이전의 숫자와 두번 이전의 숫자의 합을 구함 초기..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12941 코딩테스트 연습 - 최솟값 만들기 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱 programmers.co.kr 길이가 같은 배열 A,B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A,B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이 때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. 단 각 배열에서 k번째 숫자를 뽑았다..
1. 확률적 경사하강법(stochastic gradient descent method, SGD) 모든 데이터를 사용하는 것이 아닌 매 스텝마다 데이터 1개를 sampling하여 각 스텝마다 gradient를 계산한 경사하강법 목적식이 볼록(convex)이 아니면 확률적 경사하강법을 이용하여 최적화 할 수 있다. 또한 데이터 세트가 매우 클때 일반적인 경사하강법은 속도가 너무 느려져서 매 스텝마다 일부 데이터만 사용하는 확률적 경사하강법을 이용하여 속도를 높일 수 있다. 연산량에 있어서 효율적임 만능은 아니지만 딥러닝에서는 일반적인 경사하강법보다 낫다고한다 그림1을 보면 데이터의 일부를 사용하여 추정한 그래디언트 벡터의 기댓값이 실제 그래디언트 벡터에 근사한다 데이터를 확률적으로 선택하기 때문에 안정적으로..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 로또 6/45(이하 ‘로또’)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 ..
벡터의 norm은 벡터 사이 거리로 정의된다. 그런데 벡터 사이 거리를 어떻게 정의할까? 일반적으로 유클리드 거리를 생각하지만 사실 거리를 정의하는 방법은 다양하다 임의의 n차원에서 거리를 정의한다는 것이 중요하다. 첫번째는 L1 norm, 두번째는 L2 norm이라고 부른다 1. L1 norm의 기하학적인 의미 L1 norm이란 원점에서 x까지의 거리를 위 그림에서 빨간 선분의 총 길이로 정의하는 것이다. 2. L2 norm의 기하학적 의미 L2 norm은 x까지의 거리를 위와 같이 직선거리로 정의하는 것이다. 3. norm에 따른 원 원은 원점에서 거리가 r인 점의 집합이라는 사실로부터 3-1) L1 norm을 사용한 원 robust 방법, lasso 회귀 등에서 사용 3-2) L2 norm을 사용한..
k-fold validation이라고도 한다. 보통 모형의 성능을 높이기 위해서 주어진 전체 data를 train data + validation data와 test data로 나눈다. train data는 학습을 위해 사용되는 부분이고 validation data는 학습한 모형의 성능을 평가하면서 hyperparameter를 튜닝하기 위해 사용한다. test data는 오직 최종 모형의 성능을 평가하기 위해서만 사용한다. 그런데 이들을 어떻게 나눠야 할까? train data를 k개의 fold로 나누고 그 중 k-1개를 train, 나머지 1개를 validation data라 하고 학습을 진행한다. 1-1) k-1개를 선택하는 모든 경우에 대해 반복하여 진행하고 그들의 적절한 평균으로 최종 모형 선택 ..
