MG

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 배낭문제와 유사한 풀이방식이다. dp[k]는 k원이 되는 동전의 구성 경우의 수이다. 이를 중복없이 계산하기 위해서 1번째 동전을 1~k원까지 채워넣고 그리고 2번째, 3번째 ... n번째 동전까지 경우의 수를 고려한다. 그렇게 되면 j번째 동전에서 그 전 동전이 이미 반영이 다 되고 더 이상 반영이 안되기에 중복이 안되게 된다. 그래서 dp[j]에 dp[j - arr[i]] 를 계속 더해주고 dp..

neural network는 여러 기능을 할 수 있는데 그 중 하나가 논리 게이트이다. 위 그림에서는 대표적으로 AND, OR 게이트를 예시로 들었다. 간단하게 설명하자면 AND 게이트는 두 입력변수 중 하나라도 0이면 0을 출력하고 OR 게이트는 둘 중 하나라도 1이면 1을 출력한다. 우리는 weight인 theta의 값을 적절히 정함으로써 이를 구현할 수 있다. 자세한 값은 위 그림을 보면 알 수 있다. 똑같이 x1, x2에 0, 1을 각각 대입한 경우가 나타난다. 하지만 theta값에 따라 h값이 달라지는 것을 확인할 수 있다. 우리는 이렇게 논리 게이트를 설계할 수 있다. 위 게이트를 여러개 엮어 우리는 XNOR 게이트라는 것을 구현할 것이다. 그 전에 NOR 게이트를 먼저 알아야한다. 여기서 N..

NN(neural network)의 모델은 위 그림과 같습니다. logistic regression과 마찬가지로 logistic function을 사용하고 feature인 input을 넣어주고 중간의 일련의 과정을 지나 output인 h를 출력한다. 이때 중간에 사용하는 함수를 sigmoid activation function, g(z)라고 부르고 theta를 weights라 부른다. 그리고 첫번째 feature을 x0를 bias unit이라하고 이 값은 1이기에 굳이 나타내지 않기도 합니다. 중간 과정을 자세히 들여다보면 뇌의 뉴런이 서로서로에게 영향을 주듯 보이며 각 노드의 무리를 layer라고 합니다. layer가 나뉘어져 이전 layer가 그 다음 layer에게 영향을 주며 끝까지 이어갑니다. 여..

이전 강의까지는 linear regression과 logistic regression을 배웠습니다. 하지만 위와 같이 데이터가 분포하는 경우는 non-linear regression이 필요하게 됩니다. 이런 경우를 logistic regression을 이용해서 해결할 수도 있겠지만 위 그림에서 보이듯이 변수가 x1, x2밖에 없어도 x1x2, x1^2 이 생기는 등 단 2개의 변수만으로 수 없이 많은 feature이 생기는 것을 확인할 수 있습니다. 이렇게 되면 약 100개의 feature이 주어졌지만 연산으로 넘어가면 5000 feature 이상이 있는것처럼 보여집니다. 이 외에도 이전 강의에서 봤던 overfitting 문제도 있어 다른 모델이 필요합니다. 그 모델은 바로 neural network ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 전형적인 dp문제이다. dp[i]는 i번째 포도주에 도달했을때 가장 많이 마신 양이다. 그렇다면 두 가지 방법으로 나뉠 수 있다. 첫번째로 i번째를 마셨을때이다. 이를 마셨다면 또 두가지로 나뉜다. 이전 포도주를 마셨냐 안 마셨냐이다. 마셨다면 3번 연속으로 못 마시기에 dp[i - 3]과 이전 포도주, 현재 포도주를 다 더해준다. 이전 포도주를 안 마셨다면 dp[i - 2]와 현재 포도주를 더해준..

이번 강의에서는 머신러닝 학습중 공통된 문제인 Overfitting과 그 해결책인 Regularization을 알아보도록 하겠습니다. 위 그림을 보면 왼쪽에서 오른쪽으로 갈수록 h함수가 더 복잡해지고 변수가 많아지는 것을 확인할 수 있습니다. 이는 feature의 개수에 따라 달라지고 그에 맞춰 parameter의 개수도 늘어납니다. 왼쪽 그래프는 변수가 너무 적어 h함수가 결과를 잘 예측하지 못하고 있음을 확인할 수 있습니다. 이를 Underfit, High biased 라고 합니다. 중간 그래프는 적당히 변수가 있어 h함수가 데이터를 적절히 예측하고 있어 성공적인 h함수라고 할 수 있습니다. 반면 오른쪽 그래프는 변수가 많아 훈련 데이터에만 너무 잘 맞고 그 외 구간에서는 우리의 직관과 맞지 않는, ..

이번 시간에는 Multiclass Classification에 대해 알아보겠습니다. 우린 전 수업에서 악성 종양인지 양성 종양인지 알아내는, class가 2개뿐인 Binary Classification에 대해 다루었습니다. 하지만 우리 일상생활에서 무언가를 정할 때 항목이 단 2개가 아닌 여러개인 경우가 많습니다. 예시로 이메일 분류를 일, 친구, 가족 항목으로 분류하거나 날씨를 맑음, 비, 눈 등으로 나누는 경우가 있겠습니다. 이런 경우 항목이 여러개 만들고 이를 분류할 필요가 있습니다. 그렇다면 라벨이 여러 개인 경우에는 h함수를 어떻게 정의할까요? 정답은 class 개수만큼 정의하는 것입니다. 그림 아래편에서 h함수를 보면 알 수 있듯이 h^(i) 함수는 x가 주어졌을때 y = i인 경우를 맞추는 ..

이번 시간에는 Logistic Regression의 Cost function을 알아보려고 합니다. Linear Regression와 똑같이 J 함수를 정의하고 h함수를 새로 대입하면 간단하게 해결될 것 같지만 그렇게 하면 문제가 생깁니다. 바로 J함수가 왼쪽 그래프처럼 Non-convex function으로 그려지게 되는데 이렇게 되면 local-optima가 많이 생겨 global-optima에 도달하지 못해 비교적 정확한 예측이 불가능하다는 문제가 생깁니다. 그렇기에 우리는 새로운 Cost function을 정의해야만 합니다. 새로 정의한 J함수입니다. J함수가 이전과는 다른 모습이 눈에 띕니다. 바로 y의 값에 따라 함수를 2개로 나눈 것인데 이렇게 함으로써 방금 언급한 문제점을 해결할 수 있고 더..