TIL💡(277)
-
[중급 알고리즘] Brute Force 확장3
💚 2234 성곽 💥 여기서 쟁점은 하나의 벽을 제거해서 얻을 수 있는 가장 넓은 방의 크기를 구하는 일이다. 하나의 벽을 제거할 때는 최대 두 개의 방을 합할 수 있으므로 인접한 방의 크기 합의 최대를 구하면 된다. 따라서 방별로 인접성을 파악한 후 이미 구한 방의 크기를 활용하면 되지 않을까? 🎶 딩동댕동~ 앞서 푼 16932 모양만들기 문제와 유사하게 풀면 된다. 이를 위해 각 방의 정보와 해당 위치의 방 정보를 저장하는 작업이 필요하다. #include #include using namespace std; int n, m; // 성곽 int a[50][50]; // [i,j]의 방번호 int d[50][50]; // 방 i의 크기 int room[50 * 50]; // 문제에서 안내된 1,2,4,..
2022.06.19 -
AI RUSH 2022 참가 🏃♀️
작년에 참가했던 친구의 추천으로 지원해본 AI RUSH.. AI 기초 지식이 워낙 부족한 탓에 서류부터 될까 걱정했는데, 서류가 통과되고 코테까지 보고 나니 일사천리로 결과가 나왔다. 오늘 갑자기 코딩테스트 합격했으니 최종 참가자라는 통보를 받았다. 기쁘긴 하지만 되고나니 큰일이다라는 생각이 든다. 더욱이 다음주부터 시작하는 일이 많아서 시간이 많이 빠듯할 것 같다는 우려도 있다..ㅠㅡㅠ 아무래도 알고리즘 공부 시간을 약간 줄이고, 기초 AI 공부를 더해야겠다. 부족하지만 최선을 다해서 대회에 임할 생각이다.
2022.06.18 -
[중급 알고리즘] Brute Froce 확장 2
💚 16956 늑대와 양 최소의 울타리를 구하는 것이 아니므로 사실 BFS를 쓸 필요가 없다. 양과 늑대가 붙어있는 경우를 확인하고, 없으면 모든 빈칸에 울타리를 설치하면 절대로 늑대가 양에게 갈 수 없다. 💚5014 스타트링크 처음에 이 문제를 보았을 때는 그냥 BFS 식으로 탐색하는 것이 아니라 건방지게 단순 연산으로 풀 수 있을 것 같았다. 예를 들어 a, b를 각각 위, 아래로 이동가능한 거리라고 가정하자. 2라는 거리를 이동해야할 때, 위로는 2층씩, 아래에는 3층씩 이동가능하다면 $2a + 3b = 2$라는 이차방정식이 세워진다. 여기서 단순히 $a, b$를 구하는 것이 아니라 양의 정수를 구해야하므로 BFS 식으로 탐색을 해야하는 것이 맞았다. 시간복잡도는 최악의 경우 모든 층을 방문하는 것..
2022.06.18 -
[Codeforces] 1694B. Paranoid String
이 문제는 greedy하게 풀면 모든 조합을 만들 필요가 없다고 한다..나는 모든 조합을 다 시도해봤더니 시간 초과가 발생한다. We want to show that a binary string T of length $m$ is paranoid if and only if $m = 1$ or($m > 1$ and $S[m] \neq S[m - 1]$) 🌱 In the case of $S[m - 1] = S[m]$ 우리는 마지막 두 char를 지울 수 없다. 왜냐하면 동일한 char라서 남아있기 때문이다. 따라서 S는 paranoid가 아니다. 🌱 In the case of $S[m - 1] \neq S[m]$ 만약 $m = 2$이라면, 우리는 하나의 연산만으로 우리의 목표에 도달할 수 있다. 그렇지 않은 ..
2022.06.17 -
[Codeforces] 1694A. Creep
나는 이거 그나마 패턴 만들어서 꾸역꾸역 string을 만들었는데, 이보다 더 간단한 패턴이 있다고 한다. Define the minimum possible creepiness of the string as ans. We want to show that ans is equal to $max(1, |a - b|)$. 최소한의 creepiness를 가지는 ans라는 string을 정의해보자. 우리는 ans가 $max(1, |a - b|)$와 동일하다는 것을 보여주어야 한다. $S[1..1]$의 creepiness는 1과 동일하고, $S[1..n]$는 $|a - b|$와 동일하다. 따라서 $max(1, |a - b|) t; while(t--) { int a, b; cin >> a >> b; for(int i ..
2022.06.17 -
5장. 오차역전파법(Backpropagation)
앞 장에서 신경망의 가중치 매개변수의 기울기(정확히는 가중치 매개변수에 대한 손실 함수의 기울기)는 수치 미분을 사용해 구했다. 수치 미분은 단순하고 구현하기도 쉽지만 계산 시간이 오래 걸린다는 게 단점이다. 오차역전파법은 가중치 매개변수의 기울기를 효율적으로 계산하도록 한다. 순전파(forward propagation): 계산을 왼쪽에서 오른쪽으로 진행 역전파(backward propagation): 계산을 오른쪽에서 왼쪽으로 진행 역전파를 통해 미분값을 전달할 수 있고, 각 변수의 미분을 효율적으로 구할 수 있다. 연쇄 법칙(Chain Rule)💡 1학년 미적분학I 시간에 가장 열심히 공부했던 체인룰... 역전파의 계산 절차는 신호 $E$에 노드의 국소적 미분($\frac{\partial y}{\pa..
2022.06.16