전체 글93 Graphs 개요 그래프는 (V, E) 쌍으로 나타낸다. V는 Vertices로 정점의 set을, E는 Edges로 간선의 collection을 의미한다. 둘 모두 position ADT로, 임의의 원소를 저장할 수 있다. Edge의 종류 Directed edge: 순서가 있는 정점 (u, v) 쌍. 각각 origin, destination이라고 한다. Directed graph: 모든 간선이 directed인 그래프 Undirected edge: 순서가 없는 정점 (u, v) 쌍. Undirected graph: 모든 간선이 undirected인 그래프 용어 정리 endpoints: 어떤 간선에 대해 양 끝에 연결된 두 정점. adjacent vertices: 간선으로 직접 연결된 두 정점. incident: 어떤.. 2020. 12. 7. Hash Table 개요 비효율적이었던 맵을 개선 해보자. 맵의 모든 method를 그대로 가지고 있다. 추가로 볼만한 건 다음과 같다. entrySet(): 맵의 모든 entry를 리스트로 반환한다. keySet(): 맵의 모든 key를 리스트로 반환한다. / 파이썬의 dict.keys() values(): 맵의 모든 value를 리스트로 반환한다. / 파이썬의 dict.values() 해시 테이블은 해시 함수 h와 크기 N의 배열 (table)로 이루어진다. 해시 함수 해시 함수 h는 주어진 키 x를 정수 [0, N)에 매핑한다. (예: h(x) = x % N) h(x)는 x에 대한 hash value이고, {키: 값} 쌍을 테이블 index h(키)에 저장하게 된다. 일반적으로 Hash code와 Compression.. 2020. 12. 7. Map & Dictionary 개요 탐색이 용이한 {키: 값} entry의 collection. 맵은 중복 키를 허용하지 않고, 딕셔너리는 중복 키를 허용한다. 맵과 딕셔너리의 Entry ADT {키: 값} 쌍을 저장한다. 다음 네 가지 메소드를 지원한다. key(): 키 반환 value(): 값 반환 setKey(k): 키를 k로 변경 setValue(v): 값을 v로 변경 맵, 딕셔너리 ADT 두 ADT는 공통적으로 다음 메소드를 지원한다. find(k): 키가 k인 entry를 탐색해 포인터를 반환한다. 존재하지 않는 경우 iter::end를 반환한다. put(k, v): 키가 k, 값이 v인 entry를 삽입한다. erase(k): 키가 k인 entry를 삭제한다. 추가로 size, empty, begin, end를 지원할 수.. 2020. 12. 7. 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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 16 다음
