피너클의 it공부방

18185번: 라면 사기 (Small)https://www.acmicpc.net/problem/18185 그리드 문제다. 참 싫다. 라면 한개를 사면 3원, 2개를 사면 5원, 3개를 사면 7원이다. 이걸 다르게 생각하면라면 한개를 사면 3원그 다음에 라면을 사면 2원그 다음에 또 라면을 사면 2원 이렇게 생각하자. int n;long long arr[10001];long long one = 0, two = 0;long long ans = 0;사용할 변수들이다.n이랑 arr은 입력이고 ans는 정답이다.one은 앞에서 한개를 사면 추가된다.two는 앞에서 한개를 사고 또 한개를 사면 추가된다.즉 one -> two로 넘어가는 것이다. cin >> n; for (int i = 0; i > arr[i];입력..

17071번: 숨바꼭질 5https://www.acmicpc.net/problem/17071bfs를 이용했다. int n, k;queue> q;int visited[500001][2];사용할 변수들이다.visited는 해당 위치에 언제 도착했는지이다.visited[50][0] = 50이면 좌표 50에 시간 50만에 도착했다는 뜻이다.visited[50][1] = 29이면 좌표 50에 시간 29만에 도착했다는 뜻이다.0에는 해당 좌표에 도착한 짝수 시간이 들어가고1에는 해당 좌표에 도착한 홀수 시간이 들어간다. cin >> n >> k; for (int i = 0; i 값들을 입력받고 visited를 -1로 초기화한다.그 후 visited[n]을 초기화한다. 이때 당연히 0만 초기화해준다. 0초에 도착했으..

13544번: 수열과 쿼리 3https://www.acmicpc.net/problem/13544 세그먼트 트리는 참 변형된게 많다.여기서는 머지소트트리를 이용한다. 위에가 세그먼트 트리고 아래가 머지 소트 트리다.가장 큰 차이점은 숫자를 정렬한다는 것이다.세그먼트 트리는 그 자리 그대로 사용하지만 머지 소트 트리는 숫자를 정렬한다. merge sort와 동일하게 생각하면 된다. int n, m;int arr[100001];vector segtree[4 * 100001];사용할 변수들이다.segtree에는 당연히 범위 안의 숫자들이 정렬된 상태로 들어갈 것이다.void init(int node, int start, int end, int left, int right) { if (end 초기화 함수다. if..

11376번: 열혈강호 2https://www.acmicpc.net/problem/11376 이분매칭 문제다.이분 매칭이 무엇인지는 다른 곳에서 보고오길 바란다. 이 문제에서 헷갈리는것은 한 사람이 2개의 일을 할 수 있다는 것이다.bool dfs(int person) { if (visited[person]) return false; visited[person] = true; for (int i = 0; i 내가 사용한 이분 매칭 알고리즘이다. person이 들어오면 person이 할수있는 일들을 확인하며 job (할수있는일)에 매칭된 사람이 없거나 match[job] (job에 매칭된 사람) 이 다른 일을 할 수 있으면 true를 반환한다. 결국 dfs는 일에 사람이 매칭되면 true를 반환한다. ..

3006번: 터보소트https://www.acmicpc.net/problem/3006 세그먼트 트리를 이용해서 풀었다. 75 4 3 7 1 2 6위와 같이 주어졌다고 하자 정렬하는 순서는 1, 7, 2, 6, 3, 5, 4 이다.여기서 알수있는것은 3을 정렬하기 전에 1과 2는 무조건 정렬이 되어있다는 것이다.또 5를 정렬하기 전에는 7, 6은 무조건 정렬이 되어 있다. 이걸 더 발전시켜보자71 5 4 3 2 6 7위에서 1과 7을 정렬한 형태이다. 1과 7은 맨 끝놈들이니 간단하게 생각하면 된다.이제 2를 옮긴다고 생각해보자 2를 옮기기 전에 1은 무조건 앞에 있는 상태이다. 2 9 8 7 6 5 4 3 1 위와 같은 상황이었다면 1이 앞으로 이동하고 나면 2의 자리가 뒤로 밀리게 될 것이다.1 2 9..

11266번: 단절점https://www.acmicpc.net/problem/11266 단절점을 어떻게 구해야할까위에서 단절점은 어디어디일까. 이제와서 보니 2가 두갠데 하나는 3이다.위의 3개이다. 그럼 저것들은 왜 단절점일까?1을 제거하면 위처럼 그래프들이 처음 상태에서 떨어지게된다. connected component가 늘어나는 것이다.6과 7도 마찮가지로 제거하면 CC가 늘어난다. 그럼 이제제거하면 CC가 늘어나는 정점을 어떻게 구해야할까 1에서 dfs를 시작해서 6으로 향했다고 해보자6의 자식들은 6을 제거했을때 6보다 위에있는 정점으로 연결되지 않는다. 그렇기 때문에 6을 단절점이다. 그럼 4로 가보자4보다 아래있는 5는 4보다 위에있는 1로 향할수가 있다. 그러니 4는 단절점이 아니다. 그럼..

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 반환하고 ..