728x90 Quality control (Univ. Study)/Algorithm Design39 Algorithm Design - B-Tree / B+Tree B-Tree Bayer & McCreight가 1970년에 제안한 구조이다. 차수 m인 B-트리의 특성은 아래와 같다. 1. B-트리는 공백이거나 높이가 1 이상인 m-원 탐색 트리이다. 2. 루트와 리프를 제외한 내부 노드는 아래와 같이 최소 e[m/2u] , 최대 m개의 서브트리를 갖고 있고 적어도 [m/2] - 1개의 키 값(노드의 반 이상 채워짐)을 갖고 있다. 3. 루트 : 리프가 아니면 적어도 두 개의 서브트리를 가진다. 4. 모든 리프는 같은 레벨이다. 또한 B-트리의 장점은 삽입,삭제 뒤에도 균형 상태 유지가 되고 저장 장치의 효율성이 좋다. 각 노드의 반 이상 키 값 저장을 저장하고 최악의 경우에도 O(log_n (N+1))의 시간복잡도를 보장한다. 아래는 이러한 특징이 반영된 3차 B-.. 2024. 4. 5. Algorithm Design - Tree Tree 우선 트리구조를 가볍게 살펴보자. 이미 자료구조론 수업에서 다뤘던 내용이기 때문에 간단하게만 살펴보려한다. Tree terminology 1. 루트(Root): 부모가 없는 노드 (A) 2. 자식(Child): 노드 u가 노드 v의 부모라면, v는 u의 자식입니다. 3. Siblings: 같은 부모를 가진 노드들 4. Internal node: 적어도 하나의 자식을 가진 노드 (A, B, C, F) 5. Leaf node: 자식이 없는 노드 (E, I, J, K, G, H, D) 6. 노드의 깊이(Depth of a node): ancestor의 수 7. Height of a tree: 어떤 노드의 최대 깊이 8. 차수(Degree): 노드의 자식 수 Traversal 종류 Preorder (.. 2024. 4. 4. 알고리즘 설계 실습 - 트리 순환 문제 위의 문제처럼 트리를 만들고 preorder, inorder, postoder함수를 짜서 실행시켜보면되는 단순한 문제이다. 이전에 자료구조론 수업을 들을 때 C++로 몇날 몇일을 고생하면서 B트리를 설계했던 기억이 있는데 비교적 간단한 트리 순환 문제였다. import sys input = sys.stdin.readline # 입력 받기 N = int(input()) # 빈 트리 정의 tree = {} for n in range(N): root, left, right = sys.stdin.readline().strip().split() tree[root] = [left, right] # preorder def preorder(root): if root != '.': print(root, end=''.. 2024. 4. 3. 알고리즘 설계 실습 - k번째 교환(heap sort) 문제 N개의 양의 정수가 저장된 배열 A가 있습니다. 아래 의사 코드 (pseudo-code)를 사용한 힙 정렬 로 배열 A를 정렬할 경우 K 번째 교환되는 수와 K 번 교환된 직후의 배열 A의 모든 원소를 출력 해 보세요. N개의 양의 정수가 저장된 배열에 대한 힙 정렬 의사 코드는 아래와 같습니다. heap_sort(A[1..n]) { # A[1..n]을 정렬한다. build_min_heap(A, n); for i 2024. 3. 30. Algorithm Design - Parallel Sorting Algorithm / 바이토닉 정렬 / 홀짝 정렬 CPU vs GPUGPU는 CPU와 다르게 수천 수만개의 코어가 존재하여 hardware multithreading이나 SIMD(Single Input, Multiple Data)과 같은 병렬처리에서 강력한 모습을 보인다.CPU는 큰 캐시를 갖고 있어서 긴 대기 시간 메모리 액세스를 짧은 대기 시간 캐시 액세스로 변환하는 능력이 있다. 고도화된 제어능력이 있어서 분기 지연 시간 감소를 위한 분기 예측능력과 데이터 지연 시간 단축을 위한 데이터 포워딩도 할 수 있다. 또한 강력한 ALU로 작업 지연 시간을 단축한다.GPU는 작은 캐시가 특징이다. 메모리 처리량을 높이기 위한 것이다. 분기 예측이나 데이터 포워딩이 없다. 에너지 효율이 높은 ALU가 있어서 지연 시간이 길지만 높은 처리량을 위.. 2024. 3. 26. Algorithm Design - 셸 정렬 / 퀵 정렬 / 힙 정렬 / 계수 정렬 / 기수 정렬 Shell Sort 셸 정렬(Shell Sort)은 삽입 정렬을 개선한 버전으로, 1959년 도널드 셸(Donald Shell)에 의해 발표되었다. 삽입 정렬이 이웃하는 요소들과의 비교만을 수행하는 반면, 셸 정렬은 떨어진 요소들과의 비교를 통해 더 빠른 정렬을 가능하게 한다. Stable하고 In-place정렬법이라는 장점이 있다. 우선 정렬 과정을 직접 보자. 정렬과정에서 볼 수 있듯이 셸 정렬에서는 '간격(gap)'이라는 개념을 사용하여, 간격만큼 떨어진 요소들을 서로 비교하고 정렬한다. 초기 간격은 보통 배열 크기의 절반으로 설정하고, 각 단계마다 간격을 줄여나간다. 설정된 간격에 따라 배열을 여러 부분 리스트로 나누고, 각 부분 리스트에 대해 독립적으로 삽입 정렬을 수행한다. 간격을 줄여가며 위.. 2024. 3. 22. 알고리즘 설계 실습 - 두 정삼각형 문제 첫 번째 줄에는 1개의 수를, 두 번째 줄에는 2개의 수를, …, N번째 줄에는 N개의 수를 아래 그림 과 같이 배치한 같은 크기의 정삼각형 A, B가 주어진다. 각 위치에 있는 수는 0 또는 1이다. 정삼각형을 시계방향 또는 반시계 방향으로 120도 회전시키거나 좌우로 대칭시킬 수 있다. 예를 들어, 위 그림의 정삼각형 A를 회전시켜서 얻을 수 있는 정삼각형들은 다음과 같다. A를 횟수 제한 없이 회전시키거나 대칭시켜 B와 차이가 최소로 나게 하라. 이때 차이가 얼마인지 구하라. 차이라는 것은 일치하지 않는 부분의 개수이다. 입력 첫 번째 줄에 A, B의 크기 N이 주어집니다. 두 번째 줄부터 N+1번째 줄까지, 정삼각형 A의 각 위치에 있는 수들이 주어집니다. i+1 (1≤i≤N)번째 줄에는 정.. 2024. 3. 21. Algorithm Design - Master Theorem 마스터 정리T(n) = aT(n/b) + f(n)와 같은 모양을 가진 점화식은 마스터 정리에 의해 바로 분석할 수 있다. 이번 수업시간에 다룬 내용이어서 정리를 하긴하겠으나 마스터 정리는 이전에도 정리를 했었기에 가볍게 정리하고 넘어가자.n^(logb a) = h(n)이라 하면 아래와 같이 복잡도를 구할 수 있다. 이걸 직관적으로 표현하면 아래와 같다. 1. h(n)이 더 무거우면 h(n)이 수행시간을 결정한다.2. f(n)이 더 무거우면 f(n)이 수행시간을 결정한다.3. h(n)과 f(n)이 같은 무게이면 h(n)에 logn을 곱한 것이 수행시간이 된다. 이때 마스터 정리를 이용할 수 있는 조건이 존재한다. 1. f(n)은 asymptotically positive funct.. 2024. 3. 14. Algorithm Design - 실습(GDC_LCM, Sort) GDC_LCM 최대공약수, 최소공배수를 구하는 과제이다. #include using namespace std; // 최대공약수를 계산하는 함수 int gcd(int a, int b) { int min, ans = 0; if(a>b){ min = b; } else{ min = a; } for (int i=1; ib){ base = a; } else{ base = b; } for (int i=base; ;i++) { if ((i%a == 0) && (i%b == 0)) { return i; } } } int main() { int a, b; cin >> a >>b; cout n; // 첫 번째 줄에서 n 을 입력받음 int* numbers = new int[n]; // 동적으로 정수 배열을 할당 // 두 번.. 2024. 3. 13. 이전 1 2 3 4 5 다음 728x90
