pseong

Problem - E - Codeforces codeforces.com 보자마자 트리디피 인 것은 알았지만 한 가지 착각한 것 때문에 시간이 너무 오래 걸렸다. dp[i] : i를 루트로 하는 서브트리 내에서 정답 이라고 했을 때 dp[i] 는 max(모든 자식 dp[j] 를 더한 값, max(dp[j]) + 1)이라고 생각했다. 여기서 간과한 사실은 이렇게 구현하면 max(dp[j]) + 1)에 포함된 노드들 중에 모든 자식 dp[k]를 더한 값이 존재할 수 있다는 것이다. max(dp[j]) + 1로 구한 값은 항상 그 자식들도 max(dp[k]) + 1로 구해져야 한다. 생각해 보면 max(dp[j]) + 1이라는 값은 트리의 깊이이다. 따라서 트리의 깊이와 모든 자식 dp[j] 를 더한 값은 분리..

Problem - F - Codeforces codeforces.com F번 치곤 쉽게 나와서 진짜 오랜만에 F번을 풀어봤다. 가장 안좋은 방법은 k개를 선택하고 k개를 차례대로 순회하면서 답을 구하는 방법이다. 이 방법은 O(nCk * k) 시간 복잡도 이므로 말도 안되는 시간이 걸린다.( 대략 30만 팩토리얼 ) k개를 선택하는 방법은 괸장히 비효율적이므로 다른 방법을 생각해 내야 한다. 답은 문제의 정의를 다르게 하면 된다. 디스크립션에서 k개를 선택하고 분할해서 계산한다. 우리는 분할 먼저 하고 k개를 선택할 것이다. ( 생각해 보면 이 풀이가 떠올리기 어렵지 않은 이유가, 연산의 순서를 바꾸는 방법은 흔한 풀이 방법중에 하나이기 때문일 것이다. ) 분할 먼저 하고 왼쪽에서 d개, 오른쪽에서 k-..

Problem - D - Codeforces codeforces.com 세로 x 가로 y 인 사각형으로부터 잘려 나온 n개의 조각들이 있다고 가정하자. (1) n개의 조각들로 세로 x 가로 y 인 사각형을 만들 수 있는지 판단할 수 있다. (2) 첫 번째 조각은 세로가 x이거나 가로가 y인 사각형 이어야 한다. 세로가 x인 조각과 가로가 y인 조각은 동시에 존재할 수 없다. 세로가 x인 조각을 먼저 잘랐다고 가정하면 가로는 y보다 작아지므로 가로가 y인 조각을 영원히 사용할 수 없다. 가로가 y인 조각을 먼저 잘랐다고 가정하면 세로는 x보다 작아지므로 세로가 x인 조각을 영원히 사용할 수 없다. 따라서 동시에 존재할 수 없으므로 항상 다음에 사용할 조각의 가로 또는 세로의 길이는 유일하다. 만약 가로가 ..

먼저 Certificate Manager 과 Route53 에서 SSL 인증서를 받아야 한다. 받고 난 후 CloudFront 에서 어떻게 설정하는지에 대한 기록이다. 일단 Certificate Manager 에서 SSL 인증서를 받을 때 위치를 꼭 버지니아 북부로 하자. 먼저 api.example.com 주소를 API 서버 주소로 사용하고 싶다면 Route53 에서 다음과 같이 설정해 주어야 한다. a.example.com 을 API 서버 주소로 먼저 향하게 해야 한다. api.example.com 을 API 서버 주소로 향하게 한다면 안되니 주의하자. 그리고 CloudFront 에 들어가서 배포 생성을 누르고 원본 도메인을 적어야 하는데 이것은 Route53 에서 API 주소와 연결된 도메인을 적어줘..

결과는 2위를 했다. 목표는 10위안에 들어보자 였는데 생각보다 결과가 너무 잘 나와서 뿌듯하다. 작년에 인하대 IUPC에서 선발되어서 2023년 3월 11일에 열린 2022 shake! 대회에 참여했다. 올해는 온라인으로 시험을 봤는데 항상 알고리즘을 공부하던 환경에서 시험을 보니까 더 좋았다. 결론적으로 이번 대회에서 A B C D E F G, 7문제를 풀었다. 까먹기 전에 문제에 대한 후기를 작성하고 싶어서 시험 끝나고 5시간 정도의 휴식을 가진 뒤 작성하고 있다. A번 문제는 몇 번 이길 수 있는지 세는 거였고 자신보다 낮은 애들을 최대한 살리면서 진행하고 사라지면 반전 연산을 사용하는 게 답이었다. 그럭저럭 쉽게 풀었다. B번 문제는 1부터 k까지의 주어진 소수에 해당하는 인수의 개수를 구하는 ..

중국인의 나머지 정리가 무엇을 의미하는지는 나무위키에 잘 설명이 되어있다. 중국인의 나머지 정리 - 나무위키 (namu.wiki) 보통 중국인의 나머지 정리라 하면 모든 m이 서로소여야 한다. 하지만 서로소가 아닐때도 해를 구하고 싶을때가 있을 것이다. 이런 경우에는 두 개의 합동식을 하나로 합친다. 계속 이렇게 합쳐 주다가 마지막 한 개의 합동식만 남았을 때 답을 구해주면 해결된다. 따라서 두 개의 합동식을 합치는 방법만 알면 문제를 풀 수 있다. x ≡ a1 ( mod x1 ) x ≡ a2 ( mod x2 ) 먼저 이렇게 두 개의 합동식이 있다고 하자. g = gcd(x1, x2) 라고 하자. 아래 두 개의 식이 성립하므로 x ≡ a1 (mod g) x ≡ a2 (mod g) 다음 식이 성립한다고 할..

Problem - E - Codeforces codeforces.com Solution. 간선의 가중치가 k인 간선의 개수를 dp[k] 라 하자. 간선의 가중치는 연결된 두 노드의 최대 공약수 이므로 최대 공약수가 k가 되려면 두 수는 k의 배수가 되어야 한다. 따라서 k의 배수 중에서 2개를 선택하는 경우의 수 n/kC2를 구해주면 dp[k]의 초기값을 설정할 수 있다. 하지만 k의 배수 중에서 2k의 배수중에서 2개를 선택한 경우의 수는 최대공약수가 2k이므로 제외해 주어야 하고 마찬가지로 3k, 4k... 쭉 제외해 주어야 한다. 따라서 n부터 1까지 반대로 dp[i]를 채워 주면 답을 구할 수 있다. k를 선택했을 때 최대 공약수가 k + 1 인 추가할 수 있는 간선의 개수는 dp[k + 1] 이..

Problem - E - Codeforces codeforces.com 먼저 x가 y를 이긴다라는 것을 x에서 y로 가는 간선이 존재한다고 하자. 그리고 어떤 그래프에서 다른 모든 노드로 갈 수 있는 노드를 후보라고 하자. Lemma 1. 토너먼트의 승자는 최소 한 명은 존재한다. (후보는 무조건 한 명 존재한다.) Proof. 먼저 n이 1 또는 2일 때를 생각해 보자. 1 또는 2일 때는 무조건 어떤 한 노드는 다른 모든 노드를 방문할 수 있다. 여기서 노드를 하나씩 추가해 보자. 지문에 나온 대로 완전 그래프여야 하기 때문에 노드 하나를 추가할 때마다 기존에 있던 모든 노드와 연결되어야 한다. 여기서 기존에 있던 노드 중에서 모든 노드를 방문할 수 있는 노드를 x라 하자. 새로 추가하는 노드를 y라..