본문 바로가기

알고리즘49

Codeforces Round #683 (Div. 2, by Meet IT) AB import sys input = sys.stdin.readline for _ in range(int(input())): n = int(input()) print(n) for i in range(n): print(i+1, end=" ") print() A - Add Candies 한 바구니를 선택한다는 조건을 무시하면, 사탕을 n번 넣었을 때 모든 바구니에 똑같이 (n * (n+1))/2 개의 사탕을 넣게 된다. 이때 각 바구니에 들어있는 사탕 수는 처음과 같이 등차 +1의 관계를 가진다. 따라서 1번 바구니부터 1, 2, 3... 순서로 빼주면 모든 바구니가 같은 수의 사탕을 가지게 된다. 결론은 1번부터 n번까지 순서대로 한 번 씩 선택하면 된다. #include using namespace std;.. 2020. 11. 16.
ICPC Seoul Regional 2020 예선 참여 E F I K 총 네 문제를 풀었다. 4 솔브의 벽이 이런 건가 싶으면서도 다음번엔 더 잘할 수 있을 거란 확신이 들기도 했다. I번 Project Teams SCPC에서 분명 같은 문제가 나왔던 것 같다. 그대로 풀어서 빠른 정답을 받을 수 있었다. E번 Cycle Game, F번 Escaping 팀원이 둘 다 쉬운 문제라면서 순식간에 풀어버렸다. 나중에 들으니 E는 유니온 파인드 기본 문제이고, F는 예상대로 직선으로 이동하는 게 항상 최선이므로 그에 대한 처리만 해 주면 풀리는 문제였다. 그렇게 쉽지만은 않은 것 같은데 실수 없이 풀었다는 점이 정말 대단했다. K번 Road Reconstruction L번을 고민하던 중, 옆에서 "그냥 PQ에 가중치 박고 bfs 하면 되는 문제니까 구현해"라고 해서.. 2020. 10. 11.
2020 IGRUS Newbie Programming Contest 참여 from sys import stdin input = stdin.readline n, m = map(int, input().split()) if m == 1 or m == 2: print("NEWBIE!") elif m=0: print(len(m)-2) else: print(32) B 새로운 언어 CC 19945번: 새로운 언어 CC C언어는 int형 변수를 32개의 bit를 이용하여 2의 보수 방식을 따라서 이진수의 형태로 저장한다. 즉, 정수 10은 0000 0000 0000 0000 0000 0000 0000 1010으로 저장된다. 하지만 세상을 뒤흔들 새로운 언어 CC� www.acmicpc.net from sys import stdin input = stdin.readline N = int(in.. 2020. 9. 27.
Suffix Array와 LCP Array #include using namespace std; typedef long long ll; typedef pair pii; vector suffixArray, LCPArray; void getLCP(vector& sa, vector& lcpa, string& s) { int i, j, k, l = 0, m = 26, sLen = s.length(); sa.resize(sLen, 0); lcpa.resize(sLen, 0); // cnt: radix cnt | x: rank vector cnt(max(sLen, m), 0), x(sLen, 0), y(sLen, 0); for (i = 0; i < sLen; ++i) cnt[x[i] = s[i] - 'a']++; for (i = 0; i < m; ++i) .. 2020. 9. 23.
Topological Sort #include using namespace std; const int MAX = 10000 + 1; vector adj[MAX]; queue Q; int N, res; int indegree[MAX], cost[MAX], result[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 1; i > cost[i]; int K; cin >> K; for (int k = 1; k > p; adj[p].push_back(i); } if (indegree[i] == 0) { Q.push(i); result[i] = cost[i]; res = max(res, result[i]); } } for (int.. 2020. 9. 16.
유니온 파인드 연속된 구간 [p : q] 을 merge 하는 경우, 단순하게 p, p+1, ..., q 를 순서대로 merge 하면 정보의 낭비가 크다. merge(p ... q) 를 위에서 언급한 작업이라고 하자. 단순히 merge(p ... q)를 하는 경우 - 3, 4에서 불필요한 작업을 반복해서 하게 된다. 정보의 낭비를 줄여보자. 방향을 뒤집어 오른쪽을 root로 하여 merge 한다. 이제 구간 [3 : 6] 을 merge 해보자. 구현은 다음과 같이 하였다. while (search(p) != search(q)) { int next = search(p) + 1; merge(q, p); p = next; } p는 3을 가리키고, q는 6을 가리키고 있다. 첫 루프에서, 다음 그림과 같이 merge(q, p).. 2020. 9. 11.

티스토리툴바