Miscellaneous

https://codeforces.com/contest/1992 Dashboard - Codeforces Round 957 (Div. 3) - Codeforces codeforces.com 2024.07.21콘테스트를 친건 7월 11일이었는데... 요즘 이것저것 한다고 미뤘다가 열흘만에 드디어 포스팅.. 방학 동안에 학교에 알고리즘 동아리 사람들 몇명이랑 코포 스터디하면서 코포 연습중인데확실히 혼자 하는 것보다 아는 사람이랑 날짜 정해놓고 문제 얘기하면서 공부하는게 도움이 꽤 되는 것 같다.요즘 스터디하면서 딥2도 종종 하고있는데.. 2솔도 간당간당한 수준이라.. 퍼포 떨어질까봐 버츄얼로만 돌리는 중.. 각설하고, 이번 Div.3에선 간만에 5솔을 했고, 드디어 민트를 달성했다!  A. Only Plus..

https://www.acmicpc.net/problem/1736  알고리즘 동아리 시간에 고민하다가 결국 못풀었던 문제.처음 고민할땐 DP로 풀릴거같아서 어떻게든 점화식을 세워 보려고 했었는데.. 잘 안되더라;그리고 점화식 고민하면서 DP인것도 의심이 들었던게, 시간제한이 2초나 되고, N,M이 최대 100밖에 안돼서.. 확신이 안섰다..(조금 직접적인) 힌트를 들어도 이해가 안됐다가, 다행히 다음날에 번뜩 아이디어가 떠올라서 풀었더니 AC !  일단, 로봇의 움직임은 문제에서 나왔다시피 아래쪽 또는 오른쪽 둘 중 하나이다.최소의 로봇을 사용하므로, 하나의 로봇이 최대한 많은 쓰레기를 치워야 한다. 따라서 모든 쓰레기를 치우기 위해선, 어떤 로봇은 가장 위, 가장 왼쪽에 위치한 쓰레기에 도달해야하고, ..

MST는 Minimum Spanning Tree로 그래프의 모든 정점을 연결하고(연결성분의 수가 1개이고), 간선의 개수가 정점 수 - 1개인 트리를 말한다.MBST는 Minimum Battleneck Spanning Tree로, 트리를 이루는 간선의 최대 가중치가 최소가 되도록하는 스패닝트리를 말한다. 이번학기 자료구조 강의 내용에,"MST는 MBST인가?"라는 내용에 대해서 교수님께서 설명을 해주셨는데,, 되게 짧게 설명을 해주셔서,,, 조금 보충하고자 이것저것 찾아봤는데, 한국어로 된 좋은 글이 없었어 이해하는 데에 애를 먹었다..미래의 누군가가 나와 같은 고민을 하고있다면.. 이 글을 통해 해소할 수 있으면 좋겠다. 그래서 MST는 MBST일까?어떤 그래프 G의 mst를 T, T의 bottlene..

https://codeforces.com/contest/1986 Dashboard - Codeforces Round 954 (Div. 3) - Codeforces codeforces.comhttps://codeforces.com/blog/entry/130762 Codeforces Round 954 (Div. 3) Editorial - Codeforces codeforces.com 2024.06.24종강하고 첫 코포! 코드포스가 라운드가 자주 열려서 좋긴 한데..시간대가 너무 새벽이라 학교와 병행하기가 조금 어려워서 못하고 엣코더만 했었다.사실 런타임때 안하고 버츄얼로 돌릴 수도 있었던건데... 머릿속으로만 해야지~해야지~ 하다가 결국 종강하는 동안 한번도 안해버린... 시작하기 전에 오랜만에 코포를 돌리..

https://www.acmicpc.net/problem/1135    일단, 가장 처음 떠올린 풀이는 "자식노드 중에서 자식이 가장 많은 노드를 먼저 선택하면 되는거 아닌가?" 라고 생각했다. 따라서 임의의 노드에 대해서, 그 노드를 루트로하는 트리의 노드 수를 탑다운 방식으로 찾아내고, 적절히 정렬해서 풀면 될 것이라고 생각했다. 이때 제출한 코드는 아래와 같다.#includeusing namespace std;#define X first #define Y second#define rep(i,x,y) for(ll i=x;i pii;typedef pair pll;int dx[] = {0,0,1,-1};int dy[] = {1,-1,0,0};/*------------------------------*/v..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 www.acmicpc.net그리디 도장깨기 중 찾은 문제. 전구의 수는 최대 100'000개. 나올 수 있는 모든 경우의 수는 2^100'000..당연히 무지성 브루트포스로는 안풀리는 문제이다.  일단 비슷한 문제를 종만북에서 봤던 것 같다.흐릿하지만 그 기억을 잘 떠올려서 문제를 접근하면.. 문제를 푸는 데 가장 중요한건 스위치를 누르는 순서는 상관없다는 점.1번을 누르고 2번을 누르든, 2번을 누르고 1번을 누르든 전구의 상태는 달라지지 않는다. 따라서 앞에서부터 차례대로 스위치를 누른다고 했..

https://www.acmicpc.net/problem/1515 1515번: 수 이어 쓰기세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준www.acmicpc.net그리디 공부하다가 찾은 괜찮은 문제 되게 복잡하게 생각했었다가... 결국 못풀고 다른 사람 풀이를 찾아봤다. 우선 뭔가 규칙이 있을 것이라고 생각했다.8개의 예제들을 보면 입력의 맨 오른쪽 자리와 출력의 맨 오른쪽 자리가 같았다. (예제2번 제외)뭔가 숫자의 오름차순?과 관련이 있을것 같아서.. 규칙을 어떻게든 찾아보면 되겠구나..했는데아무리 고민해도 안나오길래 결국.. 포기했다.. 그냥 단순하게 모..

https://atcoder.jp/contests/abc344/tasks Tasks - Toyota Programming Contest 2024#3（AtCoder Beginner Contest 344） AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2024.03.09 개강하니까 되게 뭐가 바쁘다.. 오전 수업 때문에 잠을 일찍 자다보니 코포도 거의 못하고... 버츄얼이라도 돌릴까 해봤는데.. 뭐가 할게 많다 허허.. 그래도 ABC는 매주 토요일 밤이다 보니까 주말 약속만 없으면 웬만하면 할 수 있을 듯 하다. 더군다나 ..