분류 전체보기
1450_냅색문제
https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net Meet in Middle알고리즘을 이용해보라고 힌트가 주어져 있는 문제이다. 위 문제같은 경우, 쉽게 생각하면 주어진 배열중에서 합이 c가 넘지않는 부분배열의 개수를 구하는 문제라고 생각해ㅗㄷ 좋을 것이다. 예를들어 [ 1, 2, ,3 , 4, 5,6 ] 해당 6개의 짐이 있다면 합이 10을 넘지않는 부분집합의 개수를 구하는 문제로 봐도 될 것이다. 이런 경우 모든 배열을 한번씩 탐색하면 굉장히..
1644_소수의 연속합
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 이전에 소수구하기 문제를 풀었던 경험이 있는데 소수를 구하는 리스트를 만든 후에, 저번문제에서 다뤘던 방식을 사용해서 문제를 풀면 된다. 두가지의 문제가 합쳐진 형태이다. n = int(input()) lst = [True] * (n+1) for i in range(2,int((n+1)**0.5)+1): if lst[i]: for j in range(i*2,n+1,i): lst[j] = False sosu = [0] for i in range(2,n+1): if lst[i]: sosu.append(i) start,e..
가우스 함수를 이용한 선형회귀 모델 직접구현
가우스 함수를 이용한 선형회귀 모델 직접구현을 해보자. 전글,전전글에서 소개했던 방법외에 가우스 함수를 사용해서도 모델을 구현할 수 있는데, 이는 직선이 아닌 곡선을 구현하는 경우에 사용된다. 즉, 위와같은 가우스 함수의 합으로 예측 모델을 구할 수 있는 것이다. 즉 위와같은 꼬불꼬불한 예측 모델을 만들 수 있게 된다. 몇개의 가우스 함수를 더해서 모델을 만들건지를 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차원 배열에서 공간을 가리키는 두개의 포인터를 지니는 방식으로 특정값을 추출해내는 알고리즘이다. 인터넷을 좀 뒤져서 공부를 해보니 투 포인터에는 몇가지 방법이 있다. 크게 두가지가..