Python
가우스 함수를 이용한 선형회귀 모델 직접구현
가우스 함수를 이용한 선형회귀 모델 직접구현을 해보자. 전글,전전글에서 소개했던 방법외에 가우스 함수를 사용해서도 모델을 구현할 수 있는데, 이는 직선이 아닌 곡선을 구현하는 경우에 사용된다. 즉, 위와같은 가우스 함수의 합으로 예측 모델을 구할 수 있는 것이다. 즉 위와같은 꼬불꼬불한 예측 모델을 만들 수 있게 된다. 몇개의 가우스 함수를 더해서 모델을 만들건지를 K라고 생각하고 이는 우리가 정한다고 생각해보자. 수식적으로 보면 K개의 가우스 함수는 위처럼 식을 세울 수 있다. 이때 Uk와 시그마값은 위와 같이 설정해 둘 수 있다. 결국 말은 어렵지만 전글,전전글에서 했던것과 똑같이 예측모델을 만드는데 이를 가우스함수로 만들 뿐이다. 그리고 우리는 가우스 함수를 어떻게 만들어야 할지도 알고있다. 또한 ..
다중차원 선형모델 직접 구현
저번 글에서 간단한 선형 예측 모델을 직접 구현해 봤는데, 이번에는 다중차원일 경우에 어떻게 모델을 구현할지 알아보겠다. 해석해를 통한 방법과 경사하강법을 통한경우를 둘다 직접구현해 보았다. 수식적인 공식을 보고 직접 코드를 구현해 봐서 좋은코드는 아닐지 몰라도 원리는 들어가 있을꺼라 생각한다. 이전에 1차원인 경우에는 예측모델이 ax + b라는 말을 한적이 있는데, 그렇다면 2차원인 경우에는 어떨까 ax^2 + bx + c 일까? 그렇지는 않다. 우선 2차원이라는 표현도 맞긴 하지만 입력이 2개 이상으로 오는 경우라고 생각하면 좋을 것이다. 조금 쉽게 생각하여 키와 몸무게를 가지고 나이를 맞추는 모델을 구현해본다고 생각해보자. 키,몸무게 2개의 다른 요소가 입력으로 주어지고 이를 통해 나이를 맞추기 때..
1806_부분합
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 이역시 투포인터로 풀 수 있었다! 단 이전까지는 start포이터와 end 포인터가 끝에서 시작했는데 이번에는 둘다 시작점에서 출발하게 하는것이 달랐다. 10 15 5 1 3 5 10 7 4 9 2 8 먼저 start포인터와 end 포인터를 둘다 0이라 생각하고 시작한다. 그리고 두 포인터 가 지칭하는 사이의 값들을 더한게 S보다 작다면 end 포인터를 증가시키고, 그렇지 않다면 st..
3273_두수의 합
https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 처음 문제를 보면 for문을 두번 돌려서 문제를 풀었을 것 같다. 하지만 문제에서도 나와있듯이 투 포인터 알고리즘을 사용해서 풀라고 한다! 투 포인터 알고리즘이란 1차원 배열에서 공간을 가리키는 두개의 포인터를 지니는 방식으로 특정값을 추출해내는 알고리즘이다. 인터넷을 좀 뒤져서 공부를 해보니 투 포인터에는 몇가지 방법이 있다. 크게 두가지가..
1956_운동
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 이제 그래프를 활용해서 최단거리를 구하는 것은 익숙해졌다! 사이클을 구하기 위해서 어떻게 해야할까 고민하다가 결국 사이클이란 것은 본인에서 시작해서 본인으로 돌아오는 최단거리라고 생각했다. 지금까지 코드를 구현할때는 1번에서 1번으로 가는것은 0으로 두었었는데, 이를 그냥 설정하지 않고 코드를 진행시키고, INF가 아닌 최솟값을 찾는 코드를 구현하면 될것같아서 해..
10217_KCM Travel
https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 되게 어려운 문제였다.. 처음에는 시간을 최소로 하는 알고리즘을 찾으며 비용의 제약을 두는방식으로 하면 될것 같았으나, 생각을 해보니 당장은 시간도 비용도 손해같지만 결국 초반에 돌아가야하는 경우가 생겼다. 1 6 149 8 1 2 60 20 2 3 30 70 1 3 100 80 1 3 20 180 3 4 20 100 3 5 150 20 5 6 50 40 4 ..