본문 바로가기

전체 글80

Codeforces Round #688 (Div. 2) ABCD import sys input = sys.stdin.readline for TEST in range(int(input())): n, m = map(int, input().split()) r = [*map(int, input().split())] c = [*map(int, input().split())] s = set(x for x in r) res = 0 for i in c: if i in s: res += 1 print(res) A - Cancel the Trains 인접한 지점끼리 거리가 모두 같으므로 중복되는 값의 수가 답이다. import sys input = sys.stdin.readline for TEST in range(int(input())): n = int(input()) s = [*ma.. 2020. 12. 5.
Binary Search Tree 개요 노드에 키(또는 {키, 값} 쌍)를 저장하는 이진트리로, 다음 성질을 만족한다. 노드 v와 왼쪽 자식 u, 오른쪽 자식 w에 대해 key(u) ≤ key(v) ≤ key(w) 를 만족한다. 리프 노드는 아무것도 저장하지 않고, 트리를 중위 순회하면 키 오름차순으로 방문하게 된다. 탐색 키 k를 찾으려면, 루트 노드에서 출발해 k와 현재 노드의 키를 비교하며 탐색한다. k가 현재 노드의 키보다 작다면 왼쪽 노드로, 크다면 오른쪽 노드를 탐색한다. 리프 노드에 도달하면 키 k가 존재하지 않음을 의미한다. 삽입 먼저, 탐색과 같은 방법으로 키 k가 이미 존재하는지 판단한다. 리프 노드에 도달하면 해당 위치에 k를 삽입한다. 삭제 먼저 k에 대해 탐색하여 노드 v를 찼았다고 가정하자. v의 두 자식이 모두.. 2020. 12. 4.
Heap 개요 노드에 키를 저장하는 이진트리로, 다음 두 가지 성질을 만족한다. Heap order: 루트를 제외한 모든 노드 v에 대해 key(n) ≥ key( parent(n) ) Complete binary tree: 깊이 i [0 : h)에 노드 총 2i개. 특히 i = h-1에서 internal nodes are to the left of the external nodes 라고 하는데 잘 모르겠다. Last node 최대 깊이 h에서 가장 오른쪽에 있는 노드 트리의 높이 O(log n) 이다. 깊이 i [0 : h)에 2i개의 노드가 있고, h에 최소 한 개의 노드가 있다. 식으로 쓰면 n ≥ 1 + 2 + ... + 2h-1 + 1 = 2h 이다. 즉 n ≥ 2h 이다. 양변에 로그를 취하면 log n.. 2020. 12. 3.
Priority Queue 개요 Entry를 담는 ADT로, Entry는 보통 key를 우선순위로 하는 { key, value } 쌍이다. 우선순위에 따라 정렬되는 Queue로, Entry 간 Total order relation이 성립한다. Priority Queue 대표적인 operation은 insert, removeMin이 있고, 추가로 min, size, empty 등을 지원할 수 있다. List-based 구현으로 sorted list를 이용하는 방법과 unsorted list를 이용하는 방법이 있다. Total order relation 전순서라고 하며, Reflexive property ( x ≤ x ) Antisymmetric property ( x ≤ y and y ≤ x then x = y ) Transitiv.. 2020. 12. 3.
Educational Codeforces Round 99 (Rated for Div. 2) ABCD import sys input = sys.stdin.readline for TEST in range(int(input())): print(len(input().rstrip())) A - Strange Functions A번에 이렇게 큰 수를 다루는 문제가 나올 리 없기 때문에 당당하게 길이를 출력하였다. #include using namespace std; typedef long long ll; ll dp[2000001]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); set s; for (int i = 1; i TEST; while (TEST--) { int n; cin >> n; cout TEST; while (TEST--) { int.. 2020. 12. 1.
치킨 쿠폰 문제: 처음에 교환 쿠폰 n장이 있고, k장을 사용하면 1장의 쿠폰을 줄 때, 최대 몇 마리의 치킨을 받을 수 있는가? 사용한 총 쿠폰 수를 t라고 하자. 처음 n장이 있으니 t의 초기값은 n이다. 새로 받을 수 있는 쿠폰은 n // k 장이다. t += n // k * 가지고 있는 쿠폰으로 최대한 많이 교환 이때 남는 쿠폰은 n // k + n % k 장이다. n = n % k + n // k * 교환하지 못한 n % k 장 + 이제 새로 받은 n // k 장 이것을 새로 받을 수 있는 쿠폰이 0장이 될 때까지 반복하면 된다. t = n while n//k > 0: t += n//k n = n//k + n%k 이제 t를 한번에 구하자. k개의 쿠폰을 사용하면 1개의 쿠폰을 받으므로, k - 1개의 쿠폰.. 2020. 11. 25.