본문 바로가기

전체 글75

Error Detection Types of Errors - single-bit error: 주어진 데이터 유닛 중 1bit만 바뀐다. - burst error: multiple error (2 or more bits) Error Detection vs Correction - 공통점: extra/redundant/check bit 수행 - 차이점: correction을 하려면 detection이 선행되어야 한다. correction을 위해선 정확한 비트 넘버와 위치를 알아야 하므로 더 어렵다. Error Detection - Redundancy개념을 이용 - 에러를 감지하기 위해 끝에 extra bits를 더한다. - sender가 redundant bit를 붙이면 receiver는 두 비트 세트 사이의 관계를 체크하고 오류를 감지.. 2021. 5. 1.
Graph - 그래프 정의 및 특성 - Directed graph (digraph) - G = (V, E) - V: vertex들의 집합 - E: V 원소들의 순서쌍 집합 - directed edge (v, w)는 v->w 또는 vw로 나타냄. - Undirected graph - G = (V, E) - V: vertex들의 집합 - E: V 원소들의 순서가 없는 쌍 집합 - undirected edge {v, w}는 v-w 또는 vw, wv로 나타냄. - incident: 간선-정점 간의 연결 관계 / adjacent: 정점-정점 간의 인접 관계 - Weighted Graph - edge에 값이 있는 경우. - (V, E, W)또는 (V, E)로 나타냄 - Graph Representations - G = (V, E), n = |V|, .. 2021. 4. 30.
백준 2193 이친수 www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 아래와 같이 풀었는데 틀렸다고 뜸. 가장 큰 수인 90을 넣어봤더니 음수가 나왔다. 배열타입을 long long int로 고치니 해결됨. #include using namespace std; long long int d[91][2]; int main() { int n; cin >> n; if (n == 1) { cout 2021. 4. 15.
백준 13913 숨바꼭질4 www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1697 숨바꼭질 문제에 경로 출력이 포함된 문제. 초반에 구현한 코드는 아래와 같다. 큐 q에 새로운 원소를 넣을 때 경로를 포함한 temp2큐를 함께 넣어주었다. #include #include using namespace std; int n, k; int visited[200001]; int main() { cin >> n >> k; if (n == k) { cout 2021. 4. 9.
Radix Sort Radix sort 키값에 대한 속성이 주어졌을 때, 비교 연산이 아닌 다른 연산을 사용해 linear time에 정렬을 수행할 수 있다. 속성 예시 : 이름, 다섯 자리 10진수, 범위가 정해진 정수 정렬 과정 1. 서로 다른 pile에 분배 - θ(n) 2. 각각의 pile을 정렬 3. 정렬된 pile들을 합침 - θ(n) 최하위 숫자(or 비트, 문자, 필드)순으로 pile에 분배하면 정렬 과정을 생략 가능 Total O(d*(n+k)) (d: 필드 수(ex. 다섯 자리 십진수에서 5), k: pile 수(ex. 다섯 자리 십진수에서 10(0~9))) -> d, k가 constant라면 θ(n) 2021. 4. 9.
Heapsort Heap 구조((left) Complete binary tree)와 순서(부모 key값 >= 자식 key값)를 만족하는 binary tree HeapSort insert() -> upHeap() : 리프에서 루트까지 swap. O(logn) removeMax() -> deleteMax() : 끝값을 루트에 덮어씌운 뒤 리프까지 swap. findMax() : 루트노드의 키값 리턴. O(1) heapSort(E, n): 배열 E로부터 힙 H를 만든 뒤 max값을 빼서 E에 순서대로 넣는 과정을 n번 반복한다. deleteMax(H): 가장 마지막 노드 값을 가장 첫번째 값에 덮어씌움-> 마지막 노드 삭제-> fixHeap fixHeap(H, K): downHeap. 왼쪽 자식과 오른쪽 자식 중 더 큰 것과.. 2021. 4. 8.

티스토리툴바