피너클의 it공부방

11280번: 2-SAT - 3https://www.acmicpc.net/problem/11280 SCC를 이용해서 풀었다. (P ∧ ¬Q) ¬P ∨ Q (A ∧ B) 이거는 A and B 이거다.(A ∨ B) 이거는 A or B 이거다.문제는 (A ∨ B) ∧ (A ∨ B) ∧ (A ∨ B) ∧ (A ∨ B) 이런 식으로 나온다.즉 (A ∨ B) 이게 무조건 True 여야한다. 이제 (A ∨ B) 이걸 (¬A → B) ∧ (¬B → A) 이렇게 바꿔야 한다.그러기 위해서는 먼저 A → B 이게 뭔지를 알아야 한다. A → B 이건 조건문이다. "A 이면 B이다" 이런식으로 가는 것이다.A가 "비가 온다" B가 "우산을 쓴다" 이렇게 가고A가 True고 B가 True면"비가온다" 그러니 "우산을 쓴다" ..

4008번: 특공대https://www.acmicpc.net/problem/4008 dp와 Convex Hull Trick 으로 풀었다. 먼저 dp 식을 만들었다.dp[i] = 0 ~ i까지 특공대를 조직했을때 최대 전투력대충 이정도로 생각해보자. dp[i]를 만들었다고 생각하고 dp[i + 1]로 넘어가자dp[i + 1]은 dp[i]에서 새로운 병사가 추가되어 x[i + 1]이 추가되어야 한다.dp[i + 1] = dp[i] + a * x[i + 1] ^ 2 + b * x[i + 1] + c 하지만 새로 추가될 병사인 x[i + 1]은 앞의 인원과 그룹이 될수도 있다.x[i + 1]과 x[i]이 하나의 특공대가 되게 하려면 dp[i]가 아닌 dp[i - 1]을 사용해야한다.dp[i + 1] = dp[i..

13263번: 나무 자르기Convex Hull Trick 으로 풀었다. 문제를 먼저 봐보자.만약 내가 5번 나무의 높이를 0으로 만들면 5번 보다 번호가 큰 나무를 자르기 전까지는전기톱을 충전할때 b[5]만큼의 비용이 든다. dp[i]는 i번째 나무를 높이가 1이 될때까지 자르는데 필요한 충전 비용의 최소값으로 정의할 것이다.만약에 전기톱을 충전하는 비용이 100이라고 하고 나무의 높이를 10이라고 해보자.우리는 나무를 자르고, 충전한다.높이 10 | 충전 비용 0높이 9 | 충전비용 100높이 8 | 충전비용 200높이 7 | 충전비용 300높이 6 | 충전비용 400높이 5 | 충전비용 500높이 4 | 충전비용 600높이 3 | 충전비용 700높이 2 | 충전비용 800..

신경망은 퍼셉트론을 다층으로 쌓고 활성화 함수를 개선한 것이다. 앞의 퍼셉트론을 수식으로 표현한다면 $y = h(b + w_{1}x_{1} + w_{2}x_{2})$$h(x) = \left\{\begin{matrix} 0\quad if\,x\leq 0 \\ 1\quad if\,x> 0 \end{matrix}\right.$위처럼 된다. 위에서 h(x) 함수같이 x를 출력신호로 변환하는 함수를 활성화 함수라 한다.여기서 x는 앞의 입력신호화 가중치, 편향의 계산 결과이다.그림으로 그리면 이런 형태이다. 하지만 활성화 함수에는 여러 종류가 있다. 시그모이드 함수S자 형태의 함수이다.def sigmoid(x): return 1 / (1 + np.exp(-x)) 계단함수계단함수는 0보다 크면 1 반환하고 ..

AND와 NADN, OR 모두 같은 구조로 만들수있다.안에있는 가중치와 편향만 다를 뿐이다. 가중치 : 입력 신호의 중요도편향 : 활성화 정도를 조정하는 매개변수 def AND(x1, x2): x = np.array([x1, x2]) w = np.array([0.5, 0.5]) b = -0.5 y = np.sum(w * x) + b if y > 0 : return 1 else : return 0AND는 위처럼 구현 가능하다.w는 가중치 값이다. 0.5와 0.5, 이 두값은 각각 x1, x2에 곱해진다.b는 편향이다. 입력신호에 가중치를 곱한 값에 더해줄것이다.입력값이 1과 1이라면 1 * 0.5 + 1 * 0.5 - 0.5 = 0.5가 될것이다.0.5는 0보다 크니 1을 반환하고 AND의 기능..

#include 으로 불러오고 삽입, 삭제, 탐색 모두 log(N) 삽입 방법은 크게 2개배열 처럼 넣거나 insert로 넣거나둘의 차이점은?1부터 100까지 m[10]에 배열 처럼 넣고 m[10]을 출력하면 당연히 100이 출력된다. 하지만 insert로 집어넣은 경우에는 맨 처음에 넣은 값인 1이 출력된다. insert의 경우 값이 있을 경우 그 값을 덮지 않는 것이다. 삭제 m.erase()를 통해 지울 수 있다. 없는 값을 지워도 딱히 에러는 안뜨는거같다. 탐색 탐색은 배열처럼 찾을수도 있고 find를 통해 찾을 수도 있다.find를 통해 찾은 경우에는 iterator로 반환되기 때문에 값을 출력하려면 -> 를 이용해야한다. 없는 값을 출력하면 위 처럼 나온다. map에는 순서가 없다. 들어간 순..