본문 바로가기

분류 전체보기

문제 풀이/Codeforces 2020. 6. 24. Codeforces Round #652 (Div. 2) A - FashionabLee Problem - A - Codeforces codeforces.com 어떤 정다각형을 좌표평면 위에 놓았을 때, 이 정다각형을 회전시켜서 X축과 평행한 변과 Y축과 평행한 변이 동시에 있을 수 있다면 이 정다각형을 아름답다고 하자. \(n\)이 주어지면, 정 \(n\)각형이 아름다운지 여부를 알아내야 한다. \(n\)이 4로 나눠 떨어지면 이 정다각형은 아름답다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ll b) { for (; b;..
알고리즘/그래프 2020. 6. 22. Biconnected Component Biconnected Component (BCC)는 무방향 그래프에서, 다음 조건을 만족하는 정점의 부분집합을 말합니다. 1. 부분집합에서 어떤 정점 하나를 삭제하더라도, 남은 정점들은 서로 연결되어 있다. 2. 이 부분집합에 다른 정점들을 추가하더라도 1을 만족하지 않는다. (1번을 만족하는 최대 크기의 집합이다) 따라서 다음과 같은 무방향 그래프는, 다음과 같이 5개의 BCC로 분리됩니다. 그래프를 이와같이 BCC로 분리하여 하나의 BCC를 하나의 정점으로 대체하면 그래프를 트리로 나타낼 수 있게 됩니다. 일반적인 그래프를 트리로 바꾸고 나면 트리에만 사용할 수 있는 다양한 알고리즘을 사용할 수 있게 됩니다. SCC를 먼저 보신분들은 알겠지만, SCC와 개념이나 코드가 거의 동일합니다. SCC의 무방..
문제 풀이/Codeforces 2020. 6. 21. Codeforces Round #651 (Div. 2) A - Maximum GCD Problem - A - Codeforces codeforces.com 정수 \(n\)이 주어진다. \(1\)이상 \(n\)이하인 서로 다른 정수 2개를 골랐을 때, \(\gcd (a,b)\)의 최대값을 구해야 한다. 당연하지만, \(\gcd (\lfloor \frac n2 \rfloor, \lfloor \frac n2 \rfloor \times 2) = \lfloor \frac n2 \rfloor\)가 답이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(..
문제 풀이/Codeforces 2020. 6. 19. Codeforces Global Round 8 A - C+= Problem - A - Codeforces codeforces.com 정수 \(a, b\)가 주어진다. 이 정수들에 다음의 두 가지 연산을 할 수 있다. 1. \(a\) += \(b\) 2. \(b\) += \(a\) 이 때, \(a\)나 \(b\)가 \(n\)보다 크도록 만들기 위한 연산 횟수의 최소값을 구해야 한다. 관찰로 더 작은 수의 크기를 늘리는게 무조건 이득이라는 사실을 알 수 있다. 그러면 전체적인 수의 크기가 지수함수의 형태로 증가하므로, 단순 시뮬레이션으로도 충분히 시간안에 돌아가게 된다. 실제로 최악인 \(a=b=1, n=10^9\)를 넣어도 43번의 연산안에 완료됨으로 확인할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1..
알고리즘/그래프 2020. 6. 18. Strongly Connected Component Strongly Connected Component (SCC)는 방향 그래프에서, 다음 조건을 만족하는 정점의 부분집합을 말합니다. 1. 부분집합에서 어떻게 두 정점 \(u,v\)를 선택하더라도 \(u\)에서 \(v\)로 가는 경로가 존재한다. 2. 부분집합에 속한 정점 \(u\)와 그렇지 않은 정점 \(v\)에 대해서, \(u\)에서 \(v\)로 가는 경로와 \(v\)에서 \(u\)로 가는 경로가 동시에 존재하지 않는다. 따라서 다음과 같은 방향 그래프는, 다음과 같이 4개의 SCC로 분할됩니다. 그래프를 이와같이 SCC로 분할하여 하나의 SCC를 하나의 정점으로 대체하면 그래프를 DAG로 나타낼 수 있게 됩니다. 일반적인 그래프를 DAG로 바꾸고 나면 위상정렬이나 DP등 다양한 작업을 할 수 있게 됩..
문제 풀이/Codeforces 2020. 6. 17. Codeforces Round #650 (Div. 3) A - Short Substrings Problem - A - Codeforces codeforces.com 문자열 \(a\)가 있다. \(b\)는 \(a\)의 연속된 길이 2의 부분문자열을 모두 이어 붙여서 만들어지는데, 주어지는 \(b\)를 이용해 \(a\)를 알아내야 한다. \(b\)의 짝수번째 인덱스에 있는 문자들을 모두 출력한 다음, 맨 마지막 글자를 출력하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ll b) { for (; b; a %= b, sw..
알고리즘/그래프 2020. 6. 15. Euler tour technique 트리를 펴서 배열에 저장해봅시다. 다음과 같은 트리가 있다고 가정해봅시다. 1번 정점이 루트입니다. 이 트리에서 루트인 1번 정점부터 시작해 DFS를 돌립니다. 그리고 각 정점이 방문되는 순서대로 번호를 다시 붙여줍시다. 그리고 새로 붙인 번호를 인덱스로 하는 배열에 각 정점을 저장합시다. 그러면 트리를 배열에 저장할 수 있게 됩니다. 방법은 매우 간단한데, 굳이 이런식으로 저장을 하는 이유가 뭘까요? 이런 식으로 트리를 저장하면, 각 정점을 루트로 하는 서브트리가 모두 하나의 구간으로 나타나게 됩니다. 1번 정점의 서브트리는 구간 \([1,7]\), 2번 정점의 서브트리는 구간 \([2,5]\), 3번 정점의 서브트리는 구간 \([6,6]\)... 이와 같이 각 서브트리를 하나의 구간으로 바꿔 생각할 ..
문제 풀이/Codeforces 2020. 6. 8. Codeforces Round #648 (Div. 2) A - Matrix Game Problem - A - Codeforces codeforces.com \(n \times m\) 크기의 격자가 있다. 두 사람이 이 격자에 번갈아가며 말을 놓으려고 하는데, 말을 놓을 때는 같은 행이나 열에 말이 없어야 한다. 말을 더이상 놓지 못하는 사람이 진다. 초기 격자의 상태가 주어졌을 때, 누가 이기는지 알아내야 한다. 현재 말이 놓여있지 않은 행의 개수를 \(r\), 열의 개수를 \(c\)라고 하자. 그러면 말을 \(min(r,c)\)번 놓을 수 있으므로, 이 값이 홀수면 전자가, 짝수면 후자가 승리한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33..

티스토리툴바