MG

앞서 설명했었던 Supervised Learning의 한 종류인 Classification을 다시 다룹니다. 우리가 지금까지 Linear Regression을 이용하여 예측을 했기에 이를 그대로 적용하면 될 것 같지만 문제가 생깁니다. 위 그림은 종양의 크기를 알았을 때 악성인지 양성인지 추측하는 문제입니다. 위와 같이 데이터가 모여있고 오른쪽에 위치한 데이터처럼 동떨어진 데이터가 생길 경우 당연히 우린 악성 종양이라고 판단하지만 Linear Regression은 저 데이터 하나 때문에 이 전의 데이터들의 판단을 수정하게 되어 정확도가 떨어진 함수가 됩니다. 이 이유는 오른쪽 데이터를 넣기 전까지는 함수가 합리적으로 예측했지만 오른쪽 데이터를 추가하는 순간 그래프가 오른쪽으로 더 기울어 져버리기 때문에 ..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 얼핏 보면 간단한 조합 구현 문제이지만 범위를 봐야합니다. 최대값인 100_C_50 는 long long int 의 범위를 거뜬히 넘어버려 계산식으로만 하면 틀립니다. 그렇기에 string으로 구현해 줍니다. 기본적으로 dp를 베이스로 nCm = n-1Cm-1 + n-1Cm 을 이용하여 재귀를 돌려줍니다. n = m or m = 0 일 때 1을 반환하고 이 전의 값이 있으면 그대로 반환해줍니다. 그리고 이 두 값을 더할 때 string의 첫째자리만 더해서 문자열로 추가하는 방식으로 정답을 string으로 반환합니..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 동전 k일때 동전의 최소 개수를 구하는 문제입니다. 저는 0원부터 k원까지 dp를 완성해서 푸는 방식으로 해결하였습니다. dp를 모두 INF로 초기화시키고 1원부터 k원까지 dp를 돌려줍니다. dp[i]를 초기화할때 동전 벡터를 전부 돌려가면서 dp[i]랑 dp[i - 동전] 을 비교해 더 작은 값을 저장합니다. 이때 i - 동전이 0 이상일때와 dp가 INF가 아닐..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 얼핏 보면 간단해 보이지만 a, b, c의 범위와 시간 제한 때문에 조금 고민이 필요한 문제입니다. 그냥 a^b 를 c로 나누게 되면 b번 반복이 있기 때문에 시간초과가 나게 됩니다. 그렇기에 분할 정복으로 O(b) 를 O(logb) 로 만들어 줍니다. 지수법칙을 적용해 보면 a^b = a^(b/2) * a^(b/2) 로 표현되기 때문에 이를 이용해 재귀를 돌려서 풀어줍니다. 그리고 계산을 하기 전에 a를 미리 c로 나눈값을 대입해 long long 범위 초과가..

이번 강의에선 theta값을 수학적으로 바로 찾는 방법인 Normal Equation에 대해 알아보겠습니다. 이 방법은 Gradient Descent와 다르게 계산식 한 번으로 적절한 theta값을 찾을 수 있습니다. 위 그림 아래쪽에 있는 식입니다. 이를 통해 반복이나 learning rate를 정할 필요도 없이 바로 theta를 구하게 됩니다. 강의에서는 이 식의 증명을 따로 하진 않았지만 궁금해서 제가 찾아보았습니다. 증명과정은 위 그림과 같고 결과만 알아도 되기에 참고만 하시면 좋을 것 같습니다. 참고한 사이트입니다. https://eli.thegreenplace.net/2014/derivation-of-the-normal-equation-for-linear-regression/ Derivatio..

이전 강의에서는 특징(변수)가 1개인 Univariate Regression 만 다루었습니다. 하지만 현실에선 2개, 3개 또는 거의 무한한 변수가 존재하게 됩니다. 이를 Multivariate Regression 이라고 합니다. m 개의 training sets 에서 각 set 당 n 개의 변수가 주어집니다. 여기서 x 는 변수이고 i번째 set 의 j번째 변수로 정의합니다. Multivariate Regression 에 Gradient Descent 를 적용시켜보면 위 그림과 같이 됩니다. 원래 사용했던대로 식을 사용하지만 이전과는 다르게 x가 n + 1 차원을 가지고 있기에 theta 도 마찬가지입니다. 그렇기에 이를 모두 계산해주는 것만 다릅니다. 오른쪽 아래 그림에서 미분도 똑같이 진행되는 모습..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 간단한 DP 문제입니다. 배열에 각 칸의 숫자를 입력받고 dp를 long long으로 선언해줍니다. 그리고 각 칸마다 오른쪽, 아래로 점프했을때 게임 판을 넘어가지 않는다면 그 칸의 dp 만큼 점프한 칸에 더해줍니다. 마지막 칸에 도착하면 루프를 탈출해주고 출력합니다. #include #define MAX 101 using namespace std; typedef long long ll..

https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 처음에 고민을 많이 하다 수학으로 풀었었습니다. 우체국의 위치를 x 로 잡고 각 마을과의 거리와 인구를 곱하면 여러 절댓값으로 이루어진 그래프가 그려지고 그 그래프의 극소점이 답이 되었습니다. 하지만 알고리즘 분류에 그리디가 있는 것을 보고 다른 풀이를 참고하다 더 간단한 방법이 있다는 것을 알게 되었습니다. 아래 ..